0

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

ここに画像の説明を入力

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

4

2 に答える 2

1

ウィキペディアのプロパティとケースに基づいて...

3622ケース 5 の下に挿入され、左に回転します。

親のPは赤ですが、おじさんは黒かそこにいません。

ウィキペディアは「おじさんは黒人」と言っているだけですが、コードを見ると、そのケースがトリガーされていることがわかります。


36プロパティ 5 (特定のノードからそのリーフ ノードへのすべてのパスに同じ数の黒いノードが含まれる) が保持されていないため、なしのツリーは既に無効であることに注意してください。

  • 20 ~ 15 には 1 つの黒ノードが含まれます
  • 20 ~ 30 には 2 つの黒いノードが含まれます

挿入順序が20, 15, 22, 30, 36...

すべてのノードが赤で挿入されます。

22ケース 2 の下に挿入されます。

親は黒人。

30ケース3の下に挿入され2215黒と20赤を作ります。

親と叔父は赤です。どちらも黒く塗り直され、祖父母は赤くなります。

3622ケース 5 の下に挿入され、左に回転します。

親のPは赤ですが、おじさんは黒かそこにいません。

于 2013-11-06T09:38:41.640 に答える