数据结构与算法 · 单选题 · 第 60 题
计算机基础面试八股 · 第 60 题
关于红黑树和 AVL 树的比较,下列说法正确的是?
- A红黑树的平衡要求更宽松,插入删除时旋转更少,适合写操作较多的场景
- B红黑树是严格平衡的,所以它的查找性能总是比 AVL 树更好
- C红黑树依靠节点颜色来维持平衡,插入和删除时完全不需要旋转
- DAVL 树的高度最多可以达到约 2log n,比同规模的红黑树还要高
答案
A A. 红黑树的平衡要求更宽松,插入删除时旋转更少,适合写操作较多的场景
解析
AVL 树要求左右子树高度差不超过 1,查找略快,但插入删除可能要多次旋转。红黑树只保证最长路径不超过最短路径的两倍,高度上限约 2log n,调整代价更低。所以 Java 的 TreeMap、HashMap 的树化桶以及 Linux 的进程调度器(CFS,6.6 起换成 EEVDF)都用红黑树。红黑树调整时同样需要旋转。