1. 红黑树的结构定义
  2. 红黑树的学习诀窍
  3. 红黑树的学前思考
  4. 红黑树的插入调整情况
  5. 红黑树的删除调整情况
  6. 红黑树的代码演示

1.红黑树——结构定义

五个条件：

（1）每个结点非黑即红

（2）根结点是黑色

（3）叶结点(NIL)是黑色

（4）如果一个结点是红色，则它的两个子结点都是黑色的（红色和红色不能挨着）

（5）从根结点出发到所有叶结点路径上，黑色结点数量相同

2.红黑树——学习诀窍

（1）插入调整站在==祖父结点==看

（2）删除调整站在==父结点==看

（3）插入（2）和删除（3）的情况处理一共总结为五种

（4）理解调整策略时，时刻记住黑色结点数量调整前后相同（对整体不影响）

3.红黑树——学前思考

qes1：红黑树中，最长路径和最短路径长度的关系？

qes2：新插入的结点是什么颜色的？红色，黑色？

ans2：红色。插入黑色一定失衡，插入红色不一定失衡。

4.插入调整情况

（1）情况一：叔叔是红色——最简单

（四种情况，x也可以在图示中的另外三个兄弟结点的位置）

（2）情况二：叔叔是黑色（LL、LR）

LL型为例：

①红黑黑：红色上浮

②黑红红：红色下沉

LR型：先进行小左旋，不需要进行颜色调整，再进行大右旋，最后才进行颜色调整（红色上浮、红色下沉）

5.删除调整

情况1：删除度为2的红色结点

情况2：删除度为2的黑色结点

（1）和（2）转换为删除度为1和度为0的情况，不另做讨论。

情况3：删除度为1的红色结点

不存在度为1的红色结点。因为从根结点出发到所有叶结点路径上，黑色结点数量相同。

情况4：删除度为1的黑色结点

度为1的黑色结点有且只有一个红色子结点。（只有倒数第二层会出现度为1的黑色结点）直接把红色子结点变为黑色结点即可。

情况5：删除度为0的红色结点

直接删除。

情况6：删除度为0的黑色结点

影响平衡。因为从根结点出发到所有叶结点路径上，黑色结点数量相同，删除一个黑叶子结点时，另一个黑色叶子结点就会无处安放。被删除的黑色结点连接的NIL结点就会被记为双重黑色。

删除调整，主要就是解决由双重黑造成的不平衡

（1）删除调整一

brother结点为黑色且无红色子结点

（2）删除调整二

兄弟结点为黑且其同一侧的子结点是红色结点，RR类型

（3）删除调整三

brother结点为黑色且红色子结点不在同一侧，则为RL类型

（4）删除调整四

兄弟结点为红色结点

6.代码演示

#include#include typedef struct Node{int key, color; //color 0: red, 1: black, 2: double blackstruct Node *lchild, *rchild;} Node;Node __NIL;//NIL映射到一个真实结点的地址#define NIL (&__NIL)__attribute__((constructor))void init_NIL(){NIL->key = 0;NIL->color = 1;//红黑树中NIL结点是黑色NIL->lchild = NIL->rchild = NIL;return ;}Node *getNewNode(int key){Node *p = (Node *)malloc(sizeof(Node));p->key = key;p->lchild = p->rchild = NIL;p->color = 0; //新插入结点默认是红色（插入黑色必定不平衡）return p;}//返回当前结点下面是否有红色结点int has_red_child(Node *root){return root->lchild->color == 0 || root->rchild->color == 0;}//左旋Node *left_rotate(Node *root){printf("left rotate: %d\n", root->key);Node *new_root = root->rchild; //新根结点=原根结点的右子结点root->rchild = new_root->lchild; //原根结点的右子结点=新根结点的左子结点new_root->lchild = root; //新根结点的左子结点=原根结点return new_root;}//右旋Node *right_rotate(Node *root){printf("right_rotate: %d\n", root->key);Node *new_root = root->lchild; //新根结点=原根结点的左子结点root->lchild = new_root->rchild; //原根结点的左子结点=新根结点的右子结点new_root->rchild = root; //新根结点的右子结点=原根结点return new_root;}const char *insert_maintain_type_str[] = {"insert type 1: change color", "insert type 2: LL", "insert type 2: LR", "insert type 2: RR", "insert type 2: RL"};Node *insert_maintain(Node *root){if(!has_red_child(root)) return root; //如果当前结点的子结点没有红色的，就不会出现双红的情况//左（右）子树颜色是红色并且左（右）子树没有红色子孩子时没有冲突if(!(root->lchild->color == 0 && has_red_child(root->lchild)) && !(root->rchild->color == 0 && has_red_child(root->rchild))) return root;//rotateint type = 0;if(root->rchild->color == 1){//右子树颜色是黑色，说明冲突发生在L（LL、LR）if(root->lchild->rchild->color == 0){ // LR类型root->lchild = left_rotate(root->lchild); //抓住左子树进行小左旋++type;}++type;root = right_rotate(root); //抓住根结点大右旋 LL} else if(root->lchild->color == 1){ //左子树的颜色是黑色，说明冲突发生在R（RR、RL）type = 2;if(root->rchild->lchild->color == 0){ //RL类型root->rchild = right_rotate(root->rchild); //抓住右子树进行小右旋++type;}++type;root = left_rotate(root); //抓住根结点大左旋 RR}printf("insert maintain type = %s\n", insert_maintain_type_str[type]);//上三角变成红黑黑root->color = 0;root->lchild->color = root->rchild->color = 1;return root;}Node *__insert(Node *root, int key){if(root == NIL) return getNewNode(key);if(root->key == key) return root;if(root->key > key) root->lchild = __insert(root->lchild, key);else root->rchild = __insert(root->rchild, key);return insert_maintain(root); //返回进行调整以后的根结点}Node *insert(Node *root, int key){root = __insert(root, key);root->color = 1; //保证根结点是黑色return root;}const char *erase_maintain_type_str[] = {"red 1(right) : change color","red 2(left) : change color","balck 1 : no red child", "black 2 : LL","black 2 : LR", "black 2 : RR","black 2 : RL"};//删除调整Node *erase_maintain(Node *root){if(root->lchild->color != 2 && root->rchild->color != 2) return root; //左右子树都不是双重黑，直接returnint type = 0;if(has_red_child(root)){ //如果当前结点下有红色子结点，就是双重黑结点的兄弟结点是红色root->color = 0; //原根结点改为红色if(root->lchild->color == 0){ //如果左侧的结点是红色root = right_rotate(root); //拉着当前根结点进行右旋，双黑结点就会在右子树上} else { //否则拉着根结点进行左旋，双黑结点就会在左子树上root = left_rotate(root);type= 1;}root->color = 1; //旋转之后的新根结点改为黑色if(type) root->lchild = erase_maintain(root->lchild); //type是1，递归到左子树去进行删除调整else root->rchild = erase_maintain(root->rchild); //否则到右子树进行删除调整printf("brother is %s\n", erase_maintain_type_str[type]);return root;}//处理双黑结点的兄弟结点是黑色且无红色子结点（删除调整一）if((root->lchild->color == 1 && !has_red_child(root->lchild)) || (root->rchild->color == 1 && !has_red_child(root->rchild))){ type = 2; --root->lchild->color; //左子结点-1层黑色 --root->rchild->color; //右子结点-1层黑色 ++root->color; //根结点+1层黑色 return root; }type = 2;//调整二、三if(root->rchild->color == 1){ //如果左子树的颜色是黑色 Lif(root->lchild->lchild->color != 0){ // LR类型（要直接判断左子树的颜色，因为LL类型是优先的，右子 树不论是不是红色，只要左子树是红色就是LL类型）++type;root->lchild = left_rotate(root->lchild); //抓住左子树进行小左旋}++type;root->rchild->color = 1;root->lchild->color = root->color; //新根结点的颜色改为原根结点的原色。右旋的新根结点就是原来的左 子树root = right_rotate(root); //抓住当前根结点进行大右旋} else { //LLtype = 3;if(root->rchild->rchild->color != 0){++type;root->rchild = right_rotate(root->rchild);}++type;root->rchild->color = root->color;root = left_rotate(root);}root->lchild->color = 1;root->lchild->color = root->rchild->color = 1; //根结点的左右子结点都改为黑色printf("brother is %s\n", erase_maintain_type_str[type]);return root;}Node *__erase(Node *root, int key){if(root == NIL) return root;if(root->key > key) root->lchild = __erase(root->lchild, key); //到左子树删除else if(root->key < key) root->rchild = __erase(root->rchild, key); //到右子树删除else { //要删除的是当前结点if(root->lchild == NIL || root->rchild == NIL){ //删除n = 0 || n = 1的，对应了情况3、4、5、6Node *temp = root->lchild == NIL ? root->rchild : root->lchild; //如果左子树为空就指向右子树，否则指向左子树。找到唯一子孩子或者让temp指向NIL//情况4：红色子结点变为黑色代替被删除的黑色结点。红色是0，黑色是1，把当前子结点的黑色加到子结 点上去//情况5直接删除，不用管颜色//情况6：temp结点指向的其实是NIL结点，把当前结点的黑色加到NIL上去变成双重黑temp->color += root->color; free(root);return temp;} else { //n = 2Node *temp = root->lchild;while(temp->rchild != NIL) temp = temp->rchild; //找到当前结点的前驱（也可以是后继）root->key = temp->key; //前驱的值直接赋值给当前结点root->lchild = __erase(root->lchild, temp->key); //到左子树中删除前驱结点的值}}return erase_maintain(root); }Node *erase(Node *root, int key){root = __erase(root, key);root->color = 1; //保证根结点是黑色return root;}void clear(Node *root){if(root == NIL) return ;clear(root->lchild);clear(root->rchild);free(root);return ;}void printf_node(Node *root){printf("( %d(%d) | %d, %d )\n", root->key, root->color, root->lchild->key, root->rchild->key);return ;}void output(Node *root){if(root == NIL) return ;printf_node(root);output(root->lchild);output(root->rchild);return ;}int main(){Node *root = NIL;int key;while(~scanf("%d", &key)){if(key == -1) break;printf("\n===insert %d to rad black tree===\n", key);root = insert(root, key);output(root);}while(~scanf("%d", &key)){if(key == -1) break;printf("\n===erase %d to rad black tree===\n", key);root = erase(root, key);output(root);}clear(root);return 0;}

要是对您有帮助，点个赞再走吧~ 欢迎评论区讨论~