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

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つのポインタ）だけです。データ、左の子リンク、および右の子リンク。