ソートされた値に対する赤黒の挿入操作の動作

Question

データ構造体が新しくなった。私は赤黒の木の挿入アルゴリズムの実装を行った。アルゴリズムがソートされた値の挿入をどのように処理するか、私は理解できません。

データセット[10,5,2]で説明しましょう。

したがって、初期値10が挿入され、ツリーのルートになり、その色が黒になります。

次に、ルート10の下に5を追加します.5の色は赤色になります（今のところ、プロパティに違反していません）。 （その色は赤です）赤親の下に赤の子を許可しないのルールに違反することになります2の 追加 - ：

今、私たちはさらに後2を追加する追加します、ツリーは次のようになります。 Red-blackツリーに3つのケースがあります： - 3つのケースはすべて、parentOf（newlyInsertedNode）に兄弟があるとみなします。しかし、私の場合、parentOf（2）= 5には兄弟はありません。だから、このシナリオがRed-black treeアルゴリズムでどのように扱われるのか。

Answer 1

赤黒のツリーの詳細は、記事/ブック/実装によって少し異なる場合があります。

しかし、非常に一般的な変形がIntroduction To Algorithms (CLRS)によって使用されています。この変形例では、特別な子供がNILです。 A NIL子供には特別な「Null」キーが含まれており、それは単なる葉であることを示しています。

RBの木のための不変量は、次のとおり

1. すべてのノードが赤または黒のいずれかです。
2. 根は黒です。
3. すべての葉（NIL）は黒です。
4. ノードが赤の場合、その子は両方とも黒です。各ノードについて
5. 、葉子孫ノードからのすべての単純なパスがブラックノードの同数

注意を含む、特に、不変3からNILノードが黒色です。この共通のバリアントを使用して

---

は、あなたのRBの木は、4つの追加のノードを持っています

2. 右の子の5

3. 左の右の子と右の子ども2

5の右の子は、あなたが欠けている兄弟です。