红黑树（RBtree）

忘是亡心i 2022-08-04 16:38 129阅读 0赞

有可能是因为输入不够随机，也有可能经过某些插入和删除操作，二叉搜索树有可能会失去平衡而造成效率低下的情况。红黑树是一种平衡的二叉搜索树。

# 红黑树（RBtree）定义 #

红黑树不仅仅是一个二叉搜索树，而且满足以下规则：

1.  每个节点的颜色不是红色就是黑色；
2.  根节点的颜色为黑色。
3.  NULL节点视为黑色；
4.  如果每个节点的颜色为红色，则其子节点的颜色必须为黑色；
5.  任何一个节点到NULL（树尾端）的任何路径，所含的黑色节点数必须相同。

所以，根据规则4，新增节点的颜色必须为红色；根据规则3，新增节点的父节点颜色必须为黑色。

# 插入节点 #

## 左旋转 ##

![这里写图片描述][20150522163918843]

## 右旋转 ##

![这里写图片描述][20150522163932447]

## 情况一： ##

插入的节点为根节点。  
对策：直接将节点的颜色改为黑色。

## 情况二： ##

插入节点的父节点为黑色。  
对策：插入节点的颜色为红色，此时并没有破坏红黑树的规则。

## 情况三： ##

插入节点的父节点和叔叔节点都是红色。  
对策：  
此时祖父节点一定存在。将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，再将祖父节点变成当前节点，从新的当前节点开始重新运行此插入算法。（图片来源：saturnman）  
插入节点4，变化前：  
![这里写图片描述][8394323_129361793372ZK.png]  
变化后：  
![这里写图片描述][8394323_1293617934U9zr.png]

## 情况四 ##

当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子节点。  
对策：  
把当前节点的父节点做为新的当前节点，以新当前节点为支点做左旋转操作。  
插入节点7，变化前：  
![这里写图片描述][8394323_1293617934U9zr.png]  
变化后：  
![这里写图片描述][8394323_1293617934d11j.png]

## 情况五 ##

当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子节点。  
对策：父节点变为黑色，祖父节点变为红色，以祖父节点为支点右旋转。  
插入节点2，变化前：  
![这里写图片描述][8394323_1293617934d11j.png]  
变化后：  
![这里写图片描述][8394323_1293617935EaES.png]

[20150522163918843]: /images/20220805/0b690f8a887f425d84a4e03a99d4b35a.png
[20150522163932447]: /images/20220805/deed5bfc501f4e8185071d283aa95a3b.png
[8394323_129361793372ZK.png]: /images/20220805/cefc575eaad446b3bc491c76cc3d9ea7.png
[8394323_1293617934U9zr.png]: /images/20220805/ce589a8fdaf243d6853e5ca899f6a531.png
[8394323_1293617934d11j.png]: /images/20220805/64746da527c84093be3a221a23f4d900.png
[8394323_1293617935EaES.png]: /images/20220805/d5112809c68d4273ae913ca086e78c89.png