红黑树的性质 ◆(1)红黑树是满二叉树 空叶结点也看作结点 ◆(2)阶为k的红黑树路径长度 从根到叶的简单路径长度最短是k,最长是2k 即树高最小是k+1,最高是2k+1 ◆(3)阶为k的红黑树的内部结点 最少是一棵完全满二叉树 Q 内部结点数最少是2k-1 2007年12月25日2时19分 北京大学张铭⊙红黑树2007年12月25日2时19分 北京大学 张铭© 红黑树 11 红黑树的性质 (1) 红黑树是满二叉树 „ 空叶结点也看作结点 (2) 阶为k的红黑树路径长度 „ 从根到叶的简单路径长度 „ 即树高 (3) 阶为k的红黑树的内部结点 „ 最少是一棵完全满二叉树 „ 内部结点数最少是2k-1 9 4 15 2 6 12 7 最短是k 最小是k+1 ，最长是2k ，最高是2k+1 6 2 9