经典指数          
原因
3402
浏览数
0
收藏数
 

红黑树的定义如下:一颗二叉查找树如果满足下面的红黑性质,则为一棵红黑树:
1)每个节点只能是红色或者黑色之一
2)根节点是黑色
3)每个叶节点是黑色
4)如果一个节点是红色,则它的两个子节点都是黑色
5)对每个节点,从该节点到其子孙节点的所有路径上包含相同数目的黑节点 对于一棵有n个内节点的红黑树,
下面描述错误的是____。
  • 从任意节点出发的所有下降路径都有相同的黑节点个数
  • 从任意节点出发的所有下降路径都有相同的红节点个数
  • 该树的高度不超过2log(n+1)
  • 从某节点到其后代叶节点的所有简单路径中,最长的一条是最短一条的至多两倍
  • 从根到叶节点(不包含根)的任一条简单路径上至少有一半的节点必是黑色的
  • 在红黑树上的查找操作可以在O(logn)时间内完成

     举报   纠错  
 
切换
1 个答案

由性质5可知,A对

从5个性质中不能推出B,B错

对于全是黑结点的红黑树,高度不超过log(n+1),该树中每两层之间最多插入一层全红结点,所以高度是不可能大于2log(n+1)的,特殊情况是只有一个黑色根节点,2log(2+1)=2>1,所以C对

D选项中最长的就是每两个黑结点中夹着一个红结点,又由性质5,所以D对

E和D的意思差不多,所以E也对

红黑树是一种平衡二叉树,而且由C选项可以看出高度小于等于2log(n+1),查找时间肯定是O(logn)级别的,所以F也对

最后答案选B

 
切换
撰写答案