(xa2)红黑树：结构
从 5 条约束看懂红黑树如何保持近似平衡
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
(xa2)红黑树：结构
从 5 条约束看懂红黑树如何保持近似平衡
定义规则
上一页我们看到红黑树长得像一棵彩色的二叉搜索树。但任意给节点涂红涂黑都行吗？什么样的树才算'红黑树'？这页揭晓定义它的五条铁律——单独看各有道理，合起来才保证了树高有界。
黑=主干水管；红=支管；任一节点走任意路径到末端，主干管段数相同——保证各处水压均衡
实例验证
上页画出的那棵树，光「看着像红黑树」还不够。下面把它送进安检通道——每条性质过一遍，过不去就判定不合格。
一关对应一条性质，全部通过才放行
提升变换
前面我们看过了红黑树的五条规则和验证方法。往树里插入新节点时，新节点默认染红——一旦它的父节点也是红色，「红色不能相邻」的规则就被破坏了。修复这种违规的第一招，叫「提升变换」。
一线与主管都权限不足，两人同时培训转正（变黑），但问题被推到经理（变红）继续处理
末端节点
上页我们说「所有叶节点都是黑色」，但红黑树里的「叶」和你直觉中的不一样——它不存数据，专门用来标记空指针的边界。我们来认识这个特殊的末端节点。
所有建筑都从同一片海面起算高度，海面是固定不动、可比较的锚点
红黒树，即是B-树
上一页我们把红色节点看成挂在父亲上的小尾巴。换个角度：红黑树和 B-树（2-3-4 树）是同一个数据结构，只是写法不同。
B-树节点像合并多行的单元格；红黑树把它拆开，红边表示'原属同一合并行'
平衡性
前面定义了红黑树的五条规则，但你可能好奇：为什么这些规则加起来恰好让树保持平衡？答案藏在一个关键性质——黑高一致。它就像一只无形的手，限制了树的高度膨胀。
必经的「主楼层」（黑节点）数量固定，途经夹层（红节点）浮动不超过一层
: 接口定义
: 接口定义：定义、要点与典型应用
本节要点
- ✓5条着色规则是不变量，所有操作都在维护它
- ✓红黑树 ≡ 2-3-4 B树，是理解操作的最强视角
- ✓近似平衡（高≤2log₂n）换来更少旋转
- ✓NIL哨兵统一「末端」概念，消除空指针特例
- ✓插入修复看叔叔，删除修复看兄弟
课后思考
先合上笔记独立想，再对照答案看思路——好问题没有唯一解。
参考答案五条性质共同服务于「近似平衡」——保证根到任意叶子的最长路径不超过最短路径的两倍，让查找、插入、删除稳定在 O(log n)。任一条都不可单独废除。
参考答案几乎是一棵完全右斜的树，黑色节点沿脊线分布，红色节点夹在中间。高度约为 2·⌊log₂(n+1)⌋，这正是 RBT 相对 AVL 牺牲的最坏树形。
参考答案双黑等价于 2-3-4 树中「键数不足」的节点——本质是向兄弟「借键」或与父节点「合并」。在 B 树视角下，删除修复就是节点的 underflow 处理。