红黑树:平衡的扩充二叉搜索树 ◆颜色特征:结点是红色或黑色 ◆根特征:根结点永远是黑色”的; 2bI u at ◆外部特征:扩充外部叶结点都是空的黑色“结点 ◆内部特征:"红色"结点的两个子结点都是黑色”的 不允许两个连续的红色结点 ◆深度特征:任何绩点到其子孙外部结点的每条简单路径都包含相 同数目的黑色结点 2007年12月25日2时19分 北京大学张铭⊙红黑树2007年12月25日2时19分 北京大学 张铭© 红黑树 9 红黑树：平衡的扩充二叉搜索树 颜色特征：结点是“红色” 或“黑色” ； 根特征：根结点永远是“黑色”的； 外部特征：扩充外部叶结点都是空的“黑色”结点； 内部特征： “红色”结点的两个子结点都是“黑色”的 „ 不允许两个连续的红色结点 深度特征：任何结点到其子孙外部结点的每条简单路径都包含相 同数目的“黑色”结点 9 4 15 2 6 12 7 21 “红色” “黑色” 扩充