张铭红黑树 2007年12月25日2时19分 情况1b重构:侄子红结点同边顺 情况2:兄弟是黑色,且有两个黑子结点 ●将D结点旋转为C结点的父结点,D继承原子根 B的颜色,B着为黑色 ◆把C着红色,B着黑色 ◆如果B原为红色,则算法结束 ◆否则,对B继续作双黑“调整 Ra 有可能量端 双处覆 2007年12月2日2时19分 北京大学张铭心红黑树 2007年12月25日2时19分 北京大学张铭心红黑树 情况3:兄弟C是红色 删除90 ●旋转 ◆当前结点变为80的右黑叶结点 ●X结点仍是双黑“”结点,转化为前面2种情况 ◆C是黑色,且有两个黑色子结点:情况2 b 2007年12月25日】时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张心红黑树 删除90 删除70 ◆当前结点变为80的右黑叶结点 ◆红结点,不要调整 ◆c是黑色且有两个黑色子结点:情况2换色 X 00?年12月25日2时 北京大学张铭红里树 2007年12月25日2时19分 北京大学张铭红黑树 5张铭 红黑树 2007年12月25日2时19分 5 2007年12月25日2时19分 北京大学 张铭© 红黑树 25 情况1(b)重构：侄子红结点同边顺 将D结点旋转为C结点的父结点，D继承原子根 B的颜色，B着为黑色 B X E C D α β B C D X α E β 2007年12月25日2时19分 北京大学 张铭© 红黑树 26 情况2：兄弟是黑色, 且有两个黑子结点 把C着红色，B着黑色 如果B原为红色，则算法结束 否则，对B继续作“双黑”调整 B X D E C B C D E X 有可能继续 双黑处理 2007年12月25日2时19分 北京大学 张铭© 红黑树 27 情况3：兄弟C 是红色 旋转 X结点仍是“双黑”结点，转化为前面2种情况 B X C α β X B C α β 2007年12月25日2时19分 北京大学 张铭© 红黑树 28 删除90 当前结点变为80的右黑叶结点 C 是黑色, 且有两个黑色子结点：情况2 65 50 10 60 62 80 70 90 B B X C E D E C D X C X B 2007年12月25日2时19分 北京大学 张铭© 红黑树 29 删除90 当前结点变为80的右黑叶结点 C 是黑色, 且有两个黑色子结点：情况2换色 65 50 10 60 62 80 70 B B X C E D E C D X C X 70 B 2007年12月25日2时19分 北京大学 张铭© 红黑树 30 删除70 红结点，不要调整 65 50 10 60 62 80 70