一棵树怎么做到“自平衡还不太费力“？——红黑树的旋转与染色

一棵树怎么做到自平衡还不太费力——红黑树的旋转与染色408 · 数据结构45 分· 树。红黑树的五条性质、与 AVL 的取舍、旋转与染色是查找章节的高频选择题来源。先把一棵树插歪给你看假设你手写一棵普通的二叉查找树BST按1, 2, 3, 4, 5, 6, 7的顺序往里插。插完之后你会发现这棵树长得跟一条斜线没什么两样——查找第 7 个节点要走 7 步退化成了链表O(n)。问题出在哪BST 只管左小右大却不管树高。于是人们发明了各种自平衡二叉查找树AVL 树是最早的一批它要求左右子树高度差不超过 1把树压得足够矮代价是每次插入删除可能要多次旋转维护成本不低。红黑树Red-Black Tree走了另一条路不追求绝对最矮而是用一套染色规则保证树矮得足够快、维护还不贵。这篇文章就讲这套规则。五条性质一条都不能少一棵红黑树每个节点不是红就是黑同时满足每个节点要么是红色要么是黑色根节点是黑色每个叶子NIL 空节点是黑色红色节点的两个子节点必须是黑色不能出现连续两个红从任一节点到其每个叶子的所有路径上黑色节点数量相同这条最关键叫黑高一致。正是第 4、5 条逼着树保持大致平衡。可以证明树高 ≤ 2 log ⁡ 2 ( n 1 ) \text{树高} \le 2\log_2(n1)树高≤2log2​(n1)也就是说红黑树的最坏高度是2 log ⁡ ( n 1 ) 2\log(n1)2log(n1)查找、插入、删除都能保证O ( log ⁡ n ) O(\log n)O(logn)。虽然它没 AVL 那么矮AVL 约1.44 log ⁡ n 1.44\log n1.44logn但换来了更少的旋转次数——插入最多 2 次旋转删除最多 3 次比 AVL 的多次旋转省事得多。染色与旋转它平衡的两件工具红黑树维持平衡靠两个动作交替进行染色recolor把某个节点从红变黑或从黑变红用来调整黑高。旋转rotate和 AVL 一样分左旋和右旋用来调整树的结构。旋转不改变中序遍历顺序只改变父子关系——所以旋转后它仍是合法的 BST。插入一个新节点时惯例先把它染成红色这样不破坏第 5 条黑高一致然后看它的叔叔节点父节点的兄弟是什么颜色分几种情况修补情形 1叔叔是红色 → 父、叔变黑祖父变红把问题上移到祖父继续处理 情形 2叔叔是黑色且新节点是父的外侧 → 旋转父节点 重新染色一次搞定 情形 3叔叔是黑色且新节点是父的内侧 → 先旋转到外侧再按情形 2 处理细节不必全背抓住一句话就够“红红冲突就转一转、染一染黑高始终不乱。”删除更复杂要处理少了一个黑的情况但思想和插入一样都是破坏哪条性质就针对性修补哪条。红黑树 vs AVL到底选谁这是面试最爱问的对比题答案其实藏在读写比例里对比项AVL 树红黑树平衡要求严格高度差 ≤ 1宽松红黑规则树高更矮≈ 1.44 log n略高≤ 2 log n查找更快稍慢插入/删除旋转多、更慢旋转少、更快典型用途查多写少的场景写多、读写均衡的场景一句话AVL 是查得极致红黑树是写起来省心。所以 Linux 的进程调度、Java 的TreeMap、C 的std::map这些插删频繁的场合清一色选了红黑树。一个会出在选择题里的细节408 选择题常考红黑树的性质判断题比如一棵红黑树从根到叶的最长路径最多是最短路径的几倍根据性质 4不能连续两个红和性质 5黑高一致最长路径是红黑红黑交替最短路径是全黑所以最长最多是2 × 黑高 黑高 2 倍 \frac{2 \times \text{黑高}}{\text{黑高}} 2 \text{ 倍}黑高2×黑高​2倍答案2 倍。这就是大致平衡的量化含义——它没有 AVL 那么紧AVL 最多约 1.44 倍但换来的是插入删除的廉价。回到开头那棵插歪的树红黑树用两条染色规则 几次旋转就换来了任何时刻最坏O ( log ⁡ n ) O(\log n)O(logn)“的承诺。它不追求绝对最矮只追求矮得够用、维护还便宜”。下次再在源码里撞见rb_insert、rb_erase这样的函数名你会知道——那团红黑相间里藏着一套用约束换效率的平衡术。红黑树、AVL 是数据结构查找一章的常客想系统跟学B站【408实验室】的《数据结构》里有从 BST 到红黑树的完整推导。