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

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