46

赤黒 (RB) ツリーの用途は何ですか? RB Tree のみを使用でき、他のデータ構造を使用できないアプリケーションはありますか?

4

4 に答える 4

37

赤黒木は自己平衡二分探索木の特定の実装であり、今日では実装の最も一般的な選択肢のようです。

二分探索木は、関連付けられた値を持つ一連のキーを格納する有限マップを実装するために使用されます。キーのみを使用し、値を格納しないでセットを実装することもできます。

良好なパフォーマンスを保証するには、ツリーのバランスを取る必要があります。そうしないと、たとえば、既にソートされているキーを挿入した場合などに、ツリーがリストに縮退する可能性があります。

ハッシュ テーブルに対する検索ツリーの利点は、ツリーをソート順に効率的にトラバースできることです。

AVL ツリーは、平衡二分探索ツリーの別の変形です。赤黒木が知られる前に人気がありました。それらは、左右のサブツリーの高さの最大差が 1 になるように、より慎重にバランスが取られています (RB ツリーは最大で 2 倍を保証します)。それらの主な欠点は、リバランスに手間がかかることです。

したがって、赤黒木は確かに優れていますが、このアプリケーションの唯一の選択肢ではありません。

于 2010-10-10T17:20:35.743 に答える
16

Red Black Trees は、自己平衡 BST のクラスに属し、他の人が回答したように、そのような自己平衡ツリーを使用できます。赤黒木は、システム シンボル テーブルとして広く使用されていることを付け加えておきます。たとえば、次の実装に使用されます。

  • Java: java.util.TreeMap 、 java.util.TreeSet 。
  • C++ STL: マップ、マルチマップ、マルチセット。
  • Linux カーネル: 完全に公平なスケジューラー、linux/rbtree.h
于 2014-03-21T12:27:28.617 に答える
9

非常に具体的なパフォーマンス要件がない限り、RB ツリーは、AVL ツリーなどの他の自己均衡バイナリ ツリーに置き換えることができます。この 2 つのどちらかを選択すると、基本的にパフォーマンスが最適化されます。基本的な操作は同じです。

それらのいずれかが他方よりも決定的に「高速」であるというわけではなく、それらの特定の用途がわずかに異なるパフォーマンスを持つ傾向があるほど十分に異なっているというだけで、他のすべては同じです。そのため、要件を慎重に、または偶然に引き出すと、そのうちの 1 つが「十分に高速」であり、もう 1 つがそうでないという結果になる可能性があります。RB は AVL よりもわずかに高速な挿入を提供しますが、ルックアップがわずかに遅くなります。

于 2010-10-10T16:45:24.790 に答える
8

赤黒は特定の場合にのみ使用できるなどのルールはありません。ツリーを一度だけ構築する必要があり、何度もクエリを実行する必要がある場合など、アプリケーションに依存します。AVL ツリーを使用できます。 AVL ツリーの検索は非常に高速ですが、厳密にバランスが取れているため、挿入と削除に時間がかかる場合があります。現在の Linux カーネルで使用されている Fair Scheduler は、今日では..

レッド ブラック ツリーに適用される制約は、ルートから最も遠いリーフまでのパスの長さが、ルートから最も近いリーフまでのパスの長さの 2 倍を超えないという点も強制します。

ところで、ここで赤黒の木に必要なさまざまな検索や挿入などの時間を探すことができます

        Average     Worst case

Space   O(n)        O(n) 

Search  O(log n)    O(log n)

Insert  O(log n)    O(log n)

Delete  O(log n)    O(log n)
于 2012-12-19T06:05:48.363 に答える