红黑树和 AVL 树有什么区别?查询与插入性能怎么比较?
下面是一段模拟面试对话。
🧑💻 面试官:红黑树和 AVL 都是平衡树,区别在哪里?
🙋♂️ 我:AVL 查询更快,红黑树插入删除更快。
🧑💻 面试官:这个结论对每种数据和实现都成立吗?两者究竟保持什么约束?
🙋♂️ 我:AVL 限制左右高度差,红黑树通过颜色规则限制路径长度。
🧑💻 面试官:红黑树没有把每个节点左右高度调得一样,为什么仍然不会退化成一条链?
先讲「怎样限制树高」,再讲维护代价。只背快慢口号,解释不了复杂度,也做不了选型。
面试速答(60 秒版)
AVL 和红黑树都是自平衡二叉搜索树,查找、插入和删除的最坏时间复杂度都可以保持 O(log n)。
AVL 要求每个节点左右子树高度差不超过 1。它的高度约束更严格,更新以后可能需要沿路径检查高度,并通过旋转恢复平衡。AVL 说明。
红黑树通过颜色与黑高等规则约束路径,允许更宽松的形状。它不要求每个节点左右高度几乎一样,但仍能保证树高在对数范围内。
因此,AVL 的较紧高度可能减少查找中的节点访问,红黑树的更新维护方式可能适合频繁修改。不过,实际速度还受实现、缓存、比较成本和负载影响,不能直接保证哪一种在所有项目里更快。

知识点详解:先看顺序,再看平衡
两种树先遵守同一条搜索规则
假设存储一批不重复整数。对于每个节点,左子树键更小,右子树键更大。查找时比较当前键,再决定向左还是向右。
如果依次插入 1、2、3,却不调整结构,普通二叉搜索树可能变成一直向右的链。继续增加有序数据,查找就需要经过很多节点。
平衡的目的,是限制从根到叶的最长路径。它不是让所有节点有相同深度,也不是把左右节点数量保持完全一样。
实际容器允许重复键时,应另有明确规则;本文用唯一键解释结构。
AVL 直接限制每个节点的高度差
AVL 把左右子树高度差控制在 -1、0、1 之内。一次更新可能影响祖先高度,因此需要沿路径检查。
以依次插入 3、2、1 为例,原来的根 3 左侧过高。进行一次右旋以后,2 成为根,1、3 分别成为左右孩子,顺序仍然正确。
旋转不是交换节点的键。它调整父子连接,并保留中序遍历顺序。更复杂的形状可能需要组合旋转,不能看到右边高就永远只做一次左旋。
删除还可能让高度变化继续向上传播。因此,维护工作不仅包含旋转,也包含高度记录和祖先检查。

红黑树用路径约束保证高度
采用常见定义时,节点有红、黑两色,根为黑色,空叶节点按黑色处理;红节点不能有红孩子;从一个节点到其后代空叶的路径,黑节点数量相同。
最后这项通常叫黑高约束。没有连续红节点,意味着红节点不能无限塞进同一条路径;相同黑高又限制了各条路径的差别。
所以,红黑树允许左右高度不同,却仍有对数高度保证。面试时无需背出整段数学证明,但要说明颜色规则怎样限制最坏路径。
更新可能通过重新着色和旋转恢复规则。不同实现还有额外约定,例如左倾红黑树限制红链接方向;不能把这种额外约定当作所有红黑树共有定义。教材作者的左倾红黑树实现。

性能取舍需要把工作量说具体
查找沿路径进行比较。树更矮,可能少访问一些节点,但如果键比较或内存访问本身很贵,差距还会受其他因素影响。
更新则要完成搜索、插入或删除,并维护平衡。旋转只是其中一项,不能拿某次旋转少直接证明整个更新更快。
对内存有序集合,可以按真实读写比例、键类型和规模比较。如果数据放在磁盘页里,还要考虑 B+ 树等不同结构,不能把内存二叉树结论直接用到数据库索引。
验证平衡树,先检查不变量
每次更新以后,可以检查中序结果是否有序、节点是否丢失。AVL 再检查高度记录和左右差值;红黑树再检查红节点关系与黑高。
测试数据要包含递增、递减、随机插入和连续删除。先保证结构正确,再比较查找次数、分配和耗时。
没有跑过同一组负载,就先把理论上的差别讲清楚,不急着给出“谁一定更快”的结论。
面试官继续追问
平衡树是不是完全二叉树?
不是。完全二叉树强调节点按层靠左排列;这些搜索树强调键顺序和各自平衡约束,不要求同一种形状。
红黑树最长路径大致是最短路径的两倍,怎么理解?
在共同采用的黑叶计数约定下,两条路径黑节点数受约束;红节点不能连续,较长路径最多在黑节点之间夹入红节点。它不会无限拉长。
实际证明应统一高度和空叶计数定义,不能把“约两倍”用作任意可视化节点数的精确公式。
查询特别多,就一定选 AVL 吗?
可以把它纳入候选,但还要看可用库、更新负载、比较成本和内存局部性。没有实际比较时,只能说明理论约束,不能承诺吞吐收益。
面试速记卡
- 共同基础:二叉搜索顺序,最坏操作保持 O(log n)。
- AVL:每个节点左右高度差不超过 1。
- 红黑树:颜色关系与相同黑高限制路径。
- 旋转作用:改变连接,保留中序键顺序。
- 选型依据:维护成本与真实负载一起看,不背绝对快慢。
公司面试真题
真题根据求职者公开面经整理,题意经过概括,非逐字原话或公司官方题库;本文为 Sunday 的独立解析。
网易 · 游戏研发 · 原帖未明确批次
AVL 树和红黑树有什么区别?(题意整理)
网易互娱游戏研发面经+时间线 ↗
正文记录 3 月 27 日一面;原帖编辑于 2025-04-25字节跳动 · 后端 · 秋招
展开讲讲 AVL 树和红黑树。(题意整理)
字节-秋招-后端开发-二面 ↗
正文记录 9 月 10 日面试;原帖发布于 2025-09-13