红黑树的阶 ◆结点X的阶(rank,也称N黑色高度") 从该结点到外部结点的黑色结点数量 不包括X结点本身,包括叶结点 ◆外部结点的阶是零 ◆根的阶称为该树的阶 rank=2 rank=2 rank= 1 2007年12月25日2时19分 北京大学张铭⊙红黑树2007年12月25日2时19分 北京大学 张铭© 红黑树 10 红黑树的阶 结点X的阶（rank，也称“黑色高度”） „ 从该结点到外部结点的黑色结点数量 „ 不包括X结点本身，包括叶结点 外部结点的阶是零 根的阶称为该树的阶 9 4 15 2 6 12 7 21 rank=2 rank=1 rank=2