問題タブ [red-black-tree-insertion]

ノード 36 を赤黒ツリーに挿入すると、次の赤黒ツリーが生成されました。

私の問題は、この特別な場合にダブルレッドを処理する方法ですか? ケース2または3ですか？

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

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

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

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

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

これは、番号を入力したときにセグメンテーション違反 11 を示しています。助けてください。私はこれで2時間立ち往生しています。いろいろ試しましたが抜けません。助けてください。rbInsert または回転関数に問題がある可能性がありますが、見つかりません。どんな助けでも大歓迎です。

赤/黒の木に関するJavaのクラスのプログラムを書いています。それらが通常どのように機能するかをよく理解しており、再帰的な挿入方法を使用することになっています。私が通常使用するのは、私の教授の Node クラスと一致するように、以下のとおりです。色に関しては、0 は黒、1 は赤です。私たちに与えられた Node クラスは、キーをまったく扱いません。

ただし、問題はブール値を返すことになっていることです。ユーザーがツリーに既にある値と同じ値を挿入した場合、false を返し、ノードをアタッチしません。それ以外の場合は、それらをアタッチして true を返します。このために提供されたコードを以下に示しますが、再帰的ではありません (プロジェクト要件の一部)。適切にバランス調整または回転する方法を実装していませんでしたが、返されたブール部分は機能します。

同等の実装をオンラインで見つけることができませんでした。プログラムの GUI が適切に機能するにはブール値が必要なようです。誰かがどこから始めるべきかについて良い提案があれば、私はそれを感謝します!