赤黒木の構造と利点

Structure Advantages Red Black Trees

まず、赤黒木の構造を見てください。

赤黒木の構造的特徴：
（1）各ノードは黒または赤のいずれかです。
（2）ルートノードが黒です。
（3）各リーフノード（NIL）は黒です。 [注：ここでのリーフノードとは、空（NILまたはNULL）のリーフノードを指します。 ]
（4）ノードが赤の場合、その子は黒でなければなりません。
（5）ノードからノードの子孫ノードまでのすべてのパスに同じ数の黒いノードが含まれます。

なぜ赤と黒の木を使うのですか？
1.まず、赤黒木はAVL木のバランス条件に適合していません。つまり、各ノードの左側のサブツリーと右側のサブツリーのバイナリツリーの最大差は1です。ただし、ノードに色を追加することをお勧めします。ノードを追加または削除するときのローテーションの数を減らすために、赤黒木は非厳密なバランスに置き換えられます。不均衡は3回転以内に解決され、AVLは厳密にバランスの取れたツリーであるため、追加または削除されます。ノードを使用する場合、状況によっては、赤や黒の木よりも回転が多くなります。したがって、赤と黒の木の挿入はより効率的です。

2.赤と黒の木は、O（log2（n））の時間計算量で操作を検索、挿入、および削除できます。

3.簡単に言えば、二分探索木は線形構造に縮退する場合があるため、赤黒木は二分探索木の欠陥を解決することです。

赤とバランスの取れた木の比較と選択
1.バランスツリーの構造はより直感的で、読み取りパフォーマンスは赤黒ツリーよりも高く、ノードの追加と削除は赤黒ツリーほど良くありません。
2、赤と黒の木、読み取りパフォーマンスはバランスツリーの追加と削除ほど良くありません回復バランスパフォーマンスはバランスツリーよりも優れています

赤黒木の使用シナリオ：
JDK1.8以降のTreeMap、TreeSet、およびHashMapは、赤黒木を使用します。