红黑树

定义

红黑树是满足以下条件的二叉搜索树
- 每个节点都是红色或黑色的
- 根节点是黑色的
- 所有叶子节点都是黑色的
- 如果一个节点是红色的，那么它的叶子节点都是黑色的
- 从任意节点到任意叶节点的简单路径中都包含等数量的黑色节点
注：
- 在执行操作后，如果根节点为红色，可以直接更改颜色
- 红黑树的所有叶子节点都是空的黑色节点，记为NIL节点（与NULL不同）

定理

定义
- 称NIL为外部节点，其余为内部节点
- 将从一个节点出发到达叶子节点的简单路径上的黑色节点个数称之为该节点的黑高。另外将根节点的黑高定义为树的黑高
定理1：一个有n个内部节点的红黑树的最大高度为$2log(n+1)$
定理2：在一个红黑树中，对任意一个节点X，在其所有到达叶子节点的简单路径中，最长的一条至多是最短的一条的两倍
意义：可以通过这两条定理得知，红黑树是一个近似平衡的二叉树，黑色节点是绝对的平衡因素，红色节点则是有限的不平衡因素，即控制了不平衡因素的影响。

红黑树的插入

基本原则

插入的节点都是红色节点
意义：不破坏黑高平衡

插入情况

情况1：父节点是黑色节点
- 无需其他操作
情况2：父节点和父节点的兄弟节点都是红色节点
- 将父节点和父节点和兄弟节点都染黑，然后依次上推
情况3：插入节点的父节点是红色节点，父节点的兄弟节点是黑色节点，插入节点是父节点的左节点
- 右转并修改染色
情况4：插入节点的父节点是红色节点，父节点的兄弟节点是黑色节点，插入节点是父节点的右节点
- 先左转，再右转，然后染色

插入的时间复杂度

时间复杂度：$O(log n)$
时间复杂度计算

红黑树的删除

基本原则

BST删除原则
- 如果目标节点有0或1个子节点：直接删除
- 如果目标节点有2个子节点：让x与左子树的最大节点，或右子树的最小节点交换，然后删除x

删除情况

情况1：删除虹色叶子节点
- 直接删除
情况2：删除黑色叶子节点
- 直接删除，兄弟节点着红色，问题上移
情况3：删除有两个子节点的节点
- 删除中序后继节点并替换值，然后执行修复

修复

修复只在删除黑色节点后触发，此时会破坏黑高平衡，产生额外的黑色，需要被吸收或重新分配
修复的起始状态
- x：replacement节点（接替被删除节点位置的节点）
- x有“额外的黑色”（需要被吸收或重新分配）
修复的目标：
- 目标：消除“额外的黑色”。恢复所有路径的黑高平衡
- 方法：
  - 如果x是红色：直接着黑色
  - 如果x是黑色：需要复杂度修复过程
修复过程的决策树 graph TD A[“开始修复
x有额外黑色”] –> B{“x是红色？”} B –>|是| C[“x着黑色
修复完成”]/ B –>|否| D{“x是根节点？”} D –>|是| E[“根节点吸收额外黑色
修复完成”] D –>|否| F[“x是黑色非根节点”]

F –> G{“x是父节点的哪个子节点？”} G –>|左子节点| H[“处理左子节点情况”] G –>|右子节点| I[“处理右子节点情况
(镜像)”]

H –> J{“兄弟节点S的颜色？”} J –>|红色| K[“情况1：兄弟是红色
重着色+旋转
转换问题”] J –>|黑色| L[“情况2：兄弟是黑色”]

K –> L

L –> M{“兄弟S的子节点颜色？”} M –>|都是黑色| N[“情况2.1：重着色
问题上移”] M –>|左红右黑| O[“情况2.2：旋转+重着色
转换为2.3”] M –>|右红| P[“情况2.3：旋转+重着色
修复完成”]

N –> Q[“x = x->parent
继续循环”] O –> P Q –> B

style C fill:#90EE90 style E fill:#90EE90 style P fill:#90EE90 style K fill:#FFE4B5 style N fill:#FFE4B5 style O fill:#FFE4B5