2

私はデータ構造が初めてです。赤黒木挿入アルゴリズムの実装を経験しました。アルゴリズムがソートされた値の挿入をどのように処理するかを理解できません。

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

したがって、イニシャル 10 が挿入され、ツリーのルートになり、その色は黒になります。10ここに画像の説明を入力

次に、ルート 10 の下に 5 を追加します。5 の色は赤になります (現時点では、どのプロパティにも違反していません)。 ここに画像の説明を入力

次に、2 を追加して追加します。追加後、ツリーは次のようになります:- ここに画像の説明を入力 2 (色が赤) の追加は、赤い親の下に赤い子を許可しないという規則に違反します。赤黒木には 3 つのケースがあります:- 3 つのケースはすべて、parentOf(newlyInsertedNode) に兄弟があることを前提としています。しかし、私の場合、parentOf(2) = 5 には兄弟がありません。では、このシナリオが赤黒木アルゴリズムでどのように処理されるか。

4

1 に答える 1

1

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

ただし、Introduction To Algorithms (CLRS)で使用される非常に一般的なバリアントがあります。このバリアントには、特別なNIL子がいます。子には特別なNIL「Null」キーが含まれており、これは単なるリーフであることを示しています。

RB ツリーの不変条件は次のとおりです。

  1. すべてのノードは、赤または黒のいずれかです。
  2. 根元は黒。
  3. すべての葉 ( NIL) は黒です。
  4. ノードが赤の場合、その子は両方とも黒です。
  5. ノードごとに、ノードから子孫の葉へのすべての単純なパスには、同じ数の黒いノードが含まれます

特に、不変の 3 -NILノードは黒であることに注意してください。

この一般的なバリアントを使用すると、RB ツリーに 4 つのノードが追加されます。

  1. 10の右の子

  2. 5の右の子

  3. 2 の左右の子

5 歳の右の子は、あなたが行方不明になっている兄弟です。

于 2016-11-03T13:36:13.107 に答える