8

ツリー操作の複雑な時間について質問があります。
（Data Structures、Horowitz et al）BSTでの挿入、削除、検索、最小-最大、後続および先行ノードの検索の時間計算量は、AVLの場合と同じであるO(h)と言われていますO(logn)。
違いが何なのか正確にはわかりません。念頭h=[logn]+1に置いて、なぜ私たちはO(h)どこか他の場所で言うのですO(logn)か？

4

2 に答える 2

11

h木の高さです。それは常にOmega(logn)[漸近的にそれよりも小さいわけではありませんlogn]。完全なツリーに非常に近い場合がありlognます（実際には取得h=logn+1しますが、チェーンに崩壊したツリー（各ノードには息子が1人しかいません）ではそうです）O(n)。

バランスの取れたツリーの場合h=O(logn)（実際にはTheta(logn)そうです）、O(h)それらのアルゴリズムは実際にはO(logn)です。

自己平衡探索木（およびAVLはその1つです）のアイデアは、ツリーがチェーン（またはその近くのどこか）に崩壊するケースを防ぐことであり、その（平衡ツリー）機能によってO(logn)高さが保証されます。

編集：
この問題をよりよく理解するために、次の2つのツリーを検討してください（そして、ひどいアスキーアーティストであることを許してください）：

          tree 1                                tree 2
            7
           /
          6
         /
        5                                         4
       /                                      /       \
      4                                      2         6
     /                                    /    \     /   \
    3                                    1      3   5     7
   /
  2
 /
1

どちらも有効な二分探索木であり、両方の要素の検索（たとえば1）はになりますO(h)。しかし、最初O(h)は、実際O(n)にはですが、2番目はですO(logn)

于 2012-09-04T06:49:30.767 に答える
2

O(h)木の高さに依存する複雑さの線形を意味します。ツリーのバランスが取れている場合、この漸近線はO(logn)（n-要素の数）になります。しかし、それはすべての木に当てはまるわけではありません。各ノードが子を残しただけの非常に不均衡な二分木を想像してみてください。このツリーは、ツリーのリストと要素の数がツリーの高さに等しくなるようになります。説明されている操作の複雑さは、O(n)代わりになりますO(logn)

于 2012-09-04T06:53:13.613 に答える