2025年蓝桥杯第十六届省赛Python组出现了一道红黑树真题。拿到这个消息的时候很多群里的选手第一反应是“省赛考红黑树是不是离谱了点”。但看完题之后你会发现它其实比想象中温和——不是让你20分钟默写一本《算法导论》第13章而是把一个经典数据结构和竞赛经典操作结合起来考察。这篇文章我打算把这件事一次性讲透红黑树是什么、为什么2025年省考会考它、Python怎么在考场上写出能跑的插入删除修正代码、以及什么时候你其实根本不需要手写红黑树。不管你是已经在备赛的选手还是刚学完二叉树想进阶数据结构的人这篇文章给你一套能直接上手的思路和代码也给你几条踩过坑之后才知道的备赛经验。1. 2025年省赛这道题到底在考什么1.1 一个“压轴数据结构”出现在省赛的真实信号红黑树这东西往年更多出现在大厂面试题、高校课程作业、或者ACM/ICPC的进阶训练里。省赛阶段考红黑树确实少见。但2025年第十六届省赛真题里明确出现这个考点背后其实是近两年蓝桥杯命题难度持续抬升的信号。随便翻翻最近几届的题目就能感觉到以前省赛常见的“模拟贪心简单搜索”三板斧现在越来越频繁地让位于更复杂的数据结构题。Python组考红黑树还有一个很特殊的背景Python不像C那样自带map/set这种底层就是红黑树的容器。C选手遇到动态有序集合问题直接调std::set完事而Python选手没得调要么自己写一棵平衡树要么另想办法用堆、二分、甚至硬排序去凑。所以在Python组考这一点其实考的是“你能不能在没有现成容器的情况下用正确的结构把复杂度压下去”。另外注意一个信号如果题目只是一个裸的“实现红黑树”那考的是背诵能力没有区分度。省赛真题不太会这么出。更常见的组合是“动态插入删除查询前驱后继/中序遍历/验证红黑性质”这时候你是不是真的理解旋转和修正立马见分晓。1.2 拿到题目后的第一件事拆解考点我在备赛和带人刷题时反复强调拿到任何一题先干三件事看数据范围、看操作类型、看有没有“能替换的现成结构”。比如题目说n和m都在10^5量级那O(n^2)直接死O(n log n)才是目标如果题目是“动态向集合里插数、删数、查某个数的前驱后继”这明显就是平衡树的活。但如果题面只是“给定一组数建树后输出中序遍历”那它考的是建树过程和代码基本功不一定要把删除修正写满。还有一种情况很阴题目说是红黑树实际上那棵树初始就满足红黑性质然后执行若干插入最后让你验证“是否依然满足五条性质”。这种题重点不是让你写出标准红黑树而是考察你对性质的检查能力。你把每个节点颜色、黑色高度、连续红色问题搞明白也能拿不少分。所以拿到题先冷静别一看“红黑树”三个字就腿软。拆开考点再对策略这才是竞赛的基本素养。1.3 红黑树、Treap与AVL竞赛选手应该怎么选很多选手会纠结既然红黑树难写我是不是应该放弃去啃Treap或者AVL我的建议是分场景看。结构平衡方式插入/删除旋转次数代码量竞赛实用度AVL树严格平衡左右子树高度差≤1插入最多2次旋转删除最多O(log n)次中等查询多、结构不被频繁改时可用红黑树统计平衡最长路径不超过最短路径2倍插入最多2次旋转删除最多3次旋转较大理解后性能稳定但代码长Treap随机优先级保证期望平衡通过旋转维护堆性质短约60-80行竞赛中最推荐FHQ-Treap不旋转通过分裂合并维护平衡无旋转短支持区间操作强烈推荐红黑树的优势在于它是“教科书级”的平衡树也是很多语言底层容器的基础但竞赛现场手撕删除修正确实有风险。我的决策规律是如果题目明确指名红黑树那就老老实实写红黑树如果题目只是需要一个动态有序集合我优先用Treap因为它在期望意义下同样是O(log n)代码量却少一大截。不过这不妨碍你把红黑树彻底搞懂。搞懂红黑树之后你看Treap和AVL都是降维打击因为所有的平衡树核心动作都是“旋转调整”区别只是谁来触发旋转、旋转多少次。2. 看懂红黑树先看这五条性质和两种旋转2.1 五条性质红黑树的“宪法”红黑树本质是一棵二叉搜索树每个节点多存一个颜色字段然后强制满足以下五条性质每个节点要么是红色要么是黑色。根节点是黑色。每个叶子节点NIL是黑色。这里说的叶子不是普通的空指针而是哨兵节点。如果一个节点是红色那么它的两个子节点都是黑色。也就是说红色节点的父节点和子节点都不能是红色等价于树中不存在两个连续的红色节点。从任意节点出发到它所有后代叶子节点的路径上包含相同数量的黑色节点。这个数量也叫黑高black-height。性质2和性质5是红黑树“不那么容易歪掉”的根因。你可以想象每条路径的黑色节点数量是一把尺子所有路径必须量出一样的长度那么红色节点再多最长的路径也就是最短路径的两倍内因为红色节点不能连续出现而黑色节点数量又固定。这就是红黑树“统计平衡”的来源——它不要求左右子树完全等高只限制比例在2倍以内所以插入删除时的旋转次数才能被压住。性质3经常被初学者忽略。很多教材里NIL是指那些用来占位的空叶子节点它们都是黑色的。在实际代码里如果你用None表示空指针就必须在逻辑上把所有None当成黑色节点来处理。后面写代码时你会发现所有判断“某个孩子是否是红色”之前都要先确认它不是None否则直接访问color属性会炸AttributeError。2.2 左旋和右旋别怕就是换座位旋转是红黑树所有修正操作的原子动作。左旋和右旋是一对镜像操作目的是在不破坏二叉搜索树性质的前提下把某个子树的结构重新摆一摆。左旋的直观理解是这样的以节点x为支点让它的右孩子y上位x变成y的左孩子。y原来的左子树自然要挂到x的右边因为那棵子树里的所有值都介于x和y之间。右旋就是完全镜像的过程以y为支点让它的左孩子x上位y变成x的右孩子x原来的右子树挂到y的左边。这里的指针修改顺序非常关键。我先给出左旋和右旋的完整Python代码再逐行讲顺序class Node: __slots__ (val, color, left, right, parent) def __init__(self, val, colorred, leftNone, rightNone, parentNone): self.val val self.color color self.left left self.right right self.parent parent def left_rotate(root, x): y x.right # 1. x的右孩子指向y的左孩子 x.right y.left if y.left is not None: y.left.parent x # 2. y的父母指针指向x的父母 y.parent x.parent if x.parent is None: root y elif x x.parent.left: x.parent.left y else: x.parent.right y # 3. y的左孩子指向xx的父母指向y y.left x x.parent y return root def right_rotate(root, x): y x.left x.left y.right if y.right is not None: y.right.parent x y.parent x.parent if x.parent is None: root y elif x x.parent.right: x.parent.right y else: x.parent.left y y.right x x.parent y return root可以看到我先动了x和孩子之间的连接再动y和祖父之间的连接最后把x和y的关系焊死。这个顺序是我踩过很多坑之后总结出来的先处理子树的交接再处理祖先关系最后处理x和y自身。如果先改了y.parent-x.parent那么后续如果要用x.parent来判断x是在父节点的左还是右就必须在步骤2之前保存好原始的父亲引用。上面的代码每一层都重新检查x.parent逻辑上是安全的但写代码时一定要注意先后。还有一个我经常用的自查方法旋转操作之后整棵树的“中序遍历不变”。这既是旋转的核心性质也是你调试时最好的验证手段。如果你旋转完中序遍历顺序变了说明某个指针改错地方了。2.3 为什么插入的新节点一定要是红色的你现在知道五条性质了但可能有一个疑问插入新节点时为什么默认给它红色而不是黑色如果直接插入黑色性质5很可能被破坏——原本所有路径黑高相同你往一条路径上多加了一个黑节点这条路径的黑高就比别的路径大1全局修正会很麻烦。但如果插入红色唯一可能被破坏的是性质4万一父节点也是红色就会出现红红相邻。红红相邻的问题只涉及局部路径修正起来要比全局黑高失衡简单得多。这是典型的“把大问题拆成小问题”的思路。插入修正过程中我们始终维护一个不变量新节点x是红色的它和它的父节点都是红色。只要父节点红就一直向上处理。插入修正分为三大类情况以“叔叔节点”的颜色作为首要分支叔叔节点是红色把父节点和叔叔节点同时变黑祖父节点变红然后x上移到祖父节点继续循环。为什么能这样处理因为把父和叔变黑就把“红红冲突”拆掉了两条路径的黑高同时加1性质5不会破坏祖父变红是为了抵消下去因为它本来就该红的场合是它的父节点红继续递归即可。叔叔节点是黑色或NIL此时不能再靠变色解决问题必须旋转。先判断x是父节点的“内侧子节点”还是“外侧子节点”。内侧表示x和父节点、祖父节点形成折线形状比如父是左孩子、x是右孩子。这种要先转一次让它们变成直线再把父节点变黑、祖父变红最后对祖父旋转。如果x自己就是根节点直接把它涂黑结束。这几种情况我后面会给出完整代码但你现在需要记住的是“红看叔”插入修正的核心分歧点永远先看叔叔节点颜色红叔叔用变色黑叔叔用旋转。3. Python实现红黑树核心代码逐段拆解3.1 节点定义与NIL处理用None还是哨兵对象我在前面代码里用了slots来节省内存这在竞赛环境里是有意义的。Python的每个对象默认带一个__dict__字典属性一多内存开销非常难看红黑树节点数如果是10^5级别普通Node类的内存消耗会让你卡在MLE的边缘。slots__直接把属性列表固定下来省掉__dict速度也更快。至于NIL节点教科书里推荐用一个独立哨兵对象因为哨兵节点永远是黑色、左右孩子都指向自己。但在竞赛Python代码里我强烈建议直接用None原因很简单代码短、好写、不容易在构造函数里搞错引用。代价就是你在判断颜色时处处小心所有地方都要先判None再访问color。为了不出bug我习惯把所有“判断某节点是否为红色/黑色”的逻辑封装成两个小函数def is_red(node): return node is not None and node.color red def is_black(node): return node is None or node.color black如果你在代码里直接用node.color遇到None就是AttributeError用这两个函数封装后None自动按黑色节点处理逻辑干净很多。这也是竞赛代码里很值得养成的习惯。3.2 查找、中序遍历与前驱后继这些操作不改结构红黑树的查询操作和普通二叉搜索树完全一样不需要处理颜色。查找的迭代版本比递归版本稳妥因为Python递归深度默认只有1000而红黑树高度最坏是2log2(n1)n10^5时高度大约34其实递归也不会爆栈。但我仍然推荐迭代版本省去函数调用开销写起来也不难def search(root, val): cur root while cur is not None: if val cur.val: return cur elif val cur.val: cur cur.left else: cur cur.right return None中序遍历返回有序数组是验证树结构的好工具。注意所谓“红黑树中序遍历有序”只验证了BST性质不能验证颜色性质所以还需要专门的check函数。前驱和后继也可以直接按BST规则找不需要颜色操作。这些查询函数在竞赛中的用途非常大因为很多动态有序集合问题最终要输出就是这些信息。3.3 插入操作入口修正逐行说清楚插入操作分两步第一步按BST规则找到位置把新节点挂上去默认红色第二步调用insert_fix修正颜色。我把完整实现写在下面def insert(root, val): node Node(val, red) if root is None: node.color black return node cur root while True: if val cur.val: if cur.left is None: node.parent cur cur.left node break cur cur.left else: if cur.right is None: node.parent cur cur.right node break cur cur.right return insert_fix(root, node) def insert_fix(root, node): while node ! root and is_red(node.parent): parent node.parent grand parent.parent if parent grand.left: # 父节点是祖父的左孩子 uncle grand.right if is_red(uncle): # 情况1叔叔是红 parent.color black uncle.color black grand.color red node grand else: # 叔叔是黑 if node parent.right: # 情况2折线先转一次 node parent root left_rotate(root, node) parent node.parent grand parent.parent # 情况3直线变色后对祖父右旋 parent.color black grand.color red root right_rotate(root, grand) else: # 父节点是祖父的右孩子镜像对称 uncle grand.left if is_red(uncle): parent.color black uncle.color black grand.color red node grand else: if node parent.left: node parent root right_rotate(root, node) parent node.parent grand parent.parent parent.color black grand.color red root left_rotate(root, grand) if root is None: break root.color black return root这段代码里最关键的是修正循环的出口条件。我们一边修正一边把node往上移最终要么node到达根节点要么node.parent不再是红色循环自然结束。最后一行root.color black是兜底操作确保性质2永远成立。即使中途把根节点涂成红色最后也会强制变黑。我在赛前默写这段代码时有一个小技巧把“情况2先旋转再进入情况3”看成“先掰直再换位”。折线形状之所以要先转一次是因为如果直接对祖父旋转会破坏子树结构。你先对父节点旋转让折线变成直线这就回到了最简单的直线模式后面的“父变黑、祖父变红、对祖父旋转”就是标准套路了。3.4 删除操作比插入难在“缺黑”问题删除操作难在如果一个黑色节点被删掉了那么经过它的那条路径黑高一定减少1性质5全局失衡。插入修正解决的是“多了一个红”删除修正解决的是“少了一个黑”。我把删除实现分成两个核心模块把节点真正摘掉以及修复黑高缺失。先看摘节点的辅助函数def transplant(root, u, v): # 用v替换u的位置 if u.parent is None: root v elif u u.parent.left: u.parent.left v else: u.parent.right v if v is not None: v.parent u.parent return roottransplant就是裸的“树上换将”不管颜色。真正的删除函数要考虑三种情况节点没有左孩子、节点没有右孩子、节点有两个孩子。前两种直接把唯一的子树顶上来就行第三种要从右子树里找后继节点把后继的值“覆盖”到待删节点上然后转去删除后继节点这样真正被物理删除的节点最多只有一个孩子。def delete(root, val): node search(root, val) if node is None: return root original_color node.color parent node.parent if node.left is None: child node.right root transplant(root, node, child) elif node.right is None: child node.left root transplant(root, node, child) else: nxt node.right while nxt.left is not None: nxt nxt.left original_color nxt.color child nxt.right if nxt.parent node: if child is not None: child.parent nxt parent nxt else: parent nxt.parent root transplant(root, nxt, child) nxt.right node.right nxt.right.parent nxt root transplant(root, node, nxt) nxt.left node.left nxt.left.parent nxt nxt.color node.color if original_color black: root delete_fix(root, child, parent) return root注意我单独记录了parent因为child可能是None删除修正函数需要知道“这个可能缺黑的节点它现在的父节点是谁”。这非常关键很多人在写delete_fix时直接访问child.parent但child是None就直接炸了。而且当删除双子节点时原始node的颜色被nxt继承所以真正需要关心的是nxt原本的颜色如果nxt原本是红色顶多当它被删掉也不会影响黑高不需要修正这和我们用original_color判断的原理一致。删除修正函数里我们要处理的“问题节点”用node表示它可能是None也可能是一个黑色节点。我们一边把额外的一层黑色向上推一边通过旋转重新平衡def delete_fix(root, node, parent): while node ! root and is_black(node): if node parent.left: sib parent.right if is_red(sib): sib.color black parent.color red root left_rotate(root, parent) sib parent.right if is_black(sib.left) and is_black(sib.right): sib.color red node parent parent node.parent else: if is_black(sib.right): sib.left.color black sib.color red root right_rotate(root, sib) sib parent.right sib.color parent.color parent.color black sib.right.color black root left_rotate(root, parent) node root else: sib parent.left if is_red(sib): sib.color black parent.color red root right_rotate(root, parent) sib parent.left if is_black(sib.left) and is_black(sib.right): sib.color red node parent parent node.parent else: if is_black(sib.left): sib.right.color black sib.color red root left_rotate(root, sib) sib parent.left sib.color parent.color parent.color black sib.left.color black root right_rotate(root, parent) node root if node is not None: node.color black return root这里有一个很容易绕晕的地方node可能是None但代码里写了 node parent.left这能成立吗因为当node是None时只要parent.left恰好也是None这个表达式就为True逻辑上正好对应“缺失黑节点的孩子是左孩子”的场景如果parent.left不是None说明node实际在右孩子自然走else分支。这种写法是有点tricky的但竞赛里它非常实用。删除修正的四种情况我建议你用一个口诀记就是“黑兄弟兄双黑兄红转上去兄黑子不黑旋兄换侄最后换色旋父”。具体来说兄弟节点是红色兄弟变黑父变红旋转父节点问题节点不变继续处理新兄弟。这个变换的目的很单纯把红色兄弟转成黑色兄弟进入后面的统一流程。兄弟是黑色且兄弟的两个孩子都是黑色这种情况兄弟这棵子树没有红色节点可以“借力”只能把问题向上抛兄弟变红问题节点移动到父节点。为什么兄弟要变红因为兄弟那边也少了一个黑黑高才平衡然后父节点带着“双重黑色”继续向上处理。兄弟是黑色但兄弟的“远侄子”是黑、“近侄子”是红先把近侄子变成黑色兄弟变红旋转兄弟把局面转换成标准的“远侄子红”形态。兄弟是黑色远侄子红这是最标准的收尾形态把兄弟涂成父节点的颜色父节点涂黑远侄子涂黑旋转父节点问题直接解决。我当时学删除修正的最大体会是不要试图一次理解全部四个分支先把它当成“模板”背下来再通过随机数据验证去加深理解。你要花十分钟去模拟一次删除修正的完整过程远不如跑一万组随机数据来得直观。3.5 用随机数据验证红黑树的正误不管插入还是删除代码写完之后必须验证。我自己在比赛前练红黑树时留了一个固定套路生成10万组随机数先插入再删除一部分每次操作后都调check函数确认整棵树依然满足五条性质。check函数长这样def check(root): if root is None: return True if is_red(root): return False black_height -1 ok True def dfs(node, cnt): nonlocal black_height, ok if node is None: if black_height -1: black_height cnt elif black_height ! cnt: ok False return if is_red(node): if is_red(node.left) or is_red(node.right): ok False nxt cnt (1 if is_black(node) else 0) dfs(node.left, nxt) dfs(node.right, nxt) dfs(root, 0) return ok and black_height 1这个check函数只检查性质2、4、5性质3在逻辑上用None代替NIL已经天然满足。如果你发现check返回False先别慌我后面会排一个“坑位检查清单”大多数bug集中在旋转的指针顺序和删除修正里的node/parent记录上。4. 竞赛实战这题到底怎么写才能拿分4.1 5分钟默写红黑树核心代码的窍门红黑树的代码量放在那里不加注释也有200行左右。想在考场上写出不爆bug的版本靠临场推理是来不及的必须在考前把模板固定下来。我自己的做法是固定一套变量命名root、node、parent、grand、uncle、sib、child整套代码都按这个命名习惯来写这样默写的时候手不抖也方便自查。插入修正的记忆点可以压缩成三句话父红再看叔。叔红父叔变黑祖父变红上移到祖父。叔黑先掰直最内子再父黑祖红旋祖父。删除修正的记忆压缩成两句话少黑找兄弟兄红旋转换黑兄。兄双黑往上抛兄黑子红换色旋父。你不需要在考场上写出教科书里那种冗长的注释代码只要有个清晰的结构考试时逻辑就不会乱。另外我建议你考前把搜索、旋转、插入、删除四个函数按固定顺序默写三遍熟练到形成肌肉记忆。4.2 如果不手写红黑树Tu推荐用什么替代我在前面说过竞赛中红黑树的替代方案就是Treap家族。Treap的核心思想是每个节点除了存键值还存一个随机优先级整棵树既要满足BST性质又要满足堆性质——父节点的优先级大于或小于子节点。这样树高期望就是O(log n)而且不需要像红黑树那样处理颜色和复杂的删除修正。Treap插入的核心是先按BST规则插入一个带有随机优先级的节点然后如果它的优先级比父节点大大根堆就往上旋转直到堆性质满足。删除也简单把要删的节点通过旋转转到叶子位置再摘掉。整个代码里只有insert和旋转两个核心操作没有“删除修正”这种魔鬼细节。如果题目不要求“严格O(log n)最坏复杂度”Treap在竞赛里几乎是完美的平衡树替代品。它代码短、容易默写、处理重复键也方便。但如果你遇到的是“验证红黑树性质”这种题那就没得替代了还是得读懂红黑树本身。4.3 边界测试数据模板万一你真的选择手写红黑树下面这组边界数据我建议你提前测一遍vals [5, 3, 7, 2, 4, 6, 8, 1, 9, 0] root None for v in vals: root insert(root, v) print(check(root)) for v in vals: root delete(root, v) if root is not None: assert check(root), fdelete {v} failed这组数据覆盖了插入时的叔叔为红、叔叔为黑、折线变直线、删除红节点、删除黑叶子、删除双子节点等主要分支。我测试时发现真正容易翻车的地方往往不是常规数据而是删除根节点后根变成None、以及删除不存在节点时search返回None这种情况。测试时多加一个delete(root, 100000)这种不存在的值确保程序不会崩。5. 常见坑位与排查技巧5.1 性质检查的顺序先查红红再查黑高写check函数时很多人把性质4和性质5混在一起查结果报错后不知道是哪个性质被破坏。我建议顺序固定成先查根是否黑再查是否存在连续红节点最后查每条路径黑高是否一致。用三个独立条件去查一旦check失败错误定位就很明确。如果你用递归写check记得处理None节点None代表NIL是黑色节点路径到这里要为黑高加1。漏掉这个等于漏了性质3所有路径的黑高计数都会差1然后得到永远为False的乌龙结果。5.2 递归深度和性能问题Python递归深度默认1000但红黑树高度是二倍对数级别普通测试根本不会爆栈。真正的问题是Python本身的运行速度。如果你在OJ上跑10^5次插入10^5次查询纯Python红黑树可能跑到3秒以上蓝桥杯Python组时间通常一到两秒量级这时候你要考虑两个优化第一用__slots__减少内存和属性访问开销第二把所有旋转和颜色判断都写成独立函数减少重复代码没有问题但不要在一个函数里做太多属性访问链式操作。还有一点如果题目允许用sortedcontainers库那就别犹豫直接用。蓝桥杯赛点环境不一定有第三方库但有些赛点是允许的。考场上第一件事是确认环境在不违反规则的前提下尽量使用现成工具这是省时间的正道。5.3 None节点与属性访问的坑我在排bug时最常遇到的一个报错是AttributeError: NoneType object has no attribute color。这种bug十有八九是忘记判None。比如插入修正里如果不先判断叔叔是否为空就去读叔叔.color遇到叔叔是None直接炸。建议把所有颜色判断都统一走is_red和is_black函数这样既安全又直观。5.4 插入修正与删除修正共同的内在规律很多选手把插入修正和删除修正当两套完全独立的东西背但它们的本质是同一个问题如何在不破坏BST性质的前提下恢复红黑不变量。插入修正的触发条件是“连续红”删除修正的触发条件是“路径少黑”。你盯着这个共同点就会发现两种情况里“叔叔/兄弟节点”都扮演了核心角色它们负责告诉你本地的黑数是否平衡以及有没有红色节点可以借来旋转。坦率说我觉得红黑树真正劝退人的不是概念而是代码细节里那些“先删一条边再补一条边”的操作。所以我写这篇文章时特别强调“先子树交接、再祖先关系、最后焊死本级关系”这个步骤顺序。你把这个顺序养成本能旋转代码基本不会错。最后分享一个我个人觉得最实用的练习方式不要只盯着屏幕看代码拿一张纸画出插入修正三种情况的变换图再把删除修正四种情况的兄弟节点颜色变化画出来。考前十分钟过一遍这两张图比临时翻博客有用得多。红黑树这东西理解一遍、手写三遍、验证十遍之后不管蓝桥杯出不出这道题你都不会慌。