题16

题16

题目

下列关于红黑树和 AVL 树的说法中, 不正确的是 ( ).
I. 一棵含有 个结点的红黑树的高度至多为
II. 若一个结点是红色的, 则它的父结点和孩子结点都是黑色的
III. 红黑树的查询效率一般要优于含有相同结点数的 AVL 树
IV. 若 AVL 树的某结点的左右孩子的平衡因子都是零, 则该结点的平衡因子也是零
A. I、III
B. III
C. II、IV
D. III、IV

分析

一棵含有 个结点的红黑树的高度至多为 ====
第二个是红黑树的性质之一，也就是根叶红这个性质
红黑树需要维护更多的结点信息，我感觉会拖累查询效率
左右孩子的平衡因子为0，说明左孩子的左右子树的高度差是0，右孩子的左右子树的高度差也是0，当前结点的平衡因子，取决于当前结点的左右子树的高度差
一定要注意这是个高度的差，不是高度，差为0，和高度本身无关，而高度本身，往往会决定一些

解

D
I 和 II 都是红黑树的性质。
AVL 是高度平衡的二叉查找树, 红黑树是适度平衡的二叉查找树, 从这一点也可以看出 AVL 的查询效率往往更优, III 错误。
AVL 的某结点的左右孩子的平衡因子都是零, 并不能说明左右子树的高度相等, 因此该结点的平衡因子不一定为零, IV 错误。