2

二分探索木を前後に移動する最悪の場合の効率に興味があります。

アンバランスな木:

   5
  /
 1 
  \
   2
    \
     3
      \
       4

最悪のケースは 4->5 のようで、4 回の操作が必要です。

バランスのとれた木:

   2
  / \
 1   4
    / \ 
   3   5

最悪のケースは 2->3 で、2 回の操作が必要です。

BST の最悪のケースは O(height-1) であり、これはバランスの取れたツリーでは O(log n) であり、バランスの取れていないツリーでは O(n-1) であると考えるのは正しいですか?

4

2 に答える 2

3

BST の最悪のケースは O(height-1) であり、これはバランスの取れたツリーでは O(log n) であり、バランスの取れていないツリーでは O(n-1) であると考えるのは正しいですか?

はい、 から に移動する場合は、上または下に移動するだけでよくk、k+1両方ではありません (不変条件が であるためleft child < parent < right child)。

O(height-1) は O(height) と書くことができますが (O(n) についても同様です)。

于 2012-05-19T12:16:42.197 に答える
1

ツリーを順番にトラバースすることだけを考えている場合、バランスに関して複雑さは変わりません。アルゴリズムはそのまま

 walk( Node n)
    walk( n.left )
    visit( n )
    walk( n.right )

ステップごとに 1 オペレーション。

ルックアップ、挿入、および削除の適用を開始すると、バランスが機能します。

そして、これらの操作を O(log N ) にするには、バランスの取れたツリーが必要です。

ツリーによって定義されたシーケンスで次の要素を見つけようとしている場合、ツリーの高さ全体を移動する必要がある場合があります。もちろん、バランスの取れたツリーではこれは O (log N) であり、バランスの取れていないツリーではこれはO（N）です

于 2012-05-19T12:21:24.730 に答える