红黑树结点的新增（c语言）

• • 1、AVL树
  • 2、红黑树概述
  • 3、左旋和右旋操作
  • • 3.1、左旋
    • 3.2、右旋
  • 4、新增节点
  • • 4.1、普通插入
    • 4.2、平衡为红黑树
  • 5、遍历（深度优先）
  • • 5.1、简单测试

每个节点的左右子树高度差不超过2，超过时就会通过左旋或右旋来保证平衡
AVL要求高度平衡，在插入时开销也比较大，所以用的也不多

红黑树不是严格的平衡二叉树，但从根到叶子的最长路径不多于最短路径的两倍长

• 特点：

1. 结点是黑色或红色
2. 根结点是黑色
3. 红结点的子结点是黑色
4. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
5. 所有叶子都是黑色。（叶子是NIL结点（末梢的结点））

红黑树通过左旋、右旋或变色来达到自平衡

• 左旋

• 右旋

int rbt_left_rotate(RbtNode *p,Rbt *root){
    
    if(p == NULL){
        return -1;
    }
    // 1、r-rl 调整为 p-rl
    RbtNode *p_right = p->right;//暂存pr
    p->right = p_right->left;//将rl变为p的右子节点

    if(p_right->left != NULL){
        p_right->left->parent = p;//将p设置为rl的父节点
    }

    //2、p和r 交换，判断p是否有父节点
    p_right->parent = p->parent;
    if(p->parent == NULL){
        *root = p_right;//p没有父节点，即p为根结点
    }else{
        if(p->parent->left == p){//判断p是左节点还是右节点
            p->parent->left = p_right;
        }else{
            p->parent->right = p_right;
        }
    }

    p_right->left = p;
    p->parent = p_right;
    return 0;
}

int rbt_right_rotate(RbtNode *p,Rbt *root) {
    

    if(p == NULL){
        return -1;
    }

    // 1、l-lr调整为 p-lr
    RbtNode *p_left = p->left;//暂存pl
    p->left = p_left->right;//将rl变为p的右子节点
    if(p_left->right != NULL){
        p_left->right->parent = p;//将p设置为rl的父节点
    }

    //2、p和 l 交换，判断p是否有父节点
    p->left->parent  = p->parent;
    if(p->parent == NULL) {
        *root = p_left;//p没有父节点，即p为根结点
    }else{
        if(p->parent->left == p){//判断p是左节点还是右节点
            p->parent->left = p->left;
        } else{
            p->parent->right = p->left;
        }
        }
    p->parent = p_left;
    p_left->right = p;

    return 0;
}

int rbt_insert(Rbt *root,int data){

        

    RbtNode *node = (Rbt)malloc(sizeof(RbtNode));
    node->data = data;
    node->left = NULL;
    node->parent = NULL;
    node->right = NULL;

    if((*root) == NULL){
        node->color = BLACK;
        (*root) = node;
        return 0;
    }
    RbtNode *parent  = (*root);//找到新增节点的父节点

    //先正常插入
    while (1){
        if(parent->data > data){
            if(parent->left == NULL){
                parent->left = node;
                node->parent = parent;
                break;
            } else{
               parent =  parent->left;
            }
        } else if(parent->data < data){
            if(parent->right== NULL){
                parent->right = node;
                node->parent = parent;
                break;
            } else{
                parent =  parent->right;
            }
        } else{
            free(node);
            node = NULL;
            return 1;//插入重复数据
        }
    }

    //平衡为红黑树
    return rbt_balance(root,node);
}

int rbt_balance(Rbt *root,RbtNode *node) {
    

    node->color = RED;//新节点一定为红色
    while (node != NULL && node->parent != NULL && node->parent->color == RED){
        //情况1 ：父结点为祖父结点的左儿子
        if(node->parent->parent != NULL && node->parent->parent->left == node->parent){
            RbtNode *uncle = node->parent->parent->right;//新结点的叔叔结点
            if(uncle != NULL && uncle->color == RED){
                //情况1 .1：有叔叔结点，且颜色为红
                uncle->color = BLACK;
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;//继续对祖父结点进行操作
            }
            else{
                //情况1 .2：叔叔为黑色，或者为空
                if(node == node->parent->right){
                    //新结点为父亲的右结点
                    node = node->parent;
                    rbt_left_rotate(node,root);//对父亲进行左旋
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rbt_right_rotate(node->parent->parent,root);
            }
        }
        //情况2 ：父结点为祖父结点的右儿子
        else if(node->parent->parent != NULL && node->parent->parent->right == node->parent){
            RbtNode *uncle = node->parent->parent->left;//新结点的叔叔结点
            if(uncle != NULL && uncle->color == RED){
                //情况2 .1：有叔叔结点，且颜色为红
                uncle->color = BLACK;
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;//继续对祖父结点进行操作
            }
            else{
                  //情况1 .2：叔叔为黑色，或者为空
                    if(node == node->parent->left){
                        //新结点为父亲的左结点
                        node = node->parent;
                        rbt_right_rotate(node,root);//对父亲进行右旋
                    }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;

                rbt_left_rotate(node->parent->parent,root);

            }
        }
    }

    (*root)->color = BLACK;//根结点一定为黑色
    return 0;
}

void rbt_print_df(Rbt root,int type){

    if(root == NULL) return;

    
    if(type == 1){
        printf("%d",root->data);
        rbt_print_df(root->left,1);
        rbt_print_df(root->right,1);
    }

        
    else if(type == 2){
        rbt_print_df(root->left,2);
        printf("%d",root->data);
        rbt_print_df(root->right,2);
    }

        
    else if(type == 3){
        rbt_print_df(root->left,3);
        rbt_print_df(root->right,3);
        printf("%d",root->data);
    }
}

#include 
#include 

#define RED 0
#define  BLACK 1

typedef struct RBT{
    struct RBT* left;
    struct RBT* parent;
    struct RBT* right;
    int color;// 0 red  1 black
    int data;
}RbtNode,*Rbt;

int rbt_left_rotate(RbtNode *p,Rbt *root);//左旋
int rbt_right_rotate(RbtNode *p,Rbt *root);//右旋
int rbt_insert(Rbt *root,int data);//插入
int rbt_balance(Rbt *root,RbtNode *node);//平衡为红黑树
void rbt_print_df(Rbt root,int type);//深度优先遍历

#define size 10
int main() {
    Rbt root = NULL;//根节点
    int data[size]={1,2,3,4,5,6,7,8,9,10};
    for (int i = 0;i
        rbt_insert(&root,data[i]);
    }

    rbt_print_df(root,1);//前序遍历

    return 0;
}

参考：https://blog.csdn.net/u014454538/article/details/120120216