【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树-CSDN 博客 - 增删改查（logN）都很快 - 动态平衡 - 解决AVL 旋转过多的算法

红黑树的性质

1. 节点是红色或黑色
2. 根是黑色
3. 叶子节点（外部节点，空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），下图中的那些 null 节点才是叶子节点，null 节点的父节点在红黑树里不将其看作叶子节点
4. 红色节点的子节点都是黑色
   1. 红色节点的父节点都是黑色
   2. 从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
5. 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

增

• 数组都要往后移动

查

• 二分查找，数组也是 logn，但是数组要排序
• 当然查估计还是比 O(1)的哈希表慢一些

缺点

• 内存碎片

原理

• 首先，必定是二叉搜索树
• 叶子节点，不存储数据，为黑结点
• 除了叶子结点，下面一定会有两个子结点
• 两个特征：
  • 每一条路径，黑节点的数量是同样的
  • 不能有连续的红色结点

插入过程

1.插入 157，带上两个叶子结点 ![[Pasted image 20240405213433.png]] 2.插入情况 1：父为黑，直接插入（4 种情况） - 插入 12，比 157 小，放在左子。 - 插入 200，比 157 大，放在右子。 规则：父结点为黑结点，插入不会破坏红黑树的特征 ![[Pasted image 20240405213706.png]]

3.插入情况 2（上溢 LL、LR、RL、LR）：父叔都为红，颜色调换 - 把父亲变成黑色 - 把叔叔也变成黑色 - 爷爷变为红色（根节点要变成黑色） - 爷爷上溢，继续进行节点处理 补充情况： 插入节点父叔为红，祖父黑，曾祖父红， 颜色调换后：父叔变黑，祖父变红，曾祖父为红，出现了两个连续的红节点，这时需要继续调整，按视频中的 4 种情况操作 *![[Pasted image 20240405214835.png]]、

4.插入情况 3（普通 LL 和 RR）：父红叔黑，颜色调换，再移动（爷父子在一条直线 ）

调换会影响叔叔路径的黑结点数量。 ![[Pasted image 20240405215132.png]] 正确步骤：旋转 - 前提：爷、父、子 必须在一条直线上面 - AVL-RR 左旋：爷爷下来，作为父亲的左子结点，父亲上去 - 如果是左边则 LL 右旋 - AVL-LL 左旋 5.插入情况 4（普通 RL 和 LR）：父红叔黑，父子不同向，先掰直，再执行情况 3（爷父子不在一条直线 ） - 倒反天罡，子变父，变成情况 3 的样子， - 再按情况三调整 ![[Pasted image 20240406123615.png]] ![[Pasted image 20240406123627.png]] ![[Pasted image 20240406123638.png]]

红黑树删除

![[Pasted image 20240406124215.png]]

1.单个红节点：

手起刀落，直接删除

![[Pasted image 20240409134220.png]]	![[Pasted image 20240409134250.png]]

2.带有一个红子节点的父节点

其子节点一定为单个红节点，本身必为黑节点 删除方式：将父节点的值替换为子节点的值，然后直接删除子节点

![[Pasted image 20240409134037.png]]	![[Pasted image 20240409134054.png]]
# 3.单个黑节点删除
### 情况一：单黑，兄黑，对侄红（不用管顺侄）：
- 兄黑，对侄红（删除 929）：
- 其为右边，其对侄为兄弟的左边（异边），其顺侄为兄弟的右边
- 删除，调整
- 父兄交替（右旋）
- 颜色对调

![[Pasted image 20240409142713.png]]	![[Pasted image 20240409142946.png]]
![[Pasted image 20240409143121.png]]	![[Pasted image 20240409143154.png]]
### 情况二：单黑，兄黑，对侄黑，顺侄红
- 扭转成为对侄红，颜色对调，然后按情况一处理
*

![[Pasted image 20240409143801.png]]	![[Pasted image 20240409143842.png]]
## 情况三：单黑，兄黑，双侄黑
- 侄包括了叶结点
兄黑，双侄黑
- 直接删除
- 调换兄弟和父亲的颜色
- 如果父亲本来就是黑，就以父亲角度按照单个黑节点的思路进行处理

![[Pasted image 20240409144651.png]]	![[Pasted image 20240409145246.png]]
![[Pasted image 20240409145332.png]]
## 情况四：单黑，兄红(不用管侄子颜色)
- 目的：把兄弟变成红色
- 先删自己
- 对调
- 换颜色
- 按照情况三双侄黑的方法处理

![[Pasted image 20240409150149.png]]	![[Pasted image 20240409151429.png]]
![[Pasted image 20240409151601.png]]	![[Pasted image 20240409151735.png]]

4. 带有两个黑节点的删除

红黑树是一个二叉搜索树。 - 先找左子树中最大的节点：（左子树最右的节点，这个值的大小最接近根节点） - 或者右子树最小的节点，原因是一样的 - 将这个值赋值为根节点 - 将这个值按照其他的节点方式删掉

![[Pasted image 20240409140314.png]]
![[Pasted image 20240409140449.png]]
![[Pasted image 20240409140605.png]]