算法导论 红黑树 （插入）

假设你已经看了我前面的二叉树和按层打印的内容，看完下面的内容保证你手撕红黑树。

对二叉树优化，引入红黑概念（源码用r和b表示红和黑），保证每条由上到下的路径的黑点相同，最坏状态下，一条路径全黑，一条路径红黑交替，是其两倍长，解决二叉树完全退化成为链表的问题。

如何保证每条路径的黑点相同，红点不连续呢？

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

图片来源于互联网，如有侵权，请联系作者删除。

在红黑树中插入新的节点，有6种状态（插入节点默认红色，如果默认黑色，将不止6种状态，很麻烦，自行脑补）

插入新的节点后用color函数处理，使其保证红黑树的平衡。

color函数包括6种插入状态（1倒6对应上图右侧的6张嵌入图片）。

1和4直接调色（能够通过调色保持平衡，则无需旋转）

2和6旋转一次后调色（直接调色无法保持平衡，需要旋转一次再调色，方能保持平衡）

3和5旋转两次后调色（直接调色无法保持平衡，需要旋转两次再调色，方能保持平衡）

总的感觉是插入点上移，变色遵循左右路径的黑点数目不变，红色不相邻，随意变，结果发现，满足条件的变化只有一种可能。

源码走起

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<malloc.h>
#define N 100
#define K 100
typedef struct redblacknode RBN;
struct redblacknode {//红黑树的节点
    int key;
    char rb;
    RBN* father;
    RBN* left;
    RBN* right;
};
void redblacktree(RBN* p, int key);//红黑树，能插入关键字
void happen_rand(int* p, int n);//生成随机数
void color(RBN* p);
void right_handed(RBN* p);//右旋
void left_handed(RBN* p);//左旋
RBN static const sentry={-1,'w',NULL,NULL,NULL};//哨兵，主要作用是节省空间，不然每一个叶节点都要开辟一个空结构体；详见算法导论10.2的介绍
RBN *uncle;//定义一个叔叔指针
RBN* NODE;//定义一个根节点指针
RBN* tmp,*tmptmp;
//*********************************以下内容是按层打印源码****************************
typedef struct queue SQ;//队列
struct queue {
    RBN array[N];
    RBN* head;
    RBN* tail;
};//申明队列结构体
int enqueue(SQ* p, RBN n);//入队
RBN* dequeue(SQ* p);//出队
int printf_tree_layer(RBN* p);//按层遍历打印二叉树
int  enqueue(SQ* p, RBN n) {
    *p->tail = n;
    p->tail++;
    if (p->tail == &p->array[N]) {
        p->tail = &p->array[0];
    }//尾部循环
    if (p->head == p->tail)//判断溢出
        return -1;

}
RBN* dequeue(SQ* p) {
    if (p->head == &p->array[N]) {
        p->head = &p->array[0];
    }//尾部循环
    if (p->head == p->tail) //判断溢出
    {
        RBN* p = NULL;
        return p;
    }
    return (p->head++);
}
SQ Q = { {0},&Q.array[0],&Q.array[0] };//Q队列初始化
int  k = 0;
int sumup = 1;//当前行的元素个数
int sumdown = 0;//下一行的元素个数
int printf_tree_layer(RBN* p) {
    if (0 == sumup) {//这里是关键，当前元素是0的时候换行，
        if (sumdown == 0) return;//判断下一行是否为0
        printf("\n");
        sumup = sumdown;
        sumdown = 0;
    }
    printf("%d ", p->key);
    sumup--;//每次打印后当前元素个数减一
    if (&sentry != p->left) { enqueue(&Q, *p->left); sumdown++; }//每次生成子元素后下一行元素个数加一
    if (&sentry != p->right) { enqueue(&Q, *p->right); sumdown++; }//每次生成子元素后下一行元素个数加一
    RBN* T = dequeue(&Q);
    printf_tree_layer(T);


}
//*********************************以上内容是按层打印源码****************************
int main() {
    int array[N] = { 0}, i;
    happen_rand(array, N);//数组随机化
    RBN node = { array[0],'b' ,&sentry,&sentry,&sentry };//根节点
    NODE = &node;
    for (i = 1; i < N; i++) {
        redblacktree(NODE, array[i]);//在红黑树中插入元素
    }
    printf_tree_layer(NODE);
}

void happen_rand(int* p, int n) {
    int i;
    for (i = 0; i < N; i++) {
        p[i] = rand() % K;

    }
}

void redblacktree(RBN* p, int key) {//递归的方式把key插入到红黑树中
    if (key < p->key && p->left == &sentry) {//插入节点后需要用color函数调色

        p->left = (RBN*)malloc(sizeof(RBN));

        p->left->key = key;
        p->left->father = p;
        p->left->left = &sentry;
        p->left->right = &sentry;
        p->left->rb = 'r';
        color(p->left);
    }
    else if (key >= p->key && p->right == &sentry) {
        p->right = (RBN*)malloc(sizeof(RBN));
        p->right->key = key;
        p->right->father =p;
        p->right->left = &sentry;
        p->right->right = &sentry;
        p->right->rb = 'r';
        color(p->right);
    }
    else if (key < p->key && p->left != &sentry)
        redblacktree(p->left, key);
    else if (key >= p->key && p->right != &sentry)
        redblacktree(p->right, key);

}

void color(RBN* p) {//颜色调整分为6种状态，前两种不旋转直接调色，后四种要旋转，旋转后再调色，旋转有4种状态，每一种状态旋转后需要调色（算法导论176页）（/右旋）（\左旋）（<左旋+/右旋）（>右旋+\左旋）
    if (p->rb=='b') {return; }
    if (p->father->rb == 'r') {
        if (p->father == p->father->father->left) {//父节点是左节点
            uncle = p->father->father->right;//叔节点是右节点
            if (uncle->rb == 'r') {//叔节点是红
                if(p->father->father->father!=&sentry)p->father->father->rb = 'r';
                p->father->rb = 'b';
                uncle->rb = 'b';
                color(p->father->father);
            }
            else if (uncle->rb == 'b' || uncle == &sentry) {//叔节点是黑或者是无
                if (p == p->father->left) {//插入节点是左，进行右旋，调色        

                  right_handed(p->father);
                    p->father->rb = 'b';
                    p->father->right->rb = 'r';
                    color(p->father);
                }
                else if (p == p->father->right) {//插入节点是右，进行左旋,右旋,调色                 

                    left_handed(p);
                    right_handed(p);
                    p->rb = 'b';
                    p->right->rb = 'r';
                    color(p);
                }
            
            }
        }
        else if (p->father == p->father->father->right) {//父节点是右节点
            uncle = p->father->father->left;//叔节点是左节点
            if (uncle->rb == 'r') {//叔节点是红
                if (p->father->father->father!= &sentry)p->father->father->rb = 'r';
                p->father->rb = 'b';
                uncle->rb = 'b';
                color(p->father->father);
            }
            else if (uncle->rb == 'b' || uncle == &sentry) {//叔节点是黑或者是无
                if (p == p->father->right) {//插入节点是右，进行左旋，调色               

                    left_handed(p->father);
                    p->father->rb = 'b';
                    p->father->left->rb = 'r';
                    color(p->father);
                }
                else if (p == p->father->left) {//插入节点是左，进行右旋，左旋，左旋，调***r />                     right_handed(p);
                    left_handed(p);
                    p->rb = 'b';
                    p->left->rb = 'r';
                    color(p);
                }
            }
        }
    }

}

void left_handed(RBN* p) {
    RBN* y = p;
    RBN* x = y->father;
    x->right = y->left;
    if (y->left != &sentry) y->left->father = x;
    y->father = x->father;
    if (x->father == &sentry) NODE = y;
    else if (x == x->father->left) x->father->left = y;
    else x->father->right = y;
    y->left = x;
    x->father = y;
}

void right_handed(RBN* p) {
    RBN* x = p;
    RBN* y = x->father;
    y->left = x->right;
    if (x->right != &sentry) x->right->father = y;
    x->father = y->father;
    if (y->father == &sentry) NODE = x;
    else if (y == y->father->left) y->father->left = x;
    else y->father->right = x;
    x->right = y;
    y->father = x;
}