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