143

AVL と赤黒の木は、ノードの赤と黒の色を除いて、どちらも自己平衡です。AVL ツリーの代わりにレッド ブラック ツリーを選択する主な理由は何ですか? レッドブラックツリーの用途は何ですか?

4

5 に答える 5

161

AVL ツリーの代わりにレッド ブラック ツリーを選択する主な理由は何ですか?

赤黒木とAVL 木はどちらも、最も一般的に使用される平衡二分探索木であり、保証付きで挿入、削除、検索をサポートしますO(logN) time。ただし、両者には次のような比較ポイントがあります。

  • AVL ツリーはより厳密にバランスが取れているため、ルックアップが高速になります。したがって、ルックアップを多用するタスクには、AVL ツリーを使用します。
  • 挿入が多いタスクの場合は、赤黒ツリーを使用します。
  • AVL ツリーは、各ノードでバランス係数を格納します。これにはO(N)余分なスペースが必要です。ただし、ツリーに挿入されるキーが常に 0 より大きいことがわかっている場合は、キーの符号ビットを使用して、赤黒ツリーの色情報を格納できます。したがって、そのような場合、赤黒木は余分なスペースを取りません。

レッドブラックツリーの用途は何ですか?

赤黒木はより汎用的です。追加、削除、およびルックアップでは比較的うまく機能しますが、AVL ツリーは追加/削除が遅くなる代わりにルックアップが高速になります。赤黒木は以下で使用されます。

  • ジャワ: java.util.TreeMap,java.util.TreeSet
  • C++ STL (ほとんどの実装で): map、multimap、multiset
  • Linux カーネル: 完全に公平なスケジューラー、linux/rbtree.h
于 2014-04-24T18:50:40.037 に答える
21

この記事を読んでみてください

相違点、類似点、パフォーマンスなどに関する優れた洞察を提供します。

記事からの引用は次のとおりです。

RB ツリーは、AVL ツリーと同様に自己バランスをとります。どちらも O(log n) ルックアップと挿入のパフォーマンスを提供します。

違いは、RB ツリーは挿入操作ごとに O(1) 回のローテーションを保証することです。これが、実際の実装で実際にパフォーマンスを犠牲にするものです。

簡素化された RB ツリーは、動的ノード構造のオーバーヘッドを持ち運ぶことなく、概念的に 2 ～ 3 個のツリーであることからこの利点を得ることができます。物理的に RB ツリーはバイナリ ツリーとして実装され、赤/黒のフラグは 2-3 の動作をシミュレートします。

私が理解している限りでは、AVL ツリーと RB ツリーはパフォーマンスの点でそれほど離れていません。RB ツリーは単純に B ツリーの変形であり、バランス調整は AVL ツリーとは異なる方法で実装されます。

于 2012-12-13T04:22:55.350 に答える