2

ここで非常に簡単な質問があります。赤黒木は並べ替えられた順序である必要がありますか？ウィキペディアページ（http://en.wikipedia.org/wiki/Red–black_tree）の右側にある小さなボックスには、検索時間はO（log（n））と書かれているので、これを尋ねます。ただし、これは、ツリーがソートされている場合にのみ当てはまります。一方、プロパティは

4

4 に答える 4

6

赤黒木はソートされたツリーです（すべてのRBツリー全体がソートされた二分木ですが、すべてのソートされた二分木が赤黒木であるとは限りません）。プレーンな二分木と赤黒木との違いは、RBツリーはバランスが取れているため、検索時間がlog 2（n）になることを保証することです。本質的には、 nノードのレイヤー数がlog 2（n）を超えないことを保証し、バイナリ検索を抑制します。

バランシングのない単純な二分木は、常にlog 2（n）時間計算量を生成するとは限りません。たとえば、次のようなツリーがある場合：

  4
 / \
3   6
     \
      7
       \
       10
         \
         12

この不均衡なツリーの場合、実際の検索時間はほぼ直線的に検出されます12（最悪の場合の時間計算量、5回の比較）。最大でlog2 （ n）層を持つ平衡ツリーの場合、上のツリーは次のようになります。

     7
   /   \
  4    10
 / \     \
3   6    12

したがって、最下位層のノードのいずれかを見つけるには、最大3つの比較が必要になります（実際には切り上げられているため、log 2（n）に適合します。ceil[log2 （ 6）] = 3）

ここで重要なのは、レイヤーの数は、ルートから開始するときに行う必要のある比較の数と機能的に同等であることを覚えておくことです。赤黒木は、バランスをとることによってレイヤーの数を最小限に制限しますが、バニラの不均衡な二分木はそうではありません。

于 2012-09-24T22:40:52.793 に答える
2

赤黒木は二分探索木です。二分探索木の定義により、左の子（およびすべての子孫）は親よりも小さく、右の子（およびすべての子孫）は親よりも大きくなければなりません。したがって、順序があります。

于 2012-09-24T22:37:38.810 に答える
1

赤黒木は、ノードを自然な順序で設定する方法のため、検索時間はO（log n）です。

ノード比較を行う場合、理論的には、ブランチを利用するときにオプションの半分を破棄します。

1つの要素に到達する前に「半分」しかできないためlog n times、検索の複雑さは次のようになります。O(log n)

于 2012-09-24T22:37:37.127 に答える
1

赤黒木の要点は、ある程度バランスを保つことです。並べ替えの制約を緩和すると、ノードを好きな場所に配置できるため、ツリーのバランスを保つのは簡単です。

于 2012-09-24T22:56:59.013 に答える