1. 从一次排行榜查找到底为什么变慢说起二叉树分类到底在解决什么问题刚入行那会儿我对数据结构的理解基本停留在考试层面。完全二叉树、满二叉树、平衡二叉树、二叉搜索树、红黑树这几个名词我背得滚瓜烂熟但真到了写代码的时候脑子里只有一句话用二叉树存不就完了吗。直到我做了一个玩家积分排行榜的功能才被现实狠狠教育了一次。最初的实现用的是最朴素的二叉搜索树数据量小的时候查一个玩家积分几百微秒后来玩家数量涨到几十万而且新玩家都是按注册时间递增插入的查询延迟一下子飙到了几十毫秒。问题就出在树退化成了一条链表而这一切的根因是我从来没有真正分清楚这几种二叉树各自在解决什么问题。数据结构里所谓的二叉树分类本质上不是在做名词辨析而是在回答一个工程问题这棵树长成什么形状才能让查找、插入、删除这些操作的代价可控。一棵形状失控的树会让你所有的算法都白搭而不同的分类对应的是不同维度的形状约束。完全二叉树和满二叉树描述的是树的填充密度平衡二叉树描述的是左右子树高度差是否受控二叉搜索树描述的是节点之间的大小关系红黑树则是用一种更宽松的平衡换取更少的调整代价。它们不是并列的五个孤立概念而是从存储、有序、效率三个角度对同一类结构的不同刻画。我用一句话先给这五种树各贴一个标签方便你建立第一印象树类型一句话定位主要服务的目标满二叉树每一层都塞满没有空缺结构规整便于理论分析完全二叉树只在最后一层最右侧有空缺数组存储、堆结构平衡二叉树左右子树高度差不超过1保证查找效率不退化二叉搜索树左小右大的有序结构有序查找与动态集合红黑树用颜色约束近似平衡工程中高效的动态有序表这张表建议你先扫一眼后面每一节我都会展开讲它们到底怎么来的、为什么要这么定义。你会慢慢发现这些定义不是拍脑袋想出来的每一个约束背后都对应着一类具体场景的痛点和代价权衡。1.1 五种树的共性都逃不开从根到一个节点的路径这个核心不管这棵树被定义成什么形状所有二叉树都有一个绕不开的基本事实访问任意一个节点必须从根节点沿着某条唯一路径走过去。这意味着树的深度直接决定了单次访问要走多少步。一棵有 n 个节点的树如果长得极不平衡深度接近 n那访问最底下的节点就要走 n 步如果长得匀称深度接近 log n同样一次访问只需要十几步就能搞定。当 n 是几十万甚至上百万的时候这个差距就是几百倍。所以你看满二叉树、完全二叉树、平衡二叉树、红黑树它们表面上的定义五花八门骨子里其实都在回答同一句话我怎么约束树的形状才能把深度压下去。唯一有点异类的是二叉搜索树它关心的是节点的相对大小关系并不直接约束形状。但也正因为它只管有序、不管形状才有了后来用平衡二叉树和红黑树去给它补课的故事。理解了这层关系你在选择用哪种树的时候就不会再犯迷糊。1.2 两类截然不同的需求存储密度优先还是查找效率优先实际项目里选哪种树往往取决于你更在意哪一头。如果你要做的是一个堆优先队列那完全二叉树是天然的选择因为它能用数组紧凑地存储父节点和子节点之间靠下标就能互相换算连指针都省了。如果你要做的是一个有序映射比如按键排序的配置表、数据库索引那你更在意的是查找效率这时候二叉搜索树是基础平衡二叉树或红黑树是加固方案。把需求先分成存储密度优先和查找效率优先两类你就能快速缩小候选范围。完全二叉树和满二叉树偏向存储平衡二叉树、红黑树偏向查找而二叉搜索树介于两者之间是一切的起点。下面几节我会沿着这个思路逐个把它们的定义、原理和实现讲透。2. 满二叉树和完全二叉树的边界数组存储为什么偏爱它们这两个概念是最容易混淆的一对也是面试里被问得最多的。它们看起来都跟树的形状是否规整有关但判定的严格程度完全不同。满二叉树是处处都满完全二叉树是只差最后一层右侧一点。理解这个差别关键在于想清楚它们各自要服务什么场景。满二叉树更多是为了理论上的简洁而完全二叉树则是为了一个非常实际的目标让树可以被数组完美地装下不浪费一个格子。我们平时用指针实现的二叉树每个节点都要存两个指针内存开销不小而且在堆这种高频操作的结构里指针跳转还会拖慢速度。完全二叉树正好有一个漂亮的数学性质可以让父节点和子节点的位置用下标直接算出来于是堆和很多优先队列的底层实现都建立在它之上。这也是为什么每次讲二叉树老师总要先讲完全二叉树的原因它不只是一个分类名词而是数组实现树结构的理论基础。2.1 满二叉树每一个内部节点都长满了两个孩子满二叉树的定义很直白一棵二叉树如果每一个内部节点都有两个子节点并且所有叶子节点都在同一层那它就是满二叉树。换个更好记的说法就是每一层都被节点填满没有任何一个位置是空缺的。比如深度为 1 的满二叉树只有一个根节点深度为 2 的有 3 个节点深度为 3 的有 7 个深度为 4 的有 15 个。规律很明显深度为 h 的满二叉树节点总数是 2^h − 1。这个公式不是记下来应付考试的它背后有个很直观的推理。第 1 层最多 1 个节点第 2 层最多 2 个第 3 层最多 4 个第 k 层最多 2^(k−1) 个。把这些层的最大值全加起来就是一个等比数列求和1 2 4 ... 2^(h−1) 2^h − 1。满二叉树就是把这个每层最大值全部取满的结果所以节点数必然是这个数。理解了这个推导你以后看到深度为 10 的满二叉树有多少节点这种问题直接 2^10 − 1 1023不用去死记。实际工程里严格意义上的满二叉树其实不常见因为节点总数必须恰好是 2^h − 1随机的增删很容易就破坏这个条件。它更多是作为一个理想参照物存在用来分析最优情况下的树高和复杂度。所以你不用纠结怎么在工作中用满二叉树而应该把它当成一把尺子用来衡量其他树到底长得有多好。2.2 完全二叉树只允许最后一层的最右侧有空缺完全二叉树的定义比满二叉树宽松一点点除了最后一层其他每一层都被节点填满而且最后一层的节点全部靠左排列中间不能有空洞。注意这里的措辞靠左排列和中间不能有空洞是关键。第 h−1 层必须满第 h 层的节点从左往右连续排一旦某个位置空了它右边就不能再有节点。满二叉树其实也是完全二叉树因为它的最后一层本来就没有空缺。反过来不成立完全二叉树不一定是满二叉树。这两个定义的关系可以用一句话记牢满二叉树是每层都满完全二叉树是最多只差最后一层的右边一点。判定一棵树是不是完全二叉树最常用的方法是按层序遍历也就是 BFS把所有节点依次编号如果在遇到第一个空节点之后又遇到了非空节点那它就不是完全二叉树。我刚开始学的时候老是把完全和满搞反觉得完全听起来更严格。后来我给自己编了个记忆法完全二叉树的完全指的是尽可能完全它允许最后一点缺角满二叉树的满才是真的一个都不能少。你可以顺着这个感觉记比死记定义牢靠得多。2.3 数组存储的数学映射父节点和子节点靠下标互相找完全二叉树最大的价值是它能用数组紧凑存储而不浪费空间。约定数组从下标 1 开始存放很多教材和实现为了方便都这么做那么对于下标为 i 的节点它和父节点、子节点的关系是这样父节点下标i / 2向下取整左孩子下标2 i右孩子下标2 i 1这套映射的推导其实很朴素。按层序遍历的顺序给节点编号根是 1它的左孩子是 2、右孩子是 3节点 2 的左孩子是 4、右孩子是 5节点 3 的左孩子是 6、右孩子是 7。你会发现每一层的起始编号都是 2 的幂次所以孩子编号和父编号之间正好差一个 2 倍关系。因为完全二叉树不会在中间留空洞所以按层序编号之后编号是连续的数组里不会有空占位被浪费掉这正是它能用下标直接寻址的前提。对比一下用指针的二叉树每个节点除了存数据还要存两个指针64 位系统下光指针就是 16 字节而且访问子节点要靠解引用跳来跳去对缓存不友好。堆排序之所以快很大一部分原因就是它用数组存完全二叉树父子寻址就是一次乘加运算缓存命中率也高。这就是形状规整带来的实实在在的性能收益。// 以最大堆为例完全二叉树用数组存下标从 1 开始 int heap[100005]; int size 0; void push(int value) { heap[size] value; int i size; // 向上调整和父节点比较父节点下标是 i/2 while (i 1 heap[i] heap[i / 2]) { swap(heap[i], heap[i / 2]); i i / 2; } } void pop() { heap[1] heap[size--]; int i 1; // 向下调整和较大的那个孩子交换 while (i * 2 size) { int child i * 2; if (child 1 size heap[child 1] heap[child]) { child; } if (heap[i] heap[child]) break; swap(heap[i], heap[child]); i child; } }上面这段代码你可以直接拿去当堆的模板注意它完全没有用到指针全靠i/2、2*i、2*i1这三个下标运算完成父子定位。这就是完全二叉树在工程里最典型的落地方式。写堆的时候如果下标从 0 开始公式要改成父节点(i-1)/2、左孩子2*i1、右孩子2*i2两者都有人用我建议你选定一种并且写注释避免自己在调试的时候算错下标。提示很多二叉树的运行时错误比如数组越界、空指针解引用都源于下标边界算错。用数组实现时务必确认 size 的判断条件向上调整要检查i 1向下调整要检查i * 2 size少一个等号就可能越界。2.4 手动判定完全二叉树的实操写法判定完全二叉树是个高频面试题思路就是用层序遍历一旦遇到空节点就把后面所有节点都标记为应该为空如果又冒出非空节点直接返回假。这里有个细节坑普通的层序遍历遇到空节点就跳过导致你无法区分最后一层的正常空缺和中间的空洞。所以正确做法是把空节点也入队遇到空节点后开始检查后续是否还有非空节点。bool isComplete(TreeNode* root) { if (!root) return true; queueTreeNode* q; q.push(root); bool seenEmpty false; // 是否已经遇到过空节点 while (!q.empty()) { TreeNode* node q.front(); q.pop(); if (!node) { seenEmpty true; // 标记进入只允许空的阶段 continue; } if (seenEmpty) return false; // 空节点之后又出现非空判定失败 q.push(node-left); // 空孩子也要入队这是关键 q.push(node-right); } return true; }我踩过的一个坑是一开始为了省事只在孩子非空时才入队结果中间有空洞的树也被判成了完全二叉树。后来加上空孩子也入队这个动作判定才正确。这个坑看起来小但面试时如果写错了基本就凉了所以建议你亲手敲一遍跑几组含空洞的用例验证。至于满二叉树的判定更简单先算出树高 h再数节点总数是不是 2^h − 1两个条件同时满足即可。3. 二叉搜索树有序性带来的便利与退化成链表的隐患讲完形状规整的两种树我们换一个角度。二叉搜索树BST关心的不是形状而是节点之间的大小关系。它给出了一个非常优雅的约定对任意一个节点它左子树里所有节点的值都小于它右子树里所有节点的值都大于它。靠着这个约定查找一个值就变成了从根开始不断比较、选择往左还是往右的过程每一步都能砍掉一半左右的候选范围。听起来很美好但这里埋着一个几乎所有初学者都会踩的坑那就是它只在长得匀称时才高效一旦插入顺序不巧它会立刻退化成一条链表。我当年做排行榜那个功能就是把玩家按注册时间递增的顺序一个一个插入 BST 的。递增插入意味着每一个新值都比之前所有值大于是每次都只能往右走、挂成右孩子树就长成了一条向右延伸的链。这时候查找最老注册的玩家要从根一路走到最末端复杂度直接从 O(log n) 掉到 O(n)。这个教训让我明白光有有序是不够的还得管住形状平衡二叉树和红黑树就是为了补上这一块。3.1 中序遍历有序BST 最核心也最实用的性质BST 有一个非常漂亮的性质对一棵二叉搜索树做中序遍历左、根、右得到的序列一定是严格递增的。这个性质既能用来验证一棵树是不是合法 BST也是很多算法题的突破口比如求第 k 小的元素、把 BST 转换成一个排序链表本质上都是利用中序有序这一条。推理一下为什么成立。中序遍历的顺序是先走左子树再访问根最后走右子树。而 BST 的定义保证了左子树所有值小于根、右子树所有值大于根。递归下去左子树的中序序列也递增右子树的中序序列也递增把它拼起来就是左子树递增序列 根 右子树递增序列整体依然递增。这条推理链条你可以自己拿一棵小树画一遍比如插入 5、3、8、1、4画出来中序就是 1、3、4、5、8一定是排好序的。利用这个性质验证 BST 的时候有个常见陷阱不能只检查节点是否大于左孩子、小于右孩子因为这样漏掉了祖先节点的约束。比如根是 10它的右孩子是 1515 的左孩子是 6虽然 6 小于 15、且 15 在 10 的右边但 6 出现在 10 的右子树里违反了右子树所有值都大于根的规定。正确的做法是中序遍历一遍看是否严格递增或者递归时把上下界传下去。// 用中序递增性质验证 BST记录前一个访问的值 bool isValidBST(TreeNode* root) { long long prev LLONG_MIN; return inorder(root, prev); } bool inorder(TreeNode* node, long long prev) { if (!node) return true; if (!inorder(node-left, prev)) return false; if (node-val prev) return false; // 必须严格大于前驱 prev node-val; if (!inorder(node-right, prev)) return false; return true; }3.2 查找与插入的复杂度为什么期望是 O(log n)在理想情况下也就是树长得比较匀称时BST 的查找复杂度是 O(log n)。这个结论怎么来的每次比较要么往左走、要么往右走等于把当前的搜索范围缩掉一半走的步数就是树的深度而一棵有 n 个节点的平衡树深度约等于 log₂n。比如 100 万个节点深度大约只有 20 层最多比 20 次就能找到目标这个速度相当可观。插入的过程和查找几乎一样先按大小关系找到应该挂载的空位置然后把新节点接上去。复杂度同样是 O(log n)因为走的路就是一次查找路径。但所有这些O(log n)都有一个前提树是平衡的。如果树的深度退化到了 n那查找和插入就变成 O(n)和遍历一遍数组没有任何区别。这也是为什么单纯的 BST 在工程里很少被直接使用它更像是后面几种平衡结构的理论原型。我一般会跟新手这么解释BST 就像一本按字母排序的电话簿你翻的时候一次跳一半很快能找到人但如果这本电话簿不是按顺序排的而是一条一条按录入时间接上去的那你只能从头翻到尾。BST 给你的是排序规则但没保证排序得匀称这两件事是分开的。3.3 有序插入导致的退化我踩过的那个坑回到开头我遇到的那个问题。玩家数据是按注册时间递增到达的每个新玩家的 ID 都比前一个大。BST 插入时新值比根大就往右结果就是每次都在最右端新增一个右孩子树从根一路向右延伸深度等于节点数量。几十万玩家树就有几十万层查找任何一个玩家都得走几十万步慢是必然的。这个现象叫退化。它提醒我们一个容易忽略的事实数据结构的性能往往取决于数据本身的分布和到达顺序而不是结构名字听起来高不高级。为了解决这个问题人们发明了能自动调整形状的树其中最基础的是 AVL 平衡二叉树工业界用得更多的是红黑树。它们的共同思路都是在插入或删除之后如果发现树不够匀称就通过局部调整让它重新匀称起来。顺便说一句判断一棵树是否退化一个直观办法是看它的最大深度。如果深度远大于 log₂n那就说明它歪了。很多语言的标准库并不会暴露底层树的深度但你可以自己写个小测试构造递增或递减序列插入然后测量深度实验一遍比看书印象深得多。3.4 删除节点的三种情况真正考验理解的地方BST 的删除是它最麻烦的操作因为你删掉一个节点后还要保持左小右大的秩序。分三种情况处理要删的节点是叶子直接删掉只有一个孩子用那个孩子顶替它的位置有两个孩子情况最复杂。对于有两个孩子的节点通常的做法是找它右子树里的最小节点也就是中序后继或者左子树里的最大节点替代被删节点的位置然后再把这个后继节点从原来的位置删掉。为什么用中序后继因为中序序列里一个节点的直接后继就是它右子树里最小的那个。用后继值去填补被删的位置既保证了左边的都比它小也保证了右边的都比它大秩序不会乱。这里我用代码把逻辑写清楚你可以对照着看TreeNode* deleteNode(TreeNode* root, int key) { if (!root) return nullptr; if (key root-val) { root-left deleteNode(root-left, key); } else if (key root-val) { root-right deleteNode(root-right, key); } else { // 找到了要删除的节点 if (!root-left) return root-right; // 只有右孩子或没有孩子 if (!root-right) return root-left; // 只有左孩子 // 有两个孩子找右子树最小节点中序后继 TreeNode* succ root-right; while (succ-left) succ succ-left; root-val succ-val; root-right deleteNode(root-right, succ-val); } return root; }我最初总是把第三种情况写成直接删掉被删节点结果整棵树的顺序全乱了。记住一句口诀两个孩子的删除本质是找个替代品再删掉替代品原来的位置。替代品可以是右子树最小值也可以是左子树最大值选哪个都行但选了就要连贯地把它从原位置删除否则会留下重复值。这个细节非常容易被漏掉。4. 平衡二叉树 AVL旋转操作背后的补偿机制既然 BST 会因为插入顺序而退化最直接的对策就是给它加一条形状约束任何节点的左右子树高度差都不能超过 1。满足这个条件的二叉搜索树就叫平衡二叉树AVL 树。这条约束保证了树的深度始终维持在 O(log n) 量级从而让查找、插入、删除都稳定高效。代价是每次操作后可能要做调整而调整的手段就是我们常说的旋转。很多人一听旋转就觉得晕其实它背后的动机非常简单理解透了就不容易忘。AVL 树是为了纪念两位发明者 Adelson-Velsky 和 Landis 命名的它是最早被提出的自平衡二叉搜索树。理解它的关键不是死记四种旋转的名字而是想清楚一句话旋转是一种不破坏中序顺序的局部重构。只要这一条立住了四种旋转该怎么转、转完为什么还合法都能自己推出来。4.1 平衡因子用一个数字衡量树歪没歪AVL 给每个节点定义一个平衡因子等于左子树高度减去右子树高度。平衡因子的取值只允许是 -1、0、1 三种分别代表右略高左右齐平左略高。一旦某个节点的平衡因子变成 -2 或 2说明这个位置失衡了必须调整。之所以把阈值定在 1是因为再大一点树高就无法保证在 log n 量级了。这个阈值的选择有点像走钢丝的容差太松了树会越走越歪太紧了每次操作都要大动干戈1 是一个经过验证的平衡点。实际实现时我们不会每次都重新算子树高度那样太浪费。常用做法是在节点里额外维护一个高度字段插入或删除后自底向上更新高度并检查平衡因子。这点和怎么算高度的直觉不太一样很多人第一反应是写个函数递归算高度但那会让每次插入都变成 O(n log n) 甚至更差。记住自平衡树的核心优化之一就是维护而不是重算这个思想在红黑树、B 树里都一样。4.2 四种旋转LL、RR、LR、RL失衡的情况按插入位置相对于失衡节点的方向分成四种。假设失衡节点叫 A插入发生在 A 的左子树的左侧叫 LL发生在左子树的右侧叫 LR发生在右子树的右侧叫 RR发生在右子树的左侧叫 RL。LL 和 RR 各做一次单旋转就能修复LR 和 RL 需要两次旋转先对子节点转再对 A 转。拿 LL 举例A 的左孩子叫 BB 的左子树增高导致 A 失衡。修复办法是以 B 为轴把 A 向右旋转下去变成 B 的右孩子同时把 B 原来的右子树挂到 A 的左孩子位置上。为什么要做这一挂接因为 B 原来的右子树值介于 B 和 A 之间旋转后必须给它找个合法位置挂到 A 的左边刚好满足左小右大。这就是不破坏中序顺序的具体体现。RR 是镜像操作向左旋转。LR 稍微绕一点插入发生在 A 的左孩子的右子树里。直接单旋解决不了得先把 B 的右孩子 C 转上来对 B 做一次左旋变成 LL 形态再对 A 做一次右旋。RL 同理镜像。我建议你自己画图推一遍或者拿三五个节点手动插入触发失衡把旋转过程画出来。光看文字记四种名字考完就忘亲手画一次能记很久。4.3 旋转的本质一次合法的局部腾挪很多人把旋转当成黑魔法其实它就是一个非常朴素的局部操作。想象你有一串按大小排好的节点旋转做的事情只是改变它们之间的父子归属但保持从左到右的读取顺序不变。换句话说旋转就是在不改变中序遍历结果的前提下让树重新长匀称。理解这一点之后你会发现旋转的次数和规模都是受控的每次插入最多引发一次失衡因为插入只让某一侧高度加 1所以最多一次调整但删除可能引发沿途多个节点失衡需要自底向上连续修复。这个差异也是面试常问的点很多人只记得插入最多旋一次却不知道删除可能要旋 O(log n) 次。原因是删除会让某个子树高度减 1这个变矮的信号会向上传递可能一路触发多个节点的平衡因子越界。4.4 AVL 的代价查询快但写操作维护成本高AVL 的平衡条件很严格好处是树高非常接近理论最小值查询性能极佳。但代价是每次插入或删除后为了维持这种严格平衡旋转和高度更新的频率偏高。如果你的场景是读多写少AVL 非常合适比如一份很少变动、但被频繁查询的字典。可如果是读写都频繁的场景AVL 的维护开销就会变得明显这时候工业界更倾向用红黑树因为它放宽了平衡条件牺牲一点查询效率换来了更少的调整。我在实际项目里很少直接手写 AVL除非是明确知道数据只读或者极少更新。更多时候会选择语言标准库里现成的有序容器它们底层大多是红黑树。但这不代表 AVL 不重要它是理解自平衡这个概念的最佳入口四种旋转的逻辑、平衡因子的维护方式几乎是所有平衡树的共同基础。学懂了 AVL再看红黑树会轻松很多。5. 红黑树用近似平衡换取工程上的划算红黑树是工业界最受欢迎的平衡二叉搜索树很多语言的有序映射底层都用它。它和 AVL 的最大区别在于AVL 追求的是严格平衡红黑树追求的是近似平衡。它通过给每个节点染上红或黑两种颜色并规定一套颜色规则来保证从根到任意叶子的路径长度不会相差太远。这个不会太远具体是多少最长的路径最多是最短路径的两倍整棵树的高度依然控制在 O(log n)。虽然比 AVL 稍微高一点但换来的是插入和删除时调整次数的大幅减少。为什么工程界偏爱这种稍微差一点但维护更省事的方案因为真实系统里写操作的频率往往不比读低每次写都做大量旋转累积起来是很大的开销。红黑树用颜色约束替代了严格的高度差约束让大部分插入删除只需要改几个颜色就能修复只有少数情况才需要旋转。这是一种典型的工程取舍不追求理论最优只追求综合成本最低。理解了这个出发点再去背红黑树的性质就不会觉得那些规则是凭空冒出来的。5.1 五条性质逐条拆解每一条都有它的作用红黑树的经典定义有五条每个节点要么是红色要么是黑色根节点必须是黑色所有叶子节点这里指空节点 NIL都是黑色红色节点的两个子节点必须是黑色也就是不能有连续的红色节点从任意节点出发到它所有后代叶子节点的路径上黑色节点数量相同。这五条里第 4 条和第 5 条是真正起约束作用的。第 4 条不能红红相连限制了红色节点不能扎堆出现第 5 条黑高相同保证了无论走哪条路径黑色节点数一致。把这两条合起来看红色节点最多只能在黑色节点之间插空出现所以最长路径红黑交替最多是最短路径全黑的两倍。这就是红黑树高度受控的核心逻辑。剩下的三条都是为了让边界情况处理起来更简单、更统一。比如根必须是黑是为了让黑高相同从一开始就有个稳定基准空叶子算黑是为了让从根到叶子的黑节点数这个计数在叶子处能整齐收尾。这些性质不是随便定的每一条都是为了简化调整算法的判断分支。当你自己尝试实现一遍红黑树就会强烈体会到这一点。5.2 插入修复三种情况与变色优先的策略新插入的节点默认染成红色因为染红不会破坏黑高相同这条性质插入前所有路径黑高一致插入一个红节点不改变黑节点计数但可能违反不能红红相连。所以插入后的修复核心就是处理当前节点和父节点都是红这个冲突。修复分几种情况。如果叔叔节点父节点的兄弟是红色那好办把父节点和叔叔都染黑、祖父染红然后把矛盾上移到祖父节点继续处理。这就是变色修复步骤少、代价低是红黑树常见的处理路径。如果叔叔节点是黑色或者不存在就得靠旋转了分左旋、右旋以及左右双旋、右左双旋几种最后重新染色保证性质恢复。旋转情况又根据当前节点是父节点的左孩子还是右孩子区分。我这里不打算把红黑树的插入修复十二种细分情况全列出来因为死记硬背意义不大。你可以抓住一条主线优先尝试变色变色解决不了再旋转。因为变色的操作代价低且不需要改变树的结构能用简单手段解决就先用简单的这就是红黑树减少调整设计思想的直接体现。真要手写实现的时候建议对着一份可靠的参考资料把每种情况的触发条件和处理动作做成表逐条调试。5.3 为什么近似平衡在工程里够用很多人会问红黑树明明比 AVL 矮不了多少为什么还要忍受它不够严格的平衡答案在成本对比上。假设插入一个节点AVL 可能需要一路更新高度、触发旋转红黑树很多时候只是改两个颜色就完事了。在一次操作里这点差别不大但在每天几亿次写入的系统里累积的差异非常可观。而且从查询成本看红黑树的高度虽然是 AVL 的一到两倍但它们都是 O(log n)在 n 达到百万级时树高一个是 20 左右一个是 40 左右差这十几步在现代 CPU 上微乎其微。换句话说红黑树在查询上损失的这点效率远远小于它在写操作上省下的调整成本。这就是它能成为工业标准的原因。一想到工程上够用就行这句话括号里的东西你就都能理解了。另外红黑树还有一个隐性优势它的调整逻辑更稳定、更容易实现成高效的迭代代码。AVL 的删除需要连续修复多个节点红黑树虽然也有复杂情况但整体提供了更统一的处理框架这让标准库作者更愿意基于它做长期维护。你想标准库要用几十年稳定和可维护性当然优先于理论上的极致。5.4 实际使用时不用手写用好语言内置的有序容器绝大多数情况下你不需要自己从零写一棵红黑树。C 的std::map/std::set、Java 的TreeMap/TreeSet、很多语言里的有序字典底层都是红黑树。你真正需要掌握的是什么场景该用它以及它的操作复杂度是多少。比如你要维护一个始终有序、能按范围查询、且增删频繁的集合那就是它的主场。但也别把它当万金油。如果你的数据量很小或者查询不要求有序用哈希表反而更快因为哈希表的平均查找是 O(1)红黑树是 O(log n)。红黑树的价值在于有序性 动态操作两件事同时要。选型的判断标准很简单你需要有序遍历或者范围查询吗需要就考虑红黑树不需要就先想哈希表。这个判断我在实际开发里用了很多年几乎没出过错。注意红黑树保证的是有序和 O(log n) 的操作但它不保证第 k 小能直接取到那需要额外维护子树大小字段。有些库提供 order statistic 的扩展但标准容器一般没有遇到这类需求要自己动手或者在选型阶段就考虑清楚。6. 五种二叉树怎么选一张对比表和几条实操判断讲了这么多定义和原理最后落到一个最实际的问题上面对一个具体需求到底该选哪种树。我把这五种树的关键属性整理成一张表方便你横向对比。注意这里的复杂度都是指操作时的不是建树时的。树类型是否有序查找复杂度插入/删除复杂度主要用途满二叉树不特别约定取决于深度取决于实现理论参照、完全树的特例完全二叉树不特别约定O(1) 数组寻址堆调整为 O(log n)堆、优先队列平衡二叉树 AVL是O(log n)O(log n)调整较多读多写少的有序表二叉搜索树 BST是平均 O(log n)最坏 O(n)平均 O(log n)最坏 O(n)有序结构入门、简单场景红黑树是O(log n)O(log n)调整较少通用有序映射、标准库看这张表你会立刻发现选型的关键就两个问题要不要有序以及读写比例大概如何。需要有序且读写均衡红黑树优先需要有序但几乎只读AVL 可以考虑需要的是优先级队列而不是有序映射那完全二叉树堆就是正解只是想要个有序的动态集合、对最坏情况不敏感那 BST 也许就够了。6.1 按场景选树三个常见例子对照举三个我实际遇到过的场景。第一实现一个任务优先级调度每次取优先级最高的任务这是堆的经典场景用完全二叉树数组实现取堆顶 O(1)调整 O(log n)。第二统计一份日志里每个接口被调用的次数并且偶尔需要按接口名排序输出这是键值统计 有序遍历用红黑树比如std::map刚好。第三做一个小型通讯录数据量几百条查找不频繁用最朴素的 BST 完全够用没必要上红黑树。从这三个例子你能看出一个规律数据规模和操作频率决定投入的复杂度。数据小、操作少简单结构就够过度设计反而增加代码维护成本。数据大、读写频繁才值得上自平衡结构。我见过不少新人一上来就想写红黑树结果项目里根本没有合适的场景纯属自己给自己加活儿。6.2 几个高频误解一次澄清第一个误解是把平衡二叉树当成一个具体的树名。其实它是一个类别AVL、红黑树都是平衡的二叉搜索树只是平衡的严格程度不同。第二个误解是以为红黑树不算是平衡二叉树严格来说它属于平衡二叉搜索树的一种只是平衡条件更宽松。第三个误解是认为完全二叉树和满二叉树是更好的树实际上它们和是否有序无关用途完全不同堆用完全二叉树只是因为它适合数组存不是因为它在查找上有优势。第四个误解也是最常见的以为平衡了查找就是 O(log n)。这个结论对查找成立对空间不成立。平衡树为了维持结构通常要额外存高度或颜色字段还有指针开销内存占用比数组或哈希表高。所以涉及内存敏感的场景也要把这部分成本算进去。选结构不能只看时间复杂度空间和实现复杂度同样是决策的一部分。6.3 面试和刷题里这些点最容易被追问从面试的角度看这几种树是常客。最高频的问题包括判断一棵树是不是完全二叉树、是不是合法 BST、求树的深度、实现 BST 的增删查、解释 AVL 旋转、说出红黑树的性质和作用。这些我在前面都给了思路和代码你可以拿去当模板练习。一个建议是不要只背概念动手实现一遍特别是旋转和删除手写完一遍印象会完全不同。刷题时还有一种题值得专门练就是不同的二叉搜索树这类计数问题。它考察的是你能否看出 BST 的结构数量和卡特兰数的关系。另外最优二叉搜索树涉及动态规划是在给定了每个键的查找概率后构造一棵期望查找代价最小的 BST和自平衡是两回事前者优化的是访问概率后者优化的是最坏深度别搞混了。这两个概念常被放在一起考把它们的区别想清楚很重要。我自己在准备相关面试的时候会把每种树的关键性质和最坏情况写在一张纸上考前扫一遍。尤其是BST 最坏 O(n)、红黑树最坏 O(log n)这种反差点以及AVL 查询快、红黑树写入省这种取舍几乎每次都会被问到把因果讲清楚比背结论有用得多。6.4 我踩过的坑和给你的几条实用建议最后说点我自己踩过或者见过别人踩的坑。第一用递归实现 BST 相关操作时务必想清楚返回什么、怎么接回去。删除节点时如果忘了把修改后的子树重新挂回父节点就会丢节点。第二写堆的时候下标从 0 还是从 1 开始一定要在开头就定好并统一混用是最容易出错的。第三判定完全二叉树时空孩子也必须入队否则中间的空洞检测不到。第四理解平衡树时别急着背旋转公式先把中序遍历不变这条原则立住旋转就能自己推。再补一条关于性能的经验不要凭直觉判断该用哪种结构用数据量和操作频率做个粗算。比如 n 是 10 万log₂n 约等于 17红黑树和 AVL 在查询上差的那点深度基本可以忽略重点就该看写操作频率谁调整少选谁。反过来 n 只有几百什么树都无所谓代码简单清晰才是第一位的。很多性能焦虑其实在数据量面前是不成立的先看量级再谈优化这是我这些年最实在的体会。 从满二叉树到红黑树：五种二叉树分类、旋转与选型指南
1. 从一次排行榜查找到底为什么变慢说起二叉树分类到底在解决什么问题刚入行那会儿我对数据结构的理解基本停留在考试层面。完全二叉树、满二叉树、平衡二叉树、二叉搜索树、红黑树这几个名词我背得滚瓜烂熟但真到了写代码的时候脑子里只有一句话用二叉树存不就完了吗。直到我做了一个玩家积分排行榜的功能才被现实狠狠教育了一次。最初的实现用的是最朴素的二叉搜索树数据量小的时候查一个玩家积分几百微秒后来玩家数量涨到几十万而且新玩家都是按注册时间递增插入的查询延迟一下子飙到了几十毫秒。问题就出在树退化成了一条链表而这一切的根因是我从来没有真正分清楚这几种二叉树各自在解决什么问题。数据结构里所谓的二叉树分类本质上不是在做名词辨析而是在回答一个工程问题这棵树长成什么形状才能让查找、插入、删除这些操作的代价可控。一棵形状失控的树会让你所有的算法都白搭而不同的分类对应的是不同维度的形状约束。完全二叉树和满二叉树描述的是树的填充密度平衡二叉树描述的是左右子树高度差是否受控二叉搜索树描述的是节点之间的大小关系红黑树则是用一种更宽松的平衡换取更少的调整代价。它们不是并列的五个孤立概念而是从存储、有序、效率三个角度对同一类结构的不同刻画。我用一句话先给这五种树各贴一个标签方便你建立第一印象树类型一句话定位主要服务的目标满二叉树每一层都塞满没有空缺结构规整便于理论分析完全二叉树只在最后一层最右侧有空缺数组存储、堆结构平衡二叉树左右子树高度差不超过1保证查找效率不退化二叉搜索树左小右大的有序结构有序查找与动态集合红黑树用颜色约束近似平衡工程中高效的动态有序表这张表建议你先扫一眼后面每一节我都会展开讲它们到底怎么来的、为什么要这么定义。你会慢慢发现这些定义不是拍脑袋想出来的每一个约束背后都对应着一类具体场景的痛点和代价权衡。1.1 五种树的共性都逃不开从根到一个节点的路径这个核心不管这棵树被定义成什么形状所有二叉树都有一个绕不开的基本事实访问任意一个节点必须从根节点沿着某条唯一路径走过去。这意味着树的深度直接决定了单次访问要走多少步。一棵有 n 个节点的树如果长得极不平衡深度接近 n那访问最底下的节点就要走 n 步如果长得匀称深度接近 log n同样一次访问只需要十几步就能搞定。当 n 是几十万甚至上百万的时候这个差距就是几百倍。所以你看满二叉树、完全二叉树、平衡二叉树、红黑树它们表面上的定义五花八门骨子里其实都在回答同一句话我怎么约束树的形状才能把深度压下去。唯一有点异类的是二叉搜索树它关心的是节点的相对大小关系并不直接约束形状。但也正因为它只管有序、不管形状才有了后来用平衡二叉树和红黑树去给它补课的故事。理解了这层关系你在选择用哪种树的时候就不会再犯迷糊。1.2 两类截然不同的需求存储密度优先还是查找效率优先实际项目里选哪种树往往取决于你更在意哪一头。如果你要做的是一个堆优先队列那完全二叉树是天然的选择因为它能用数组紧凑地存储父节点和子节点之间靠下标就能互相换算连指针都省了。如果你要做的是一个有序映射比如按键排序的配置表、数据库索引那你更在意的是查找效率这时候二叉搜索树是基础平衡二叉树或红黑树是加固方案。把需求先分成存储密度优先和查找效率优先两类你就能快速缩小候选范围。完全二叉树和满二叉树偏向存储平衡二叉树、红黑树偏向查找而二叉搜索树介于两者之间是一切的起点。下面几节我会沿着这个思路逐个把它们的定义、原理和实现讲透。2. 满二叉树和完全二叉树的边界数组存储为什么偏爱它们这两个概念是最容易混淆的一对也是面试里被问得最多的。它们看起来都跟树的形状是否规整有关但判定的严格程度完全不同。满二叉树是处处都满完全二叉树是只差最后一层右侧一点。理解这个差别关键在于想清楚它们各自要服务什么场景。满二叉树更多是为了理论上的简洁而完全二叉树则是为了一个非常实际的目标让树可以被数组完美地装下不浪费一个格子。我们平时用指针实现的二叉树每个节点都要存两个指针内存开销不小而且在堆这种高频操作的结构里指针跳转还会拖慢速度。完全二叉树正好有一个漂亮的数学性质可以让父节点和子节点的位置用下标直接算出来于是堆和很多优先队列的底层实现都建立在它之上。这也是为什么每次讲二叉树老师总要先讲完全二叉树的原因它不只是一个分类名词而是数组实现树结构的理论基础。2.1 满二叉树每一个内部节点都长满了两个孩子满二叉树的定义很直白一棵二叉树如果每一个内部节点都有两个子节点并且所有叶子节点都在同一层那它就是满二叉树。换个更好记的说法就是每一层都被节点填满没有任何一个位置是空缺的。比如深度为 1 的满二叉树只有一个根节点深度为 2 的有 3 个节点深度为 3 的有 7 个深度为 4 的有 15 个。规律很明显深度为 h 的满二叉树节点总数是 2^h − 1。这个公式不是记下来应付考试的它背后有个很直观的推理。第 1 层最多 1 个节点第 2 层最多 2 个第 3 层最多 4 个第 k 层最多 2^(k−1) 个。把这些层的最大值全加起来就是一个等比数列求和1 2 4 ... 2^(h−1) 2^h − 1。满二叉树就是把这个每层最大值全部取满的结果所以节点数必然是这个数。理解了这个推导你以后看到深度为 10 的满二叉树有多少节点这种问题直接 2^10 − 1 1023不用去死记。实际工程里严格意义上的满二叉树其实不常见因为节点总数必须恰好是 2^h − 1随机的增删很容易就破坏这个条件。它更多是作为一个理想参照物存在用来分析最优情况下的树高和复杂度。所以你不用纠结怎么在工作中用满二叉树而应该把它当成一把尺子用来衡量其他树到底长得有多好。2.2 完全二叉树只允许最后一层的最右侧有空缺完全二叉树的定义比满二叉树宽松一点点除了最后一层其他每一层都被节点填满而且最后一层的节点全部靠左排列中间不能有空洞。注意这里的措辞靠左排列和中间不能有空洞是关键。第 h−1 层必须满第 h 层的节点从左往右连续排一旦某个位置空了它右边就不能再有节点。满二叉树其实也是完全二叉树因为它的最后一层本来就没有空缺。反过来不成立完全二叉树不一定是满二叉树。这两个定义的关系可以用一句话记牢满二叉树是每层都满完全二叉树是最多只差最后一层的右边一点。判定一棵树是不是完全二叉树最常用的方法是按层序遍历也就是 BFS把所有节点依次编号如果在遇到第一个空节点之后又遇到了非空节点那它就不是完全二叉树。我刚开始学的时候老是把完全和满搞反觉得完全听起来更严格。后来我给自己编了个记忆法完全二叉树的完全指的是尽可能完全它允许最后一点缺角满二叉树的满才是真的一个都不能少。你可以顺着这个感觉记比死记定义牢靠得多。2.3 数组存储的数学映射父节点和子节点靠下标互相找完全二叉树最大的价值是它能用数组紧凑存储而不浪费空间。约定数组从下标 1 开始存放很多教材和实现为了方便都这么做那么对于下标为 i 的节点它和父节点、子节点的关系是这样父节点下标i / 2向下取整左孩子下标2 i右孩子下标2 i 1这套映射的推导其实很朴素。按层序遍历的顺序给节点编号根是 1它的左孩子是 2、右孩子是 3节点 2 的左孩子是 4、右孩子是 5节点 3 的左孩子是 6、右孩子是 7。你会发现每一层的起始编号都是 2 的幂次所以孩子编号和父编号之间正好差一个 2 倍关系。因为完全二叉树不会在中间留空洞所以按层序编号之后编号是连续的数组里不会有空占位被浪费掉这正是它能用下标直接寻址的前提。对比一下用指针的二叉树每个节点除了存数据还要存两个指针64 位系统下光指针就是 16 字节而且访问子节点要靠解引用跳来跳去对缓存不友好。堆排序之所以快很大一部分原因就是它用数组存完全二叉树父子寻址就是一次乘加运算缓存命中率也高。这就是形状规整带来的实实在在的性能收益。// 以最大堆为例完全二叉树用数组存下标从 1 开始 int heap[100005]; int size 0; void push(int value) { heap[size] value; int i size; // 向上调整和父节点比较父节点下标是 i/2 while (i 1 heap[i] heap[i / 2]) { swap(heap[i], heap[i / 2]); i i / 2; } } void pop() { heap[1] heap[size--]; int i 1; // 向下调整和较大的那个孩子交换 while (i * 2 size) { int child i * 2; if (child 1 size heap[child 1] heap[child]) { child; } if (heap[i] heap[child]) break; swap(heap[i], heap[child]); i child; } }上面这段代码你可以直接拿去当堆的模板注意它完全没有用到指针全靠i/2、2*i、2*i1这三个下标运算完成父子定位。这就是完全二叉树在工程里最典型的落地方式。写堆的时候如果下标从 0 开始公式要改成父节点(i-1)/2、左孩子2*i1、右孩子2*i2两者都有人用我建议你选定一种并且写注释避免自己在调试的时候算错下标。提示很多二叉树的运行时错误比如数组越界、空指针解引用都源于下标边界算错。用数组实现时务必确认 size 的判断条件向上调整要检查i 1向下调整要检查i * 2 size少一个等号就可能越界。2.4 手动判定完全二叉树的实操写法判定完全二叉树是个高频面试题思路就是用层序遍历一旦遇到空节点就把后面所有节点都标记为应该为空如果又冒出非空节点直接返回假。这里有个细节坑普通的层序遍历遇到空节点就跳过导致你无法区分最后一层的正常空缺和中间的空洞。所以正确做法是把空节点也入队遇到空节点后开始检查后续是否还有非空节点。bool isComplete(TreeNode* root) { if (!root) return true; queueTreeNode* q; q.push(root); bool seenEmpty false; // 是否已经遇到过空节点 while (!q.empty()) { TreeNode* node q.front(); q.pop(); if (!node) { seenEmpty true; // 标记进入只允许空的阶段 continue; } if (seenEmpty) return false; // 空节点之后又出现非空判定失败 q.push(node-left); // 空孩子也要入队这是关键 q.push(node-right); } return true; }我踩过的一个坑是一开始为了省事只在孩子非空时才入队结果中间有空洞的树也被判成了完全二叉树。后来加上空孩子也入队这个动作判定才正确。这个坑看起来小但面试时如果写错了基本就凉了所以建议你亲手敲一遍跑几组含空洞的用例验证。至于满二叉树的判定更简单先算出树高 h再数节点总数是不是 2^h − 1两个条件同时满足即可。3. 二叉搜索树有序性带来的便利与退化成链表的隐患讲完形状规整的两种树我们换一个角度。二叉搜索树BST关心的不是形状而是节点之间的大小关系。它给出了一个非常优雅的约定对任意一个节点它左子树里所有节点的值都小于它右子树里所有节点的值都大于它。靠着这个约定查找一个值就变成了从根开始不断比较、选择往左还是往右的过程每一步都能砍掉一半左右的候选范围。听起来很美好但这里埋着一个几乎所有初学者都会踩的坑那就是它只在长得匀称时才高效一旦插入顺序不巧它会立刻退化成一条链表。我当年做排行榜那个功能就是把玩家按注册时间递增的顺序一个一个插入 BST 的。递增插入意味着每一个新值都比之前所有值大于是每次都只能往右走、挂成右孩子树就长成了一条向右延伸的链。这时候查找最老注册的玩家要从根一路走到最末端复杂度直接从 O(log n) 掉到 O(n)。这个教训让我明白光有有序是不够的还得管住形状平衡二叉树和红黑树就是为了补上这一块。3.1 中序遍历有序BST 最核心也最实用的性质BST 有一个非常漂亮的性质对一棵二叉搜索树做中序遍历左、根、右得到的序列一定是严格递增的。这个性质既能用来验证一棵树是不是合法 BST也是很多算法题的突破口比如求第 k 小的元素、把 BST 转换成一个排序链表本质上都是利用中序有序这一条。推理一下为什么成立。中序遍历的顺序是先走左子树再访问根最后走右子树。而 BST 的定义保证了左子树所有值小于根、右子树所有值大于根。递归下去左子树的中序序列也递增右子树的中序序列也递增把它拼起来就是左子树递增序列 根 右子树递增序列整体依然递增。这条推理链条你可以自己拿一棵小树画一遍比如插入 5、3、8、1、4画出来中序就是 1、3、4、5、8一定是排好序的。利用这个性质验证 BST 的时候有个常见陷阱不能只检查节点是否大于左孩子、小于右孩子因为这样漏掉了祖先节点的约束。比如根是 10它的右孩子是 1515 的左孩子是 6虽然 6 小于 15、且 15 在 10 的右边但 6 出现在 10 的右子树里违反了右子树所有值都大于根的规定。正确的做法是中序遍历一遍看是否严格递增或者递归时把上下界传下去。// 用中序递增性质验证 BST记录前一个访问的值 bool isValidBST(TreeNode* root) { long long prev LLONG_MIN; return inorder(root, prev); } bool inorder(TreeNode* node, long long prev) { if (!node) return true; if (!inorder(node-left, prev)) return false; if (node-val prev) return false; // 必须严格大于前驱 prev node-val; if (!inorder(node-right, prev)) return false; return true; }3.2 查找与插入的复杂度为什么期望是 O(log n)在理想情况下也就是树长得比较匀称时BST 的查找复杂度是 O(log n)。这个结论怎么来的每次比较要么往左走、要么往右走等于把当前的搜索范围缩掉一半走的步数就是树的深度而一棵有 n 个节点的平衡树深度约等于 log₂n。比如 100 万个节点深度大约只有 20 层最多比 20 次就能找到目标这个速度相当可观。插入的过程和查找几乎一样先按大小关系找到应该挂载的空位置然后把新节点接上去。复杂度同样是 O(log n)因为走的路就是一次查找路径。但所有这些O(log n)都有一个前提树是平衡的。如果树的深度退化到了 n那查找和插入就变成 O(n)和遍历一遍数组没有任何区别。这也是为什么单纯的 BST 在工程里很少被直接使用它更像是后面几种平衡结构的理论原型。我一般会跟新手这么解释BST 就像一本按字母排序的电话簿你翻的时候一次跳一半很快能找到人但如果这本电话簿不是按顺序排的而是一条一条按录入时间接上去的那你只能从头翻到尾。BST 给你的是排序规则但没保证排序得匀称这两件事是分开的。3.3 有序插入导致的退化我踩过的那个坑回到开头我遇到的那个问题。玩家数据是按注册时间递增到达的每个新玩家的 ID 都比前一个大。BST 插入时新值比根大就往右结果就是每次都在最右端新增一个右孩子树从根一路向右延伸深度等于节点数量。几十万玩家树就有几十万层查找任何一个玩家都得走几十万步慢是必然的。这个现象叫退化。它提醒我们一个容易忽略的事实数据结构的性能往往取决于数据本身的分布和到达顺序而不是结构名字听起来高不高级。为了解决这个问题人们发明了能自动调整形状的树其中最基础的是 AVL 平衡二叉树工业界用得更多的是红黑树。它们的共同思路都是在插入或删除之后如果发现树不够匀称就通过局部调整让它重新匀称起来。顺便说一句判断一棵树是否退化一个直观办法是看它的最大深度。如果深度远大于 log₂n那就说明它歪了。很多语言的标准库并不会暴露底层树的深度但你可以自己写个小测试构造递增或递减序列插入然后测量深度实验一遍比看书印象深得多。3.4 删除节点的三种情况真正考验理解的地方BST 的删除是它最麻烦的操作因为你删掉一个节点后还要保持左小右大的秩序。分三种情况处理要删的节点是叶子直接删掉只有一个孩子用那个孩子顶替它的位置有两个孩子情况最复杂。对于有两个孩子的节点通常的做法是找它右子树里的最小节点也就是中序后继或者左子树里的最大节点替代被删节点的位置然后再把这个后继节点从原来的位置删掉。为什么用中序后继因为中序序列里一个节点的直接后继就是它右子树里最小的那个。用后继值去填补被删的位置既保证了左边的都比它小也保证了右边的都比它大秩序不会乱。这里我用代码把逻辑写清楚你可以对照着看TreeNode* deleteNode(TreeNode* root, int key) { if (!root) return nullptr; if (key root-val) { root-left deleteNode(root-left, key); } else if (key root-val) { root-right deleteNode(root-right, key); } else { // 找到了要删除的节点 if (!root-left) return root-right; // 只有右孩子或没有孩子 if (!root-right) return root-left; // 只有左孩子 // 有两个孩子找右子树最小节点中序后继 TreeNode* succ root-right; while (succ-left) succ succ-left; root-val succ-val; root-right deleteNode(root-right, succ-val); } return root; }我最初总是把第三种情况写成直接删掉被删节点结果整棵树的顺序全乱了。记住一句口诀两个孩子的删除本质是找个替代品再删掉替代品原来的位置。替代品可以是右子树最小值也可以是左子树最大值选哪个都行但选了就要连贯地把它从原位置删除否则会留下重复值。这个细节非常容易被漏掉。4. 平衡二叉树 AVL旋转操作背后的补偿机制既然 BST 会因为插入顺序而退化最直接的对策就是给它加一条形状约束任何节点的左右子树高度差都不能超过 1。满足这个条件的二叉搜索树就叫平衡二叉树AVL 树。这条约束保证了树的深度始终维持在 O(log n) 量级从而让查找、插入、删除都稳定高效。代价是每次操作后可能要做调整而调整的手段就是我们常说的旋转。很多人一听旋转就觉得晕其实它背后的动机非常简单理解透了就不容易忘。AVL 树是为了纪念两位发明者 Adelson-Velsky 和 Landis 命名的它是最早被提出的自平衡二叉搜索树。理解它的关键不是死记四种旋转的名字而是想清楚一句话旋转是一种不破坏中序顺序的局部重构。只要这一条立住了四种旋转该怎么转、转完为什么还合法都能自己推出来。4.1 平衡因子用一个数字衡量树歪没歪AVL 给每个节点定义一个平衡因子等于左子树高度减去右子树高度。平衡因子的取值只允许是 -1、0、1 三种分别代表右略高左右齐平左略高。一旦某个节点的平衡因子变成 -2 或 2说明这个位置失衡了必须调整。之所以把阈值定在 1是因为再大一点树高就无法保证在 log n 量级了。这个阈值的选择有点像走钢丝的容差太松了树会越走越歪太紧了每次操作都要大动干戈1 是一个经过验证的平衡点。实际实现时我们不会每次都重新算子树高度那样太浪费。常用做法是在节点里额外维护一个高度字段插入或删除后自底向上更新高度并检查平衡因子。这点和怎么算高度的直觉不太一样很多人第一反应是写个函数递归算高度但那会让每次插入都变成 O(n log n) 甚至更差。记住自平衡树的核心优化之一就是维护而不是重算这个思想在红黑树、B 树里都一样。4.2 四种旋转LL、RR、LR、RL失衡的情况按插入位置相对于失衡节点的方向分成四种。假设失衡节点叫 A插入发生在 A 的左子树的左侧叫 LL发生在左子树的右侧叫 LR发生在右子树的右侧叫 RR发生在右子树的左侧叫 RL。LL 和 RR 各做一次单旋转就能修复LR 和 RL 需要两次旋转先对子节点转再对 A 转。拿 LL 举例A 的左孩子叫 BB 的左子树增高导致 A 失衡。修复办法是以 B 为轴把 A 向右旋转下去变成 B 的右孩子同时把 B 原来的右子树挂到 A 的左孩子位置上。为什么要做这一挂接因为 B 原来的右子树值介于 B 和 A 之间旋转后必须给它找个合法位置挂到 A 的左边刚好满足左小右大。这就是不破坏中序顺序的具体体现。RR 是镜像操作向左旋转。LR 稍微绕一点插入发生在 A 的左孩子的右子树里。直接单旋解决不了得先把 B 的右孩子 C 转上来对 B 做一次左旋变成 LL 形态再对 A 做一次右旋。RL 同理镜像。我建议你自己画图推一遍或者拿三五个节点手动插入触发失衡把旋转过程画出来。光看文字记四种名字考完就忘亲手画一次能记很久。4.3 旋转的本质一次合法的局部腾挪很多人把旋转当成黑魔法其实它就是一个非常朴素的局部操作。想象你有一串按大小排好的节点旋转做的事情只是改变它们之间的父子归属但保持从左到右的读取顺序不变。换句话说旋转就是在不改变中序遍历结果的前提下让树重新长匀称。理解这一点之后你会发现旋转的次数和规模都是受控的每次插入最多引发一次失衡因为插入只让某一侧高度加 1所以最多一次调整但删除可能引发沿途多个节点失衡需要自底向上连续修复。这个差异也是面试常问的点很多人只记得插入最多旋一次却不知道删除可能要旋 O(log n) 次。原因是删除会让某个子树高度减 1这个变矮的信号会向上传递可能一路触发多个节点的平衡因子越界。4.4 AVL 的代价查询快但写操作维护成本高AVL 的平衡条件很严格好处是树高非常接近理论最小值查询性能极佳。但代价是每次插入或删除后为了维持这种严格平衡旋转和高度更新的频率偏高。如果你的场景是读多写少AVL 非常合适比如一份很少变动、但被频繁查询的字典。可如果是读写都频繁的场景AVL 的维护开销就会变得明显这时候工业界更倾向用红黑树因为它放宽了平衡条件牺牲一点查询效率换来了更少的调整。我在实际项目里很少直接手写 AVL除非是明确知道数据只读或者极少更新。更多时候会选择语言标准库里现成的有序容器它们底层大多是红黑树。但这不代表 AVL 不重要它是理解自平衡这个概念的最佳入口四种旋转的逻辑、平衡因子的维护方式几乎是所有平衡树的共同基础。学懂了 AVL再看红黑树会轻松很多。5. 红黑树用近似平衡换取工程上的划算红黑树是工业界最受欢迎的平衡二叉搜索树很多语言的有序映射底层都用它。它和 AVL 的最大区别在于AVL 追求的是严格平衡红黑树追求的是近似平衡。它通过给每个节点染上红或黑两种颜色并规定一套颜色规则来保证从根到任意叶子的路径长度不会相差太远。这个不会太远具体是多少最长的路径最多是最短路径的两倍整棵树的高度依然控制在 O(log n)。虽然比 AVL 稍微高一点但换来的是插入和删除时调整次数的大幅减少。为什么工程界偏爱这种稍微差一点但维护更省事的方案因为真实系统里写操作的频率往往不比读低每次写都做大量旋转累积起来是很大的开销。红黑树用颜色约束替代了严格的高度差约束让大部分插入删除只需要改几个颜色就能修复只有少数情况才需要旋转。这是一种典型的工程取舍不追求理论最优只追求综合成本最低。理解了这个出发点再去背红黑树的性质就不会觉得那些规则是凭空冒出来的。5.1 五条性质逐条拆解每一条都有它的作用红黑树的经典定义有五条每个节点要么是红色要么是黑色根节点必须是黑色所有叶子节点这里指空节点 NIL都是黑色红色节点的两个子节点必须是黑色也就是不能有连续的红色节点从任意节点出发到它所有后代叶子节点的路径上黑色节点数量相同。这五条里第 4 条和第 5 条是真正起约束作用的。第 4 条不能红红相连限制了红色节点不能扎堆出现第 5 条黑高相同保证了无论走哪条路径黑色节点数一致。把这两条合起来看红色节点最多只能在黑色节点之间插空出现所以最长路径红黑交替最多是最短路径全黑的两倍。这就是红黑树高度受控的核心逻辑。剩下的三条都是为了让边界情况处理起来更简单、更统一。比如根必须是黑是为了让黑高相同从一开始就有个稳定基准空叶子算黑是为了让从根到叶子的黑节点数这个计数在叶子处能整齐收尾。这些性质不是随便定的每一条都是为了简化调整算法的判断分支。当你自己尝试实现一遍红黑树就会强烈体会到这一点。5.2 插入修复三种情况与变色优先的策略新插入的节点默认染成红色因为染红不会破坏黑高相同这条性质插入前所有路径黑高一致插入一个红节点不改变黑节点计数但可能违反不能红红相连。所以插入后的修复核心就是处理当前节点和父节点都是红这个冲突。修复分几种情况。如果叔叔节点父节点的兄弟是红色那好办把父节点和叔叔都染黑、祖父染红然后把矛盾上移到祖父节点继续处理。这就是变色修复步骤少、代价低是红黑树常见的处理路径。如果叔叔节点是黑色或者不存在就得靠旋转了分左旋、右旋以及左右双旋、右左双旋几种最后重新染色保证性质恢复。旋转情况又根据当前节点是父节点的左孩子还是右孩子区分。我这里不打算把红黑树的插入修复十二种细分情况全列出来因为死记硬背意义不大。你可以抓住一条主线优先尝试变色变色解决不了再旋转。因为变色的操作代价低且不需要改变树的结构能用简单手段解决就先用简单的这就是红黑树减少调整设计思想的直接体现。真要手写实现的时候建议对着一份可靠的参考资料把每种情况的触发条件和处理动作做成表逐条调试。5.3 为什么近似平衡在工程里够用很多人会问红黑树明明比 AVL 矮不了多少为什么还要忍受它不够严格的平衡答案在成本对比上。假设插入一个节点AVL 可能需要一路更新高度、触发旋转红黑树很多时候只是改两个颜色就完事了。在一次操作里这点差别不大但在每天几亿次写入的系统里累积的差异非常可观。而且从查询成本看红黑树的高度虽然是 AVL 的一到两倍但它们都是 O(log n)在 n 达到百万级时树高一个是 20 左右一个是 40 左右差这十几步在现代 CPU 上微乎其微。换句话说红黑树在查询上损失的这点效率远远小于它在写操作上省下的调整成本。这就是它能成为工业标准的原因。一想到工程上够用就行这句话括号里的东西你就都能理解了。另外红黑树还有一个隐性优势它的调整逻辑更稳定、更容易实现成高效的迭代代码。AVL 的删除需要连续修复多个节点红黑树虽然也有复杂情况但整体提供了更统一的处理框架这让标准库作者更愿意基于它做长期维护。你想标准库要用几十年稳定和可维护性当然优先于理论上的极致。5.4 实际使用时不用手写用好语言内置的有序容器绝大多数情况下你不需要自己从零写一棵红黑树。C 的std::map/std::set、Java 的TreeMap/TreeSet、很多语言里的有序字典底层都是红黑树。你真正需要掌握的是什么场景该用它以及它的操作复杂度是多少。比如你要维护一个始终有序、能按范围查询、且增删频繁的集合那就是它的主场。但也别把它当万金油。如果你的数据量很小或者查询不要求有序用哈希表反而更快因为哈希表的平均查找是 O(1)红黑树是 O(log n)。红黑树的价值在于有序性 动态操作两件事同时要。选型的判断标准很简单你需要有序遍历或者范围查询吗需要就考虑红黑树不需要就先想哈希表。这个判断我在实际开发里用了很多年几乎没出过错。注意红黑树保证的是有序和 O(log n) 的操作但它不保证第 k 小能直接取到那需要额外维护子树大小字段。有些库提供 order statistic 的扩展但标准容器一般没有遇到这类需求要自己动手或者在选型阶段就考虑清楚。6. 五种二叉树怎么选一张对比表和几条实操判断讲了这么多定义和原理最后落到一个最实际的问题上面对一个具体需求到底该选哪种树。我把这五种树的关键属性整理成一张表方便你横向对比。注意这里的复杂度都是指操作时的不是建树时的。树类型是否有序查找复杂度插入/删除复杂度主要用途满二叉树不特别约定取决于深度取决于实现理论参照、完全树的特例完全二叉树不特别约定O(1) 数组寻址堆调整为 O(log n)堆、优先队列平衡二叉树 AVL是O(log n)O(log n)调整较多读多写少的有序表二叉搜索树 BST是平均 O(log n)最坏 O(n)平均 O(log n)最坏 O(n)有序结构入门、简单场景红黑树是O(log n)O(log n)调整较少通用有序映射、标准库看这张表你会立刻发现选型的关键就两个问题要不要有序以及读写比例大概如何。需要有序且读写均衡红黑树优先需要有序但几乎只读AVL 可以考虑需要的是优先级队列而不是有序映射那完全二叉树堆就是正解只是想要个有序的动态集合、对最坏情况不敏感那 BST 也许就够了。6.1 按场景选树三个常见例子对照举三个我实际遇到过的场景。第一实现一个任务优先级调度每次取优先级最高的任务这是堆的经典场景用完全二叉树数组实现取堆顶 O(1)调整 O(log n)。第二统计一份日志里每个接口被调用的次数并且偶尔需要按接口名排序输出这是键值统计 有序遍历用红黑树比如std::map刚好。第三做一个小型通讯录数据量几百条查找不频繁用最朴素的 BST 完全够用没必要上红黑树。从这三个例子你能看出一个规律数据规模和操作频率决定投入的复杂度。数据小、操作少简单结构就够过度设计反而增加代码维护成本。数据大、读写频繁才值得上自平衡结构。我见过不少新人一上来就想写红黑树结果项目里根本没有合适的场景纯属自己给自己加活儿。6.2 几个高频误解一次澄清第一个误解是把平衡二叉树当成一个具体的树名。其实它是一个类别AVL、红黑树都是平衡的二叉搜索树只是平衡的严格程度不同。第二个误解是以为红黑树不算是平衡二叉树严格来说它属于平衡二叉搜索树的一种只是平衡条件更宽松。第三个误解是认为完全二叉树和满二叉树是更好的树实际上它们和是否有序无关用途完全不同堆用完全二叉树只是因为它适合数组存不是因为它在查找上有优势。第四个误解也是最常见的以为平衡了查找就是 O(log n)。这个结论对查找成立对空间不成立。平衡树为了维持结构通常要额外存高度或颜色字段还有指针开销内存占用比数组或哈希表高。所以涉及内存敏感的场景也要把这部分成本算进去。选结构不能只看时间复杂度空间和实现复杂度同样是决策的一部分。6.3 面试和刷题里这些点最容易被追问从面试的角度看这几种树是常客。最高频的问题包括判断一棵树是不是完全二叉树、是不是合法 BST、求树的深度、实现 BST 的增删查、解释 AVL 旋转、说出红黑树的性质和作用。这些我在前面都给了思路和代码你可以拿去当模板练习。一个建议是不要只背概念动手实现一遍特别是旋转和删除手写完一遍印象会完全不同。刷题时还有一种题值得专门练就是不同的二叉搜索树这类计数问题。它考察的是你能否看出 BST 的结构数量和卡特兰数的关系。另外最优二叉搜索树涉及动态规划是在给定了每个键的查找概率后构造一棵期望查找代价最小的 BST和自平衡是两回事前者优化的是访问概率后者优化的是最坏深度别搞混了。这两个概念常被放在一起考把它们的区别想清楚很重要。我自己在准备相关面试的时候会把每种树的关键性质和最坏情况写在一张纸上考前扫一遍。尤其是BST 最坏 O(n)、红黑树最坏 O(log n)这种反差点以及AVL 查询快、红黑树写入省这种取舍几乎每次都会被问到把因果讲清楚比背结论有用得多。6.4 我踩过的坑和给你的几条实用建议最后说点我自己踩过或者见过别人踩的坑。第一用递归实现 BST 相关操作时务必想清楚返回什么、怎么接回去。删除节点时如果忘了把修改后的子树重新挂回父节点就会丢节点。第二写堆的时候下标从 0 还是从 1 开始一定要在开头就定好并统一混用是最容易出错的。第三判定完全二叉树时空孩子也必须入队否则中间的空洞检测不到。第四理解平衡树时别急着背旋转公式先把中序遍历不变这条原则立住旋转就能自己推。再补一条关于性能的经验不要凭直觉判断该用哪种结构用数据量和操作频率做个粗算。比如 n 是 10 万log₂n 约等于 17红黑树和 AVL 在查询上差的那点深度基本可以忽略重点就该看写操作频率谁调整少选谁。反过来 n 只有几百什么树都无所谓代码简单清晰才是第一位的。很多性能焦虑其实在数据量面前是不成立的先看量级再谈优化这是我这些年最实在的体会。