バイナリツリーを作成する時間の複雑さ

ツリーに追加する2つのノードと、2つのニュースノードを追加するノードを提供するソースからツリーを作成しようとしています。このノードがツリー内のどこにあるかを知るために、私はO（n）を取るinorder traversalを使いました。したがって、ツリーにn個のノードを追加すると、ツリー全体の作成はO（n^2）になります。私の制約は、木を作るのにO（n）しかかからないということです。バイナリツリーを作成する時間の複雑さ

出典

2012-03-11 Dan

私は本当に 'n（n log n）'より少ない数で2つのノードを次々に追加する方法を見ることができません。あなたの説明には何かがないようです。また、それは宿題なので、適切なタグを追加する必要があります。 – Voo

ツリー内の正しい場所を見つけるためにインオーダートラバーサルが必要なのはなぜですか？ノードは、O（log（n））の平均時間内に特定のノードを見つけることができるように配置する必要があります。あなたがそのような取り決めをすることができない場合、バイナリツリーはあなたのデータの正しい構造ではないかもしれません。 – Gigatron

ツリーの典型的なO(log(n))ではなく、各ノードへのアクセスがO(1)になるように、HashMap [1]のツリーの各ノードへの参照を保持できます。 HashMapを使うと、ツリーのルートノードからそのノードを横断するのではなく、ノードに直接ジャンプすることができるので、O(n)の時間にツリーを構築することが可能になります。

[1]鍵は、ノードを一意に識別するためにソースが使用するもので、私はそれを整数または文字列とみなしています。値は、ツリー内のノードへの参照になります。ツリーの実装では、すべてのノードをパブリックにする必要があるため、ツリーを自分で作成するか、適切なライブラリ（TreeMapなどのJDKのツリーは内部構造を非公開にして切断しない）を見つける必要があります。

出典

2012-03-11 22:23:33

これで問題は解決しますが、もう1つの質問があります。なぜなら、その時点でHashMapにデータを格納し、ツリー全体を捨てるだけではないからです。 – twain249

twain249：真。これが宿題であれば、私は樹木を使う本当の理由はないと思っています。 :)現実的な（しかしまれな）理由の1つは、システムが再起動後のファイル（つまりO（n）の起動時間）から状態を素早く復元する必要があり、通常の動作中にシステムが厳密な最悪ケースしたがって、ハッシュマップの償却されたO（1）は受け入れられませんが、ツリーの予測可能なO（log（n））が必要です）。 –

完全なハッシュ関数**または 'O（1）average'を与えられた** O（1）の償却時間は、この答えでもっと主に現れるはずです:-) –

バイナリツリー内のノードを検索すると、log(n)（各レベルはそれより上のレベルの2倍の大きさ）のツリーがあるため、O(log(n))です。したがって、n要素をバイナリツリーに作成/挿入するには、O(nlog(n))です。

出典

2012-03-11 22:19:33 twain249

バイナリ検索ツリー時間の複雑さは、要素がソートされずソートされていない場合はO（n^2）である場合はO（nlogn）になります。これは、BST O（n）時間内のソートされたリストに1つの要素を挿入するために、n個の要素O（n^2）に対して、平衡型またはほぼ平衡型のバイナリ検索ツリーの最大挿入時間をlognとすると、 n要素それはnlognです

出典

2015-09-18 09:44:49 Guest

バイナリツリーを作成する時間の複雑さ

答えて

関連する問題