红黑树
# 红黑树
编辑中
- 树:非线性存储结构,由 n 个有限结点组成一个具有层次关系的集合。、
- 二叉搜索树:左孩子小于父节点,右孩子大于父节点。
- AVL 树(平衡树):具有二叉搜索树的全部特性,左右子树高度差至多为1,插入或删除节点时需要左旋和右旋保持树对的平衡。
再插入、删除很频繁的场景中,平衡树需要频繁着进行调整,会使平衡树的性能大打折扣,为解决这个问题,提出了红黑树。
# 1. 红黑树性质
- 每个节点要么是黑色,要么是红色。
- 根节点是黑色。
- 每个叶子节点(NIL)是黑色。
- 每个红色节点的两个子节点一定都是黑色。 (不能有两个红色节点相邻)
- 任意一节点到每个叶子节点的路径都包含数量相同的黑色节点,俗称:黑高。
- 可以推断出:如果一个节点存在黑子节点,你们该节点肯定有两个子节点。
![red-black-tree](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree.png)
红黑树并不是一个完美平衡二叉查找树,从图中可以看到,根节点 P 的左子树高于右子树。但左右子树黑节点的层数相等,所以红黑树这种平衡为黑色完美平衡。
# 2. 红黑树查找
与二叉搜索树的查找方式一样
![red-black-tree2](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree2.png)
# 3. 红黑树平衡
红黑树保持自平衡依靠:左旋、右旋、变色
变色:节点颜色红变黑,或者黑变红。
左旋:以某节点作为支点(旋转节点),其右子结点变为旋转节点的父节点,右子节点的左子节点变为旋转节点的右子节点,左子节点保持不变。
右旋:以某节点作为支点(旋转节点),其左子结点变为旋转节点的父节点,左子节点的右子节点变为旋转节点的左子节点,右子节点保持不变。
左旋图示
左旋动图
右旋图示
右旋动图
# 4. 红黑树插入
插入操作包括两部分工作:
- 查找插入的位置
- 插入后自平衡
注意:插入节点,必须为红色,因为红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。但如果插入节点是黑色,那么插入位置所在的子树黑色节点总是多 1,必须做自平衡。
红黑树插入情况分析:
情景1:红黑树为空树
直接把插入节点作为根节点,并把插入的节点设为黑色,因为性质 2 规定根节点是黑色。
情景2:插入节点的 Key 已存在
更新当前节点的值,为插入节点的值。
情景3:插入节点的父节点为黑色
由于插入节点是红色的,插入后并不影响红黑树的平衡。根据 Q 的大小选择插入的左右节点。
![red-black-tree-insert-red-node](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert-red-node.png)
情景4:插入节点的父节点为红色
依据性质2可知,根节点是黑色,如果插入节点的父节点为红色,那么该父节点不可能为根节点,所以插入节点总是存在祖父节点。
情景4.1:叔叔节点存在并且为红色节点,即父节点和叔叔节点都为红色
依据性质4可知,红色节点不能相连,所以祖父节点肯定为黑色。
因为不可以同时存在两个相连的红节点,那么此时该插入子树的红黑层数的情况是:黑红红,显然最简单的处理方式是改成:红黑红。
处理:
- 将 P 和 U 改成黑色
- 将 PP 改成红色
- 将 PP 设置为当前节点,进行后续
![red-black-tree-insert-red-node1](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert-red-node1.png)
可以看到,将 PP 节点设为红色,如果 PP 的父节点是黑色,那么无需做任何处理;但,如果 PP 的父节点是红色就违反了红黑树的性质,所以需要将 PP 设置为当前节点,继续做插入操作自平衡处理,直到平衡为止。
情景4.2:叔叔节点不存在或为黑节点,并且插入节点的父节点是祖父节点的左子节点
![red-black-tree-insert-red-node2](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert-red-node2.png)
情景4.2.1:新插入节点,为左子节点(LL双红)
![red-black-tree-insert-red-node3](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert-red-node3.png)
处理:
- 变色:将 P 设置为黑色,将 PP 设置为红色
- 对 PP 节点进行右旋
![red-black-tree-insert-red-node4](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert-red-node4.png)
情景4.2.2:新插入节点,为右子节点(LR双红)
![red-black-tree-insert-red-node5](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert-red-node5.png)
处理方式
- P 节点左旋(得到了 4.2.1 的情况:LL 双红)
- 变色:将 I 设置为黑色,将 PP 设置为红色
- 对 PP 节点进行右旋
情景4.3:叔叔节点不存在或为黑色,插入节点的父节点是祖父节点的右子节点
也就是情景 4.2 的相反情况。
![red-black-tree-insert-red-node7](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert-red-node7.png)
情景4.3.1:新插入节点为父节点的右子节点(RR双红)
![red-black-tree-insert-red-node8](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert-red-node8.png)
处理:
- 变颜色:将 P 设置为黑色,将 PP 设置为红色
- 对 PP 进行左旋
情景4.3.2:新插入节点为父节点的左子节点(RL双红)
![red-black-tree-insert-red-node10](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert-red-node10.png)
处理
- P 节点右旋(得到了 4.3.1 的情况:RR 双红)
- 变色:将 I 设置为黑色,将 PP 设置为红色
- 对 PP 节点进行左旋
# 5. 红黑树插入案例分析
下面看看这棵红黑树,需要插入新的节点 7.
![red-black-tree-insert1](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert1.png)
简化一下,把 NIL 节点去掉。
![red-black-tree-insert2](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert2.png)
先将准备插入的节点改成红色,也就是红色节点7,找到它应该插入的位置,应该为 8 的左节点。
![red-black-tree-insert3](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert3.png)
现在就属于情景 4.1,叔叔节点存在并且为红色节点。可以将父节点和叔叔节点变成黑色,爷爷节点变成红色,将爷爷节点置为当前节点。
![red-black-tree-insert4](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert4.png)
此时的当且节点为红 15,属于情景 4.2.2,爷爷节点为黑色,父节点为红色,叔叔节点为红色,LR 双红。通过将节点 5 左旋,获得 4.2.1 的情况 LL 双红。
![red-black-tree-insert5](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert5.png)
将节点 15 和 19 变色,并将 19 设置为当前节点
![red-black-tree-insert6](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert6.png)
对节点 19 进行右旋,此时就得到最后的红黑树
![red-black-tree-insert7](https://raw.githubusercontent.com/zouquchen/Images/main/imgs2022/red-black-tree-insert7.png)