☰

AVLツリー上の赤黒ツリー 質問する

tag-icon • tag-icon algorithm data-structures avl-tree red-black-tree
AVLツリー上の赤黒ツリー 質問する

AVL ツリーと赤黒ツリーは、ノード内の赤と黒の色を除いて、どちらも自己バランスが取れています。AVL ツリーではなく赤黒ツリーを選択する主な理由は何ですか? 赤黒ツリーの用途は何ですか?

ベストアンサー1

AVL ツリーではなく Red black ツリーを選択する主な理由は何ですか?

両方赤黒木そして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

おすすめ記事