一般的なツリーからバイナリツリー変換の複雑さ

Question

一般的なツリーをバイナリツリーに変換する時間と空間の複雑さは何ですか？！

ありがとう

Answer 1

「一般的な木」とはどういう意味かわかりません。とにかく、バランスのとれたバイナリツリーへの挿入の複雑さは O(log n), 、 どこ n 現在ツリー内にあるアイテムの数なのため、アイテムのリストから完全なツリーを構築する O(n log n), 、 どこ n 挿入するアイテムの総数です。

また、他のツリーからアイテムを取得するために必要な時間を含める必要があります。その時間は、あなたが持っている木の種類に依存します。議論のために、私はあなたが線形時間にそれを通過できると仮定するので、既存のツリーからデータを取得することは O(n).

それはあなたの合計時間の複雑さになります O(n + (n log n)).

必要な余分なスペースは次のとおりです n * sizeof(node), 、 どこ sizeof(node) バイナリツリーノードのサイズです。 「一般的なツリー」ノードに保存されているアイテムがポインターである場合、実際のオブジェクトをコピーするコストを支払う必要はありません。バイナリツリーノードのオーバーヘッド、通常は3つのポインターです。データ、左の子供のリンク、および右の子供リンク。