文件名称:
从零开始学习数据结构_红黑树.md
所在目录:
article / 数据结构代码实现
文件大小:
10.20 KB
下载地址:
文本预览:
- [一、红黑树](#一红黑树)
- [二、红黑树与AVL树](#二红黑树与avl树)
- [三、红黑树的插入](#三红黑树的插入)
- [3.1 错误的方式](#31-错误的方式)
- [3.2 正确旋转的两种方式](#32-正确旋转的两种方式)
- [3.3 左旋代码实现](#33-左旋代码实现)
- [3.4 右旋代码实现](#34-右旋代码实现)
- [四、RBtree插入完整代码+测试代码+运行结果](#四rbtree插入完整代码测试代码运行结果)
- [4.1 插入代码](#41-插入代码)
- [4.2 测试代码](#42-测试代码)
- [4.3 运行结果](#43-运行结果)
- [五、删除算法](#五删除算法)
- [六、说明](#六说明)
秋招的时候，有次现场面试，面试官就让我手撕红黑树，当时就手写了插入算法的代码，当然了，其中插入算法，包含其左旋、右旋算法的实现，今天就把完整代码分享出来，希望能帮到各位。
## 一、红黑树
1. 每个结点不是红的就是黑的；
2. 根结点为黑色；
3. 红结点的孩子必为黑结点；
4. (除了根结点)任一结点不管通过什么路径，到达叶子节点的黑结点数目一定相同；
总结概括：**一头一脚黑，黑同红不连：根为黑，到脚(叶子节点)的黑结点相同，红结点不相连。**
## 二、红黑树与AVL树
- AVL树 --> 由高度限定平衡，是严格意义上的平衡，绝对平衡；
- RBTree --> 由红黑颜色限定平衡，不是太严格限定树的平衡；
## 三、红黑树的插入
红黑树是二叉搜索树，按二叉搜索树的大小比较进行插入；**只能插入红色结点(黑色的话不满足黑同)，红色若相连，通过旋转解决！！！**
结构体控制头如下：
```cpp
typedef struct Node{ //红黑树结点类型
Color color; //红或黑色
Type data; //存储的数据
struct Node *leftChild, *rightChild, *parent; //为了方便操作，左右孩子和父结点指针
}Node;
typedef struct RBTree{ //红黑树类型
Node *root; //根结点
Node *NIL; //指向一个空结点，构造了root有父结点;
}RBTree;
```
我的想法是：**用一个指向树类型的指针，申请一个树类型空间，在利用树类型空间里面的 root 构造一棵树。**
模型示意图如下：
在产生的结点中，每个结点的左右开始都赋值为 NIL；指向空结点，使 root 的父为空，便于操作；只能开始插入时为红结点，最终插入完成，经过旋转可为黑色。
对于要旋转的话，有如下 2 大种情形：
### 3.1 错误的方式
**直接将根结点与左右孩子交换颜色，但是就不满足根是黑色了;**
### 3.2 正确旋转的两种方式
1、
**先做一次右单旋转，在交换1结点和2结点颜色。**
如下图：
2、
**先做一次先左后右的双旋转，在交换1结点和4结点的颜色。**
如下图：
**先左后右的旋转在这里可以通过：先左旋在右旋实现；实际上只写左和右旋函数就够了。**
以上的 2 个图在左边的，实际上在右边是为镜像，一个道理。
### 3.3 左旋代码实现
```cpp
void leftRotate(RBTree *t, Node *p){
Node *s = p->rightChild;
p->rightChild = s->leftChild;
if(s->leftChild != t->NIL){
s->leftChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->leftChild = p;
p->parent = s;
}
```
### 3.4 右旋代码实现
```cpp
void rightRotate(RBTree *t, Node *p){
Node *s = p->leftChild;
p->leftChild = s->rightChild;
if(s->rightChild != t->NIL){
s->rightChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->rightChild = p;
p->parent = s;
}
```
## 四、RBtree插入完整代码+测试代码+运行结果
### 4.1 插入代码
```cpp
#ifndef _RBTREE_H_
#define _RBTREE_H_
#include
typedef enum{RED, BLACK} Color;
typedef struct Node{
Color color;
Type data;
struct Node *leftChild, *rightChild, *parent;
}Node;
typedef struct RBTree{
Node *root;
Node *NIL;
}RBTree;
Node *createNode(); //创建一个结点空间
void initRBTree(RBTree **t); //初始化红黑树
void leftRotate(RBTree *t, Node *p); //坐旋转函数
void rightRotate(RBTree *t, Node *p); //右旋转函数
void insertFixup(RBTree *t, Node *x); //插入的调整函数
bool insert(RBTree *t, Type x); //插入函数
void showRBTree(RBTree rb); //显示函数
void show(RBTree rb, Node *t); //真正的显示函数
void show(RBTree rb, Node *t){
if(t != rb.NIL){
show(rb, t->leftChild);
printf("%d : %d\n", t->data, t->color);
show(rb, t->rightChild);
}
}
void showRBTree(RBTree rb){
show(rb, rb.root);
}
bool insert(RBTree *t, Type x){
Node *s = t->root;
Node *p = t->NIL;
while(s != t->NIL){ //找插入位置
p = s;
if(p->data == x){
return false;
}else if(x < p->data){
s = s->leftChild;
}else{
s = s->rightChild;
}
}
Node *q = createNode();
q->data = x;
q->parent = p;
if(p == t->NIL){
t->root = q;
}else if(x < p->data){
p->leftChild = q;
}else{
p->rightChild = q;
}
q->leftChild = t->NIL; //都指向空结点
q->rightChild = t->NIL;
q->color = RED; //插入结点颜色为红
insertFixup(t, q); //调用一个调整函数
return true;
}
void insertFixup(RBTree *t, Node *x){
Node *s;
while(x->parent->color == RED){
if(x->parent == x->parent->parent->leftChild){ //leftChild
s = x->parent->parent->rightChild;
if(s->color == RED){
x->parent->color = BLACK;
s->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
continue;
}else if(x == x->parent->rightChild){
x = x->parent;
leftRotate(t, x);
}
x->parent->color = BLACK; //交换颜色
x->parent->parent->color = RED;
rightRotate(t, x->parent->parent);
}else{ //rightChild
s = x->parent->parent->leftChild;
if(s->color == RED){
x->parent->color = BLACK;
s->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
continue;
}else if(x == x->parent->leftChild){
x = x->parent;
rightRotate(t, x);
}
x->parent->color = BLACK; //交换颜色
x->parent->parent->color = RED;
leftRotate(t, x->parent->parent);
}
}
t->root->color = BLACK;
}
void rightRotate(RBTree *t, Node *p){
Node *s = p->leftChild;
p->leftChild = s->rightChild;
if(s->rightChild != t->NIL){
s->rightChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->rightChild = p;
p->parent = s;
}
void leftRotate(RBTree *t, Node *p){
Node *s = p->rightChild;
p->rightChild = s->leftChild;
if(s->leftChild != t->NIL){
s->leftChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->leftChild = p;
p->parent = s;
}
void initRBTree(RBTree **t){
(*t) = (RBTree *)malloc(sizeof(RBTree));
(*t)->NIL = createNode();
(*t)->root = (*t)->NIL;
(*t)->NIL->color = BLACK;
(*t)->NIL->data = -1;
}
Node *createNode(){
Node *p = (Node *)malloc(sizeof(Node));
p->color = BLACK;
p->data = 0;
p->leftChild = p->rightChild = p->parent = NULL;
return p;
}
#endif
```
### 4.2 测试代码
```cpp
#include
typedef int Type;
#include"RBTree.h"
int main(void){
RBTree *rb;
int ar[] = {10, 7, 4, 8, 15, 5, 6, 11, 13, 12,};
//int ar[] = {10, 7, 5};
int n = sizeof(ar)/sizeof(int);
int i;
initRBTree(&rb);
for(i = 0; i < n; i++){
insert(rb, ar[i]);
}
printf("0代表红，1代表黑\n");
showRBTree(*rb);
return 0;
}
```
### 4.3 运行结果
## 五、删除算法
红黑树的删除思路：**在搜索二叉树中，永远记住删除结点，先化为只有左树或右树一个分支在解决；**
**所以，先找到结点，在转换为只有一个分支的，在删除(只能删除红色的结点)，可能通过旋转调整函数进行平衡！！！**
## 六、说明
原创文章链接：[从零开始学习数据结构-->红黑树
](https://mp.weixin.qq.com/s?__biz=MzU4MjQ3NzEyNA==&mid=2247485549&idx=1&sn=38cd0248e9c06c6f6a77d5ad86bbd640&chksm=fdb6fc46cac1755013b592f1a776b1c4dae374d339664091c7d54537ab5f4125686004102587&token=1129091266&lang=zh_CN#rd)
- [二、红黑树与AVL树](#二红黑树与avl树)
- [三、红黑树的插入](#三红黑树的插入)
- [3.1 错误的方式](#31-错误的方式)
- [3.2 正确旋转的两种方式](#32-正确旋转的两种方式)
- [3.3 左旋代码实现](#33-左旋代码实现)
- [3.4 右旋代码实现](#34-右旋代码实现)
- [四、RBtree插入完整代码+测试代码+运行结果](#四rbtree插入完整代码测试代码运行结果)
- [4.1 插入代码](#41-插入代码)
- [4.2 测试代码](#42-测试代码)
- [4.3 运行结果](#43-运行结果)
- [五、删除算法](#五删除算法)
- [六、说明](#六说明)
秋招的时候，有次现场面试，面试官就让我手撕红黑树，当时就手写了插入算法的代码，当然了，其中插入算法，包含其左旋、右旋算法的实现，今天就把完整代码分享出来，希望能帮到各位。
## 一、红黑树
1. 每个结点不是红的就是黑的；
2. 根结点为黑色；
3. 红结点的孩子必为黑结点；
4. (除了根结点)任一结点不管通过什么路径，到达叶子节点的黑结点数目一定相同；
总结概括：**一头一脚黑，黑同红不连：根为黑，到脚(叶子节点)的黑结点相同，红结点不相连。**
## 二、红黑树与AVL树
- AVL树 --> 由高度限定平衡，是严格意义上的平衡，绝对平衡；
- RBTree --> 由红黑颜色限定平衡，不是太严格限定树的平衡；
## 三、红黑树的插入
红黑树是二叉搜索树，按二叉搜索树的大小比较进行插入；**只能插入红色结点(黑色的话不满足黑同)，红色若相连，通过旋转解决！！！**
结构体控制头如下：
```cpp
typedef struct Node{ //红黑树结点类型
Color color; //红或黑色
Type data; //存储的数据
struct Node *leftChild, *rightChild, *parent; //为了方便操作，左右孩子和父结点指针
}Node;
typedef struct RBTree{ //红黑树类型
Node *root; //根结点
Node *NIL; //指向一个空结点，构造了root有父结点;
}RBTree;
```
我的想法是：**用一个指向树类型的指针，申请一个树类型空间，在利用树类型空间里面的 root 构造一棵树。**
模型示意图如下：
在产生的结点中，每个结点的左右开始都赋值为 NIL；指向空结点，使 root 的父为空，便于操作；只能开始插入时为红结点，最终插入完成，经过旋转可为黑色。
对于要旋转的话，有如下 2 大种情形：
### 3.1 错误的方式
**直接将根结点与左右孩子交换颜色，但是就不满足根是黑色了;**
### 3.2 正确旋转的两种方式
1、
**先做一次右单旋转，在交换1结点和2结点颜色。**
如下图：
2、
**先做一次先左后右的双旋转，在交换1结点和4结点的颜色。**
如下图：
**先左后右的旋转在这里可以通过：先左旋在右旋实现；实际上只写左和右旋函数就够了。**
以上的 2 个图在左边的，实际上在右边是为镜像，一个道理。
### 3.3 左旋代码实现
```cpp
void leftRotate(RBTree *t, Node *p){
Node *s = p->rightChild;
p->rightChild = s->leftChild;
if(s->leftChild != t->NIL){
s->leftChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->leftChild = p;
p->parent = s;
}
```
### 3.4 右旋代码实现
```cpp
void rightRotate(RBTree *t, Node *p){
Node *s = p->leftChild;
p->leftChild = s->rightChild;
if(s->rightChild != t->NIL){
s->rightChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->rightChild = p;
p->parent = s;
}
```
## 四、RBtree插入完整代码+测试代码+运行结果
### 4.1 插入代码
```cpp
#ifndef _RBTREE_H_
#define _RBTREE_H_
#include
typedef enum{RED, BLACK} Color;
typedef struct Node{
Color color;
Type data;
struct Node *leftChild, *rightChild, *parent;
}Node;
typedef struct RBTree{
Node *root;
Node *NIL;
}RBTree;
Node *createNode(); //创建一个结点空间
void initRBTree(RBTree **t); //初始化红黑树
void leftRotate(RBTree *t, Node *p); //坐旋转函数
void rightRotate(RBTree *t, Node *p); //右旋转函数
void insertFixup(RBTree *t, Node *x); //插入的调整函数
bool insert(RBTree *t, Type x); //插入函数
void showRBTree(RBTree rb); //显示函数
void show(RBTree rb, Node *t); //真正的显示函数
void show(RBTree rb, Node *t){
if(t != rb.NIL){
show(rb, t->leftChild);
printf("%d : %d\n", t->data, t->color);
show(rb, t->rightChild);
}
}
void showRBTree(RBTree rb){
show(rb, rb.root);
}
bool insert(RBTree *t, Type x){
Node *s = t->root;
Node *p = t->NIL;
while(s != t->NIL){ //找插入位置
p = s;
if(p->data == x){
return false;
}else if(x < p->data){
s = s->leftChild;
}else{
s = s->rightChild;
}
}
Node *q = createNode();
q->data = x;
q->parent = p;
if(p == t->NIL){
t->root = q;
}else if(x < p->data){
p->leftChild = q;
}else{
p->rightChild = q;
}
q->leftChild = t->NIL; //都指向空结点
q->rightChild = t->NIL;
q->color = RED; //插入结点颜色为红
insertFixup(t, q); //调用一个调整函数
return true;
}
void insertFixup(RBTree *t, Node *x){
Node *s;
while(x->parent->color == RED){
if(x->parent == x->parent->parent->leftChild){ //leftChild
s = x->parent->parent->rightChild;
if(s->color == RED){
x->parent->color = BLACK;
s->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
continue;
}else if(x == x->parent->rightChild){
x = x->parent;
leftRotate(t, x);
}
x->parent->color = BLACK; //交换颜色
x->parent->parent->color = RED;
rightRotate(t, x->parent->parent);
}else{ //rightChild
s = x->parent->parent->leftChild;
if(s->color == RED){
x->parent->color = BLACK;
s->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
continue;
}else if(x == x->parent->leftChild){
x = x->parent;
rightRotate(t, x);
}
x->parent->color = BLACK; //交换颜色
x->parent->parent->color = RED;
leftRotate(t, x->parent->parent);
}
}
t->root->color = BLACK;
}
void rightRotate(RBTree *t, Node *p){
Node *s = p->leftChild;
p->leftChild = s->rightChild;
if(s->rightChild != t->NIL){
s->rightChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->rightChild = p;
p->parent = s;
}
void leftRotate(RBTree *t, Node *p){
Node *s = p->rightChild;
p->rightChild = s->leftChild;
if(s->leftChild != t->NIL){
s->leftChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->leftChild = p;
p->parent = s;
}
void initRBTree(RBTree **t){
(*t) = (RBTree *)malloc(sizeof(RBTree));
(*t)->NIL = createNode();
(*t)->root = (*t)->NIL;
(*t)->NIL->color = BLACK;
(*t)->NIL->data = -1;
}
Node *createNode(){
Node *p = (Node *)malloc(sizeof(Node));
p->color = BLACK;
p->data = 0;
p->leftChild = p->rightChild = p->parent = NULL;
return p;
}
#endif
```
### 4.2 测试代码
```cpp
#include
typedef int Type;
#include"RBTree.h"
int main(void){
RBTree *rb;
int ar[] = {10, 7, 4, 8, 15, 5, 6, 11, 13, 12,};
//int ar[] = {10, 7, 5};
int n = sizeof(ar)/sizeof(int);
int i;
initRBTree(&rb);
for(i = 0; i < n; i++){
insert(rb, ar[i]);
}
printf("0代表红，1代表黑\n");
showRBTree(*rb);
return 0;
}
```
### 4.3 运行结果
## 五、删除算法
红黑树的删除思路：**在搜索二叉树中，永远记住删除结点，先化为只有左树或右树一个分支在解决；**
**所以，先找到结点，在转换为只有一个分支的，在删除(只能删除红色的结点)，可能通过旋转调整函数进行平衡！！！**
## 六、说明
原创文章链接：[从零开始学习数据结构-->红黑树
](https://mp.weixin.qq.com/s?__biz=MzU4MjQ3NzEyNA==&mid=2247485549&idx=1&sn=38cd0248e9c06c6f6a77d5ad86bbd640&chksm=fdb6fc46cac1755013b592f1a776b1c4dae374d339664091c7d54537ab5f4125686004102587&token=1129091266&lang=zh_CN#rd)
点赞
回复
X