数据结构之三红黑树

ゝ一世哀愁。 2022-05-29 12:29 32阅读 0赞

几天之前学习了一下红黑树。今天总结一下。

红黑树，是一种特殊的二叉排序树。她能确保任何一个节点的左右子树的高度不会超过二者中较低的那个的一倍。

要学习红黑树，首先温习一下平衡二叉树的左旋和右旋。我还是从其他地方copy 图片。(源地址：https://blog.csdn.net/sun\_tttt/article/details/65445754)

旋转的思路：首先确定以谁为基准，怎么旋转。

左旋：

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

以E基准，左旋：原来E是父节点，变为其右子树（S）的左孩子节点，现在将原来右子树(S)的左孩子变成原来父节点的右孩子。

右旋：

![这里写图片描述][SouthEast 1]

以E基准，右旋：原来S是父节点，变为其左子树（E）的右孩子节点，现在将原来左子树(E)的→孩子变成原来右子树节点的左孩子。

### 定义： ###

红黑树是满足如下条件的二叉排序树：

1.每个节点要么是红色，要么是黑色。

2.根节点必须是黑色。

3.红色父节点的两个孩子必须是 黑色。

4.对于每个节点，从该到树叶子节点的任何路径必须拥有相同个数的黑色节点。

5.每个叶子节点（NULL 或者空节点）都是黑色的。

红黑树的插入和删除操作无非是在每次操作的时候，都验证一下是否符合这五条性质。

### 插入 ###

插入步骤：

1.将一个节点按照BST插入到树中。

2. 将插入的节点涂成红色。

3.通过一系列旋转和着色操作后，使之成为一棵新的红黑树。

插入有三种结果：

1.插入的是根节点：直接涂成黑色就好。

2.被插入的节点父节点是黑色，--直接插入。

3.被插入的节点的父节点是红色。

1.叔叔节点是红色，则将父节点涂成黑色，蒋叔叔节点设置为黑色，将祖父节点设置为红色，将祖父节点设置为当前节点，之后继续最当前节点进行操作。

2.叔叔节点是黑色且当前节点是其父节点的右孩子，则将父节点作为新的当前节点，，以新的当前节点为支点进行左旋。

3.叔叔节点是黑色且当前节点是其父节点的左孩子，则将父节点设置为黑色，祖父节点设置为红色，以祖父节点为支点进行右旋。![TreeMap\_put.png][TreeMap_put.png]

删除  
Case1: x是"黑+黑"节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)  
(01) 将x的兄弟节点设为“黑色”。  
(02) 将x的父节点设为“红色”。  
(03) 对x的父节点进行左旋。  
(04) 左旋后，重新设置x的兄弟节点。  
Case 2x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。  
(01) 将x的兄弟节点设为“红色”。  
(02) 设置“x的父节点”为“新的x节点”。  
Case 3x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色  
(01) 将x兄弟节点的左孩子设为“黑色”。  
(02) 将x兄弟节点设为“红色”。  
(03) 对x的兄弟节点进行右旋。  
(04) 右旋后，重新设置x的兄弟节点。  
Case 4x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色  
(01) 将x父节点颜色 赋值给 x的兄弟节点。  
(02) 将x父节点设为“黑色”。  
(03) 将x兄弟节点的右子节设为“黑色”。  
(04) 对x的父节点进行左旋。  
(05) 设置“x”为“根节点”

这就是红黑树的基本操作。关键是理解红黑树的定义可能有点困难，其实并不是很难。

红黑树有一条重要的性质，一棵n个节点的红黑树的高度最多是2log(n+1);

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

我看有的博客是借助了TreeMap来理解的红黑树，等哪天有空了，在补上这一块的内容。

主要内容：借助TreeMap,HashMap来分析一下红黑树的增删操作。

[SouthEast]: /images/20220529/bc1de96754664d99bfc2cc63c82ba2ae.png
[SouthEast 1]: /images/20220529/86f21caff7e74536aebded043a5712da.png
[TreeMap_put.png]: /images/20220529/e3218e79fcb640c1a4414a83636477b1.png