ノード 36 を赤黒ツリーに挿入すると、次の赤黒ツリーが生成されました。
私の問題は、この特別な場合にダブルレッドを処理する方法ですか? ケース2または3ですか？
2 に答える
1
ウィキペディアのプロパティとケースに基づいて...
3622ケース 5 の下に挿入され、左に回転します。
親のPは赤ですが、おじさんは黒かそこにいません。
ウィキペディアは「おじさんは黒人」と言っているだけですが、コードを見ると、そのケースがトリガーされていることがわかります。
36プロパティ 5 (特定のノードからそのリーフ ノードへのすべてのパスに同じ数の黒いノードが含まれる) が保持されていないため、なしのツリーは既に無効であることに注意してください。
- 20 ～ 15 には 1 つの黒ノードが含まれます
- 20 ～ 30 には 2 つの黒いノードが含まれます
挿入順序が20, 15, 22, 30, 36...
すべてのノードが赤で挿入されます。
22ケース 2 の下に挿入されます。
親は黒人。
30ケース3の下に挿入され22、15黒と20赤を作ります。
親と叔父は赤です。どちらも黒く塗り直され、祖父母は赤くなります。
3622ケース 5 の下に挿入され、左に回転します。
親のPは赤ですが、おじさんは黒かそこにいません。
于 2013-11-06T09:38:41.640 に答える