08/06/16 15:22:19
赤黒木のアルゴリズムについて質問があります。
●を黒ノード、□を赤ノードとした時に
●a
／＼
／ ＼
●b □c
＼ ／＼
□d ●e ●f
からcを削除してeを昇格させる場合、削除対象が赤で置き換えるノードが黒なので
URLﾘﾝｸ(www.geocities.jp)の削除アルゴリズムケース0にしたがって
特に何もしなくて良いという事になり、全体の構造が下の図
●a
／＼
／ ＼
●b ●e
＼ ＼
□d ●f
の様になるんですが、これってイリーガルじゃないんでしょうか？fから根へ辿る時に黒ノードが3つになってしまいます。
fを赤に変更すれば良いんでしょうか？でもfの子に赤が含まれている可能性もあってちょっと億劫です。
もしくは、eが赤になれば良いんでしょうか？子を一つしか持たない赤のノードは存在し得ないと思うのですが。