红黑树插入和删除 关键点变色与旋转自平衡

昨天学习了红黑树，它是二叉搜索树的优化版本，避免了二叉搜索树在插入排好序的集合时退化成链表的问题。

一、红黑树的五条准则

1. 要么黑要么红
2. 根节点一定是黑的
3. 叶子节点（NIL）一定是黑色的
4. 红色节点的两个子节点必须是黑的（即不能连续红）
5. 从任意节点到其每一个叶子节点，黑色节点的数量相同

二、插入操作示例

1、单旋（LL型）

构建一颗 [7, 3, 1] 的红黑树

第一步：插入 7

新节点默认红色，但根节点一定是黑色，所以改成黑色。

第二步：插入 3

默认红色，父节点是黑色，没有连续红，直接插入。

第三步：插入 1

插入后出现连续红（3和1均为红色），且叔叔节点为 null（黑色）。
由于插入元素 1 与父节点 3 方向相同（左-左），触发右单旋：

• 祖父节点 7 与父节点 3 整体右旋
• 3 上浮为子树根，变黑色
• 7 下沉为右孩子，变红色

2、双旋（LR型）

构建一颗 [10, 18, 7, 15, 16] 的红黑树

第一步：插入 10

第二步：插入 18

第三步：插入 7

第四步：插入 15

出现连续红（18 和 15），叔叔节点 7 为红色，触发变色：

• 叔叔节点 7 变黑
• 父节点 18 变黑
• 祖父节点 10 变红，但根必须为黑，故重新变回黑色

第五步：插入 16

出现连续红（15 和 16），叔叔节点为 null（黑色），无法通过变色解决，触发双旋：

• 16 是右孩子，15 是左孩子 → LR（左-右）型
• 第一次旋转：16 绕 15 左旋，15 下沉，16 上浮
• 第二次旋转：16 绕 18 右旋，18 下沉，16 上浮为子树根
• 重新着色：16 变黑，18 变红

三、删除操作示例

下面是一棵红黑树，要删除节点 5，删除后破坏黑高平衡，需要对其进行旋转操作。

删除节点 5 后，其兄弟节点为 15，侄子节点为 12，属于 RL（右-左）型，触发双旋：

• 第一次旋转：12 绕 15 右旋，12 上浮，15 下沉；12 变黑，15 变红
• 第二次旋转：12 绕 10 左旋，12 上浮，10 下沉；10 变红

旋转结束后黑高一致，平衡恢复。

四、结尾

红黑树的核心机制：通过颜色约束和旋转操作，在二叉搜索树的基础上实现自平衡，保证最坏情况下的查找效率。

红黑树的应用场景

应用领域	具体场景
编程语言标准库	Java 的 TreeMap / TreeSet、C++ 的 std::map / std::set 底层均依赖红黑树
操作系统内核	Linux 内核的 CFS 调度器、虚拟内存管理使用红黑树管理进程和内存区域
数据库系统	MySQL 等数据库内存中的缓存表、排序操作常借助红黑树
网络协议	Nginx 等高性能服务器用红黑树管理定时器事件

红黑树要点整理

• 5 条性质：节点非红即黑 / 根黑 / 叶黑（NIL）/ 红节点子节点必黑 / 每条路径黑高相同
• 插入修复：叔叔红则变色，叔叔黑同向则单旋，叔叔黑反向则双旋
• 删除修复：看兄弟和侄子颜色，兄弟红先变色旋转转为黑兄弟，再根据侄子位置决定单旋或双旋，双黑可能向上冒泡
• 旋转口诀：同向单旋反向双，先掰直再反向甩