题17

题17

题目

Q:下列关于红黑树和 AVL 树的描述中, 不正确的是 ( ).
A. 两者都属于自平衡的二叉树
B. 两者查找、插入、删除的时间复杂度都相同
C. 红黑树插入和删除过程至多有 2 次旋转操作
D. 红黑树的任意一个结点的左右子树高度（含叶结点）之比不超过 2

分析

A:这个题目我觉得是选B，但是选错了
D选项描述的就是红黑树的最长路径不会超过最短路径的两倍

解

C
自平衡的二叉排序树是指在插入和删除时能自动调整以保持其所定义的平衡性, 两者都属于自平衡二叉树, 正确。两者的查找、插入、删除操作的时间复杂度都为 正确。
在红黑树中删除结点时, 情况 1 可能变为情况 2、3 或 4 , 情况 2 会变为情况 3 , 可能会出现旋转次数超过 2 次的情况, 错误。
从任一结点到每个叶结点的所有路径都包含相同数目的黑结点，没有两个连续的红结点, 且叶结点是红色的, 这意味着在任一结点到其左右子树中最远和最近的叶结点之间, 红结点的数目小于或等于黑结点的数目, 路径长度之比不超过 2, D 正确。