前言

链表脱离了数组的空间限制，理论上可以无限延伸，具有高效的插入与删除操作，但是与之付出的代价是——链表的查找效率低下。

而树结构的出现便是为了解决这个问题。

本文提供一个基于c语言的通用型红黑树模板库，您可以通过访问GitHub连接下载源码：https://github.com/chxzking/Red-Black-Tree/tree/master

常用性质

度是什么？

度有两个概念——节点度数与树的度数，节点的度指的是节点具有多少子节点。树的度则是指这个整个树中的最大节点度。还有一个类似度是树的总度数，总度数指所有节点的度数之和。而总度数和节点数存在一个关系：节点数=总度数+1。这个比较好理解，因为节点的度数就是记载了一个节点孩子节点的个数，而根节点是没有节点指向它的，所以缺了一个度，加上缺的就和总结点树相等了。

节点和高度的关系

首先要意识到树本质上是一个a1=1的等比数列，m叉树每一层最大节点树是上一层最大节点数的m倍，那么等比数列的q=m，由此可以得出结论：

1、m叉树第n层最多有 mn-1(i≥1)个节点

2、高度为h的m叉树最多有个节点。

3、高度为n的m叉树最少有多少n个节点。只需要保证每层至少一个节点便可，因此在一个树会退化成一个链表。

4、高度为n的度为m的树至少有n+m-1个节点。因为数的度为m，那么就意味着树中至少有一个节点存在m个子节点，那么最少情况下，除了这个节点外其他节点全部度为1，那么总数就是（n-1）*1+1*m ，也就是说，n层中，有n-1层的都只有一个节点，而存在1层具有m个节点。

5、具有n个节点的m叉树最小的高度为 h = logmn(m-1)+1 。为了求取最小高度，就需要让数在横向扩张，每一层都添加到最大的节点数，此时可以联立节点n等于第2条性质的结论解出h。

二叉树

概念

二叉树（Binary Tree）是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树衍生出了满二叉树和完全二叉树的概念。

满二叉树

满二叉树指的是：如果一棵二叉树的所有层都达到最大节点数，则称为满二叉树（即树中不存在度为1的节点，除叶子节点外所有的节点度均为2）。如下图所示：

最直观的感受就是最底层的一行都是平平整整的，没有缺一个少一个。

满二叉数的特性

1、高度为h的树具有2h-1个节点。

2、第n层的结点数为2i−1。

3、如果给满二叉树从1开始以从上到下从左至右进行编号，那么节点i的左孩子一定是2i，而有孩子是2i+1。证明：

证明过程

父节点：第n行的第i个节点，那么它的编号为2n-1-1+i。公式意义为，n-1行的节点总数加上本行的偏移量就是当前的编号。

左孩子节点：编号为2n-1+I。公式的含义是，n行节点总数加上本行偏移量。

由于每一个节点必定有两个子节点，所以偏移量I = (i-1)*2+1。联立可得左孩子节点的编号为2n-1+(i-1)*2+1。

左孩子编号除以父亲节点编号：(2n-1+(i-1)*2+1)÷(2n-1-1+i) = 2

同样的，如果一个节点i存在父节点，那么父节点的编号是i/2取整。

完全二叉树

完全二叉树指的是：如果一棵二叉树除了最后一层外，所有层都是满的，并且最后一层的节点从左到右连续排列，则称为完全二叉树。如图所示：

通俗的讲完全二叉树，其实只需要观察最后一层，将满二叉树的最大编号往最小编号开始删除，遗留下来的就是完全二叉树。

补充一个小点，满二叉树属于完全二叉树，但是完全二叉树不属于满二叉树。

完全二叉树的特性

1、完全二叉树最多只能存在一个度为1的节点。

2、由于完全二叉树可以由满二叉树减枝而来，所以它的编号也存在左孩子为2i，右孩子2i+1的规律，同时也支持i的父节点为i/2的性质。

3、假设一棵完全二叉树存在m个节点，那么编号i≤⌊m/2⌋的为分支节点，如果编号i＞⌊m/2⌋则为叶子节点。

4、具有n(n > 0)个节点的完全二叉树高度为⌈log2(n+1)⌉或者⌊log2n⌋+1

证明过程

第一种表达式写法的证明：
由于一层完全二叉树的最大可能是满二叉树，而最小可能是这一层具有一个节点，那么也就是意味着节点数目满足区间：2h-1-1< n ≤2h-1
2h-1< n+1 ≤2h
h-1<log2(n+1)≤h
即log2(n+1) ≤ h < log2(n+1)+1
由于高度一定是一个整数，为了确保等刚好大于等于，所以要向上取整，即：⌈log2(n+1)⌉

第二种表达式写法的证明：
和第一种一样，不过是限制区间有一点点变化：2h-1-1+1≤ n <2h
h-1≤ log2n <h
log2n< h ≤log2n+1
为了能恰好小于等于这个边界，所以需要向下取整，即：⌊log2n⌋+1

二叉树的遍历方式

深度搜索

深度搜索有三种遍历方式，分别是前、中、后序三种。一个二叉树可以看作左节点、当前节点、右节点三部分组成，而三种遍历方式就是以这三部分的遍历顺序进行划分，以当前节点为中心：

• 前序遍历：先遍历当前节点，再遍历左节点，最后遍历右节点
• 中序遍历：先遍历左节点，再遍历当前节点，最后遍历右节点
• 后序遍历：先遍历左节点，再遍历右节点，最后遍历当前节点

核心点1：为什么能使用这些方法保证完整遍历整个树。

根本原因是二叉树具有递归嵌套性，一个庞大的二叉树可以不断被看作三个节点的二叉树，比如下图，在左子树中拆分为了一个标准三节点二叉树，那么就可以进行遍历操作。

当左子树遍历完成后，对于整体来说，刚才相当于遍历完成了三节点中的左节点，那么接下来再遍历剩下两个节点就可以完成整棵树了

前序遍历

前序遍历顺序是当前节点、左节点、右节点，或者说可以写为“根左右”，也就是先遍历根节点，再遍历左节点，最后遍历右节点。以下图为例子：

这个图的遍历过程如下：

• 从最高视角看，这个数的左中右分别是2、1、3节点。那么根据前序遍历规则，那么先打印出1
• 接下来准备打印2的时候，发现2可以展开为4、2、5，在这个树的视角中根据规则要打印根节点2
• 接下来准备打印4，发现4到了底部，那么无需再次展开，直接打印4
• 之后再准备打印5，此时发现5可以展开为8、5、空，依旧更具规则先打印5
• 然后打印8，8无法展开，那么接下来打印空，空不存在节点，则直接忽略。
• 左子树打印完成，那么根据规则是根左右，那么接下来看右边，右边的值可以展开为6、3、7，可以看到这个是最底部的标准三节点，那么按照规则直接输出3、6、7

所以最终的输出为 1、2、4、5、8、3、6、7

代码实现如下：

//树的定义
typedef struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
}Node;
//前序遍历
void PreorderTraversal(Node* root){
    //递归出口，遇到空节点返回
    if(root == NULL) return;
    //先打印当前节点的值
    printf("%d ",root->data);
    //打印左节点的值
    PreorderTraversal(root->left);
    //打印右节点的值
    PreorderTraversal(root->right);
    return;
}

这个遍历方式最显著的特点是第一个打印的是整棵树的根节点。

中序遍历

中序遍历顺序是左节点、当前节点、右节点，或者说可以写为“左根右”，以下图为例子：

• 从最高视角看，这个数的左中右分别是2、1、3节点。那么根据中序遍历规则，那么先打印出2，但是而可以展开，那么就暂时不能打印它，展开后发现节点为4、2、5，此时打印节点4
• 然后按照规则打印2。
• 接着打印5，但是由于5能展开，所以展开后是8、5、空，那么最终打印的是8
• 按照规则，接下来打印5
• 左子树打印完成后，打印根节点1。
• 接下来找右节点，由于右节点能展开为6、3、7，那么按照规则就是依次打印6、3、7

最终的结果是：4、2、8、5、1、6、3、7

代码实现为：

//树的定义
typedef struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
}Node;
//中序遍历
void InorderTraversal(Node* root){
    //递归出口，遇到空节点返回
    if(root == NULL) return;
    //打印左节点的值
    InorderTraversal(root->left);
    //打印当前节点的值
    printf("%d ",root->data);
    //打印右节点的值
    InorderTraversal(root->right);
    return;
}

后序遍历

后序遍历顺序是左节点、右节点、当前节点，或者说可以写为“左右根”，以下图为例子：

• 和之前的遍历思路一样，在2、1、3的时候按照规则展开左节点，发现是4、2、5，所以先打印出4，在5的位置展开为8、5、空，那么就打印8、5，最后打印2
• 左子树的输出完成后接下来遍历右子树，按照规则是6、7、3
• 左右子树输出后，最后打印1

最终的输出结果是4、8、5、2、6、7、3、1

代码实现为

//树的定义
typedef struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
}Node;
//后序遍历
void PostorderTraversal(Node* root){
    //递归出口，遇到空节点返回
    if(root == NULL) return;
    //打印左节点的值
    PostorderTraversal(root->left);
    //打印右节点的值
    PostorderTraversal(root->right);
    //打印当前节点的值
    printf("%d ",root->data);
    return;
}

非递归深度搜索（迭代法）

递归类型的深度搜索存在一个明显的缺陷就是可能造成栈溢出，如果树的深度过深或者栈小就非常容易引发栈溢出导致程序崩溃，所以需要一种非递归类型的算法进行搜索。

仔细分析为什么使用递归后，会得出一个结论：需要利用递归后进先出的特性，而这个具有这个特性的一种数据结构是“栈”，其实递归也利用了栈，不过是使用了系统栈。所以需要手动实现一个堆区栈，用于进行搜索。

中序遍历

//非递归类型的中序遍历
typedef struct myStack
{
    Node* node;//节点地址
    struct myStack* next;
}myStack;
//压栈
void push(myStack** top,Node* node){
     if(node==NULL) return;
    //生成一个栈节点
    myStack *stackNode = (myStack*)malloc(sizeof(myStack));
    stackNode->node = node;
    stackNode->next = *top;
    //更新栈顶
    *top = stackNode; 
}
//出栈
Node* pop(myStack** top){
    if((*top) == NULL) return NULL;

    myStack* temp = *top;
    *top = (*top)->next;
    Node* node = temp->node;
    free(temp);
    return node;
}
//检查是否为空
bool isEmpty(myStack* top){
    if(!top) return true;
    return false;
}
//中序遍历
void InorderTraversal(Node* root){
    if(root == NULL) return;
    //定义栈顶
    myStack* top = NULL;
    //定义一个扫描节点
    Node* current = root;

    while((current != NULL) || !isEmpty(top)){
        //循环遍历一条路左孩子入栈
        while(current != NULL){
            push(&top,current);
            current = current->left;
        }
        //弹出一个节点，读取该节点的值
        current = pop(&top);
        printf("%d ",current->data);
        //获取右孩子
        current = current->right;
    }
}

整个代码其实并不难，首先是栈函数，入栈与出栈道代码很好理解，而中序遍历代码总体的逻辑很清晰，不过最难的部分是外层while的条件。条件1的isEmpty判断比较好理解，它的作用是为了判断栈是否空了，如果空了则意味着遍历完成。但是另外一个条件2的current != NULL是一个难点。

整个while循环的逻辑很明确，首先往左孩子的方向入栈，一直到压到NULL，这个时候再弹出一个节点用于读取，而在深度遍历中，其实每层的根节点都是作为上一个节点的左孩子保存的，所以整个逻辑就只包含了左孩子和右孩子，而current不仅作为了读取节点，同时也负责承接回溯的位置，而回溯也是栈本身完成的。

前序遍历

//前序遍历
void PreorderTraversal(Node* root){
    if(root == NULL) return;
    myStack* top = NULL;
    Node* current = root;

    while(!isEmpty(top) || current != NULL){
        //入栈
        while(current != NULL){
            printf("%d ",current->data);
            push(&top,current);
            current = current->left;
        }
        //出栈,获取右子树
        current = pop(&top);
        current = current->right;
    }
}

这一种方案的前序遍历和中序遍历很相似，不过它是先进行了打印输出然后再进行压栈操作

后序遍历

//后序遍历
void PostorderTraversal(Node* root){
    if(root == NULL) return;
    myStack* top = NULL;
    Node* current = root;
    Node* last = NULL;//用于记录上一次遍历的节点，作用是确认右子树是否被遍历过

    while(!isEmpty(top) || current != NULL){
        
       while (current != NULL){
            push(&top,current);
            current = current->left;
       }
       current = pop(&top);
       //判断是否遍历了右子树
       if(current->right == last || current->right == NULL){
            printf("%d ",current->data);
            last = current;
            current = NULL;
       }
       //如果没有遍历右子树，则往右子树开始遍历
       else{
           push(&top,current);//重新压栈
           current = current->right;//并且准备将右子树压栈
       }        
    }
}

这种方案中的后序遍历比较复杂，如果直接回溯会打印根节点，所以在打印根节点之前判断是否已经打印了右孩子，于是使用了last指针记录上一次打印的结果，用于判断是否打印了右孩子。

以上方案的思维逻辑应该是和下图类似，和树本身的逻辑并不完全对等：

它更像是以一条回溯路线为主，不断依次往右发散直至NULL节点。

不过树的遍历还有其他的思路，但是大差不差都是利用栈实现的。

比如这个前序遍历：

void PreorderTraversal(Node* root){
    if(root == NULL) return;
    myStack* top = NULL;
    Node* current = root;
    //根节点入栈
    push(&top,current);

    while(!isEmpty(top)){
        //取出栈顶节点
        current = pop(&top);
        //栈空则退出
        if(current == NULL){
            return;
        }
        //打印栈顶
        printf("%d ",current->data);
        //该节点右孩子入栈
        push(&top,current->right);
        //该节点左孩子入栈
        push(&top,current->left);
    }
}

这个遍历方式非常复合树的本身的逻辑，但是前中后三种遍历的写法差别比较大，而这个逻辑最简单的就是前序遍历写法。

广度搜索

广度搜索也是树的一种遍历方式，由于是一层层搜索，所以它能比较清晰的看到树的结构。

广度搜索的也叫层次遍历，它的基本思路是先读取一层，然后从左到右逐步访问数据，访问结束后推进到下一层。而队列的先进先出的特性非常复合层次遍历。所以层次遍历的代码实现中需要额外使用一个队列。

当一层进入到队列后，从队列头部取出一个节点的同时需要将其左右孩子入队。所以当一层遍历完成后，此时下一层的节点也入队完成等待出队。以下是代码实现：

typedef struct QueueNode{
    Node* node;//节点地址
    struct QueueNode* next;
}QueueNode;

typedef struct Queue{
    QueueNode* QueueHeader;
    QueueNode* QueueTail;
}Queue;

//入队
void enQueue(Queue* queue, Node* node){
    if(node == NULL) return;
    //创建队列节点
    QueueNode* queueNode = (QueueNode*)malloc(sizeof(QueueNode));
    queueNode->node = node;
    queueNode->next = NULL;
    //加入队列

    //如果队列为空
    if (queue->QueueHeader == NULL){
        queue->QueueHeader = queueNode;
        queue->QueueTail = queueNode;
    }
    //如果队列不为空
    else{
        queue->QueueTail->next = queueNode;
        queue->QueueTail = queueNode;
    }
    return;
}
//出队
Node* deQueue(Queue* queue){
    //如果队列为空则返回
    if(queue->QueueHeader == NULL) return NULL;
    //获取队首的树节点
    Node* node = queue->QueueHeader->node;
    //获取队列下一个节点的值
    QueueNode* temp = queue->QueueHeader;
    queue->QueueHeader = queue->QueueHeader->next;
    if(queue->QueueHeader == NULL){//如果队列为空了则置空
        queue->QueueTail = NULL;
    }
    free(temp);
    return node;
}
//队列判空
bool queueIsEmpty(Queue* queue){
    return queue->QueueHeader == NULL;
}
//层次遍历
void Hierarchical_traversal(Node* root){
    if(root == NULL) return;
    //创建一个队列
    Queue queue;
    queue.QueueHeader = NULL;
    queue.QueueTail = NULL;
    
    Node* current = root;
    enQueue(&queue,current);
    
    while (!queueIsEmpty(&queue)){
       //出队
       current = deQueue(&queue);
       if(current == NULL){
            return;
       }
       //输出节点数据     
       printf("%d ",current->data);
       //入队
       enQueue(&queue,current->left);
       enQueue(&queue,current->right);
    }
}

二叉搜索树

概念

二叉搜索树相对普通在二叉树进行了改进，或者说，从二叉搜索树开始才是真正进入了二叉树的优势领域。在普通的二叉树中，可以清楚的看到，要想查找一个值，最坏的情况依旧需要遍历整个树，就和链表的效率一样，而二叉搜索树则是在元素添加阶段就对元素进行了排序，从而提供了更加高效的搜索方案。

二叉搜索树具有以下特点：

1. 节点的左子树：每个节点的左子树中的所有节点的值都小于该节点的值。
2. 节点的右子树：每个节点的右子树中的所有节点的值都大于该节点的值。
3. 左右子树：每个节点的左右子树也都是二叉搜索树。

这些特点使得二叉搜索树在查找、插入和删除操作上具有较高的效率。平均情况下，这些操作的时间复杂度为O(log n)，最坏情况下为O(n)。

插入

由于二叉树具有递归性，所以插入操作可以使用递归的思想，而二叉搜索树只需要维持左子树小于右子树的基本规则就可以。

代码示例：

前置准备

#include <stdio.h>
#include <malloc.h>
//树的定义
typedef struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
}Node;
//创建节点
Node* createNode(int data){
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

节点插入

//插入节点（写法1），该函数的作用是将一个根节点的子树中插入一个元素，并返回这个可能被修改的根节点
Node* insert(Node* root,int data){
    if(root == NULL) return createNode(data);

    if(data <= root->data)
        root->left = insert(root->left,data);
    else
        root->right = insert(root->right,data);
    return root;
}

这个写法返回Node指针的原因是，在递归的过程中每次传入的根节点存在被修改可能，而一级指针是无法返回被修改的指针的，所以换了一种思路，返回新的地址，重新保存到根节点中 。当然也可以直接在递归的过程中修改根节点的指针的值，比如下面的写法2：

//插入节点（写法2），使用二级指针
void insert(Node** root ,int data){
    //退出条件
    if(*root == NULL){
        *root = createNode(data);
        return;
    }
    //叶子的选择
    if(data <= (*root)->data){
        insert(&(*root)->left,data);
    }else{
        insert(&(*root)->right,data);
    }
    return;
}

int num[]={10,7,20,6,8,18,23,16,19,21,24};//测试案例
int main(){
    Node* root = NULL;
    //写法1
   for(int i = 0;i<sizeof(num)/sizeof(num[0]);i++){
     root = insert(root,num[i]);
   }

    //写法2
   for(int i = 0;i<sizeof(num)/sizeof(num[0]);i++){
     insert(&root,num[i]);
   }
}

删除

删除的操作比较复杂一点，因为删除操作需要同时维护树结构不被破坏。但是树的节点之间的关系错综复杂，所以需要分类讨论。这里分为三类，以节点的度做为划分条件。

度为0时

度为0的节点是叶子节点，而叶子节点是最好删除的节点，因为它不与树的结构有直接的关系，它只被父亲节点连接，所以可以之间删除，然后将父亲节点的对应指针置空便可。

度为1时

度为1的节点相对难一些，它开始设计到了树的结构，并且分为左右子树两种情况，不过两种情况的本质都是一样的。不管它的左子树还是右子树的值是什么，相对于被删除节点的父亲节点都没有影响，如果被删除节点在是父亲节点的左子树，那么它的子节点一定接替更新后左子树的位置，如果被删除节点在是父亲节点的右子树，那么它的子节点一定接替更新后右子树的位置。

如图所示：

度为2时

度为2时最复杂的一种情况，它同时具有左右子树，如果想要删除该节点，必须要处理它的子树的逻辑，维持树的基本规则和结构，保持右子树大于左子树的规则。

处理方法主要有两种，不过它们本质上是一种，只是存在些微的区别。

第一种：被删除节点的右子树移动到被删除节点的左子树的最大节点的右子树上，返回被删除节点的左节点作为新根节点。

第二种：被删除节点的左子树移动到被删除节点的右子树的最小节点的左子树上，返回被删除节点的右节点作为新根节点。

核心点1：为什么可以这样移动，难道不会破坏其他节点吗？

这个问题是初学者最容易出现的问题，而且通常看得云里雾里，想问也无从下手，不知道自己什么地方没明白，总感觉哪里都明白，但又好像知道某一回事儿，其实只需要换一种思路就可以了：

首先要讲讲为什么可以这样移动。

首先移动需要一个大前提，那就是数据是有规律的，而二叉搜索树的规律是右边一定比左边大，以图例来说，要删除的节点是10，那么右子树最小的也是15，远远大于左子树的最大值8。
那么就以第一种移动方式为例，去掉了10，又想树保持结构，那么需要再次选出一个根节点，而根节点需要满足左小右大的原则。
在例子中左子树有很多可选的可以选5、7、8，但是最终选7的原因在于代码实现最简单。如果选5，那么返回新根节点需要进行多余的代码保存它的地址，然后改变它的右节点的值，此外还需要嫁接右子树。
如果选8也一样，需要改变它的左子树逻辑，然后再处理右子树的新加的值。
而如果使用7则简单很多，因为以它为根的这棵子树逻辑结构已经完整了，只需要加上右子树便可。

其次讲讲为什么不会影响到其他的节点。

这里需要使用整体的大局观，依旧使用第一种方式为例，这个方法中发生改变的节点只有8，看似复杂的操作，实际上都是它们的父节点在进行操作，父节点最终是要删除的。除了父节点，树中只有8真正出现了修改，并且所有的节点其实本质上是无法察觉父节点是否出现了什么操作的，因为连接的单向链表。
当然，这棵示例的二叉树看起来似乎没有办法代表所有的，但是再拓展一下思路，如果这棵树只是某一个巨大的二叉树的一棵子树，而且存在一个节点指向了这棵局部二叉树的根节点10，那么经过删除算法后，会返回一个新节点的地址7，而这棵局部二叉树树又经过调整重新满足了左小右大的原则，那么整棵巨大的二叉树树经过一次局部调整也依旧满足规则。
同理，由于二叉树具有递归性，完全可以将这些没有发生改变的节点看成一棵棵子树，那么就节点没有发生改变，子树的结构就不会改变，那么就可以得出结论，这个删除法没有对结构进行破坏。

实现代码（以第一种方法为例）：

//函数的含义，传入一棵树，删除指定节点后再返回这棵被调整过的树的根节点地址
Node* NodeDelete(Node* root,int data){
    //递归出口
    if(root == NULL) return NULL;
    //查找方向
    if(data < root->data){//值比当前节点值小，则往左
        root->left = NodeDelete(root->left,data);
    }else if(data > root->data){//值比当前节点大，则往右
        root->right = NodeDelete(root->right,data);
    }
    //删除操作
    else{//找到了值

        //情况1，度为0，
        if(root->left == NULL && root->right == NULL){
            free(root);
            return NULL;
        }
        //情况2，度为1，小类情况1：为右孩子
        else if(root->left == NULL&& root->right != NULL){
            Node* temp = root->right;
            free(root);
            return temp;
        }
        //情况2，度为1，小类情况2：为左孩子
        else if(root->left != NULL && root->right == NULL){
            Node* temp = root->left;
            free(root);
            return temp;
        }
        //情况3，度为2.
        else{
            //获取左子树最大的节点
            Node* left_max = root->left;
            while(left_max->right != NULL){
                left_max = left_max->right;
            }
            //移动右子树嫁接到该节点的右子树上
            left_max->right = root->right;
            //返回被删除节点的左子树
            Node* temp = root->left;
            free(root);
            //左子树节点作为新根节点
            return temp;
        }
    }
    //返回新树
    return root;
}

平衡二叉树

二叉搜索数提供了一个高效的搜索和插入的数据结构，但是却存在一个缺陷，在特殊的排列下，二叉搜索树可能退化为链表，从而效率降为O(n)

比如我有一个数组 1、2、3、4，如果从左到右插入树，则会出现以下情况：

从图示中可以看到，这个数组的值插入到树后，直接让树退化成了链表，从而失去了树原本的高效查找能力，那么是否办法解决二叉搜索树退化的问题呢？

AVL树

AVL树是一种自平衡二叉搜索树，它的主要特点是：

1. 平衡因子：每个节点的左子树和右子树的高度差（即平衡因子）最多为1。这确保了树的高度保持在对数级别，从而保证了基本操作（如插入、删除和查找）的时间复杂度为O(log n)。
2. 旋转操作：为了维持平衡，AVL树在插入或删除节点后可能需要进行旋转操作。旋转分为四种类型：单右旋、单左旋、双右旋和双左旋。

平衡因子

简单来说，就是AVL树可以将左右子树的高度差维持在[0,1]之间，或者说 |左子树高度-右子树高度| ≤ 1。举几个例子：

上述图的 左子树高度为3，右子树高度为4，所以它的根节点高度差（平衡因子）为 |3-4| = 1

上述图的 左子树高度为2，右子树高度为4，所以它的根节点高度差（平衡因子）为 |2-4| = 2

上述图的 左子树高度为3，右子树高度为3，所以它的根节点高度差（平衡因子）为 |3-3| = 0

四种基础旋转

AVL树使用了四种方法动态平衡二叉树树，其中LL型和RR型是基础旋转类型，LR型与RL型则是先变换为LL型或RR型然后处理，它们相对于基础型更为复杂。

这四种旋转类型的划分依据比较难以理解，笼统的说是引起AVL树失衡的哪个子树的哪个孩子。

在这之前，首先要明白一个概念——什么是首个失衡点，故名思意就是由于插入了新节点，从新节点往根节点的路线中，首个平衡因子被打破的节点就是首个失衡点。比如：

上图的首个失衡点是10

上图的首个失衡点是5

而四种操作都是以首个失衡点为基准，根据不同情况进行不同旋转操作，接下来展开讲讲如何操作以及如何根据失衡点判断采取哪种旋转操作。

LL型（单右旋）

LL型的特点是：添加节点的事件发生在首个失衡节点的左孩子的左子树上，也就是左(left)-左(left)型。

上述两个图都是很直观的展现出典型的例子，对于节点7而言，不管是节点6还是节点3，都是插入在它的左子树上，而7又是10的左孩子，所以这是LL型。

按照AVL树的规则，这个树已经不平衡了。它不平衡的原因在于左子树出现了新的节点导致深度加大，那么按照一个常规思路来说，就像是一杆天平，秤的东西变重了，那么需要往右边加点砝码，以图-LL型2为例，原本的根节点是10，那么我将根节点新选为7，那么这个天平的右边就有2的深度，但是树和天平不同的是，总节点数是固定的，如果右边多那么左边就要少，所以左边的深度就要降一个，最后形成平衡因子为0的AVL树。

以一个朴素的思路相同了旋转的逻辑后，接下来要处理细枝末节。前面的思路是让7作为新的根节点，那么就需要改变树的逻辑了，如果直接将7的右孩子指针指向10那么会和原来的8节点冲突，那么该如何解决呢？

这个在二叉搜索树中的思路是类似的，首先如果7作为根节点，那么10就一定是7的右子树，而7原本的右子树一定小于10，10失去根节点后它的左孩子节点一定是空出来的，最终就可以形成一个逻辑：失衡点的左孩子的右子树变成失衡点的左子树，失衡点成为原左孩子的右孩子。

具体旋转流程如下：

至于为什么被称为单右旋，是因为旋转操作发生在失衡点的右边。

RR型（单左旋）

RR型的特点是：添加节点的事件发生在首个失衡节点的右孩子的右子树上，也就是右(right)-右(right)型。以下是具有代表性的示例：

和LL型类似，RR型的操作逻辑有一点点不同，它的逻辑是10的右孩子指向12，然后15的左孩子指向10，然后15就成为了新的根节点。

因为旋转操作发生在失衡点的左边所以是左旋。

LR型（双旋转：先左后右）

LR型（Left-Right）是与其说是一种旋转类型，不如说是一种复合类型。

以LL型来说，插入节点在左孩子的左子树上，那么可以将左孩子提高变成根节点，但是出现了一个问题，原来的左孩子的右子树需要和原根节点合并。如果插入节点是左孩子的右子树就会把新插入到节点移动到新树上，脱离了正在平衡调整的这一棵子树的范围，就失去了意义。

为了解决这个问题，最终的解决方法是先左旋节点5，然后再右旋节点10 。也就是将这棵树经过第一次旋转变成LL型，然后再处理LL型。

而LR型因为经过先左再右的旋转过程，故而被成为LR型双旋

RL型（双旋转：先右后左）

RL型（Right-Left）和LR型的思想类似，也是组合旋转，不过是方向相反罢了。

还是一样的思路，先右旋转15，然后左旋10

插入

介绍了四种旋转之后，就需要将其转换为代码，依旧是利用其递归性。先将整个插入过程分为几个部分，查找合适点——旋转调整。在旋转调整这个部分需要详细分析过程，大致为判断平衡因子——判断旋转类型——旋转。不过在旋转的过程中还需要动态更新节点的高度，为了简化代码同时提高代码执行效率，通常情况下会将利用递归的特性，递归分为两个过程——推进和回溯，推进被用来是来查找插入位置，而回溯则是调整的主要战场，每次回溯意味着下一层的树已经处理完成，那么就需要在这次回溯中更新节点高度，以及判断平衡因子，如果平衡因子出现了失衡，那么同时需要在此次回溯中调整平衡，调整完成后再次进入下一轮回溯。

代码示例

基础定义：

#include <stdio.h>
#include <malloc.h>
//树的定义
typedef struct Node
{
    int data;//存储数据
    int height;//记录当前节点的高度
    struct Node* left;
    struct Node* right;
}Node;

//创建节点
Node* createNode(int data){
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    temp->height = 1;
    return temp;
}
//获取指定节点的高度
int getHeight(Node* root){
    return root ? root->height : 0;
}
//获取节点的平衡因子
int getBalaceFactor(Node* root){
    return getHeight(root->left) - getHeight(root->right);
}
//获取两个值得最大高度
int max(int d1,int d2){
    return d1>d2 ? d1 : d2;
}

基础旋转——LL型和RR型旋转

//处理旋转（右旋LL型）
Node* rotateRight(Node* root){
    //将左孩子作为新根节点
    Node* newroot = root->left;
    //原根节点下沉为newroot的右孩子
    root->left = newroot->right;
    newroot->right = root;
    //重新记录这两个节点中的高度
    root->height = max(getHeight(root->left),getHeight(root->right))+1;
    newroot->height = max(getHeight(newroot->left),getHeight(newroot->right))+1;
    return newroot;
}
//处理旋转（左旋RR型）
Node* rotateLeft(Node* root){
    //将右孩子作为新根节点
    Node* newroot = root->right;
    //原根节点下沉为newroot的左孩子
    root->right = newroot->left;
    newroot->left = root;
    //重新记录这两个节点中的高度
    root->height = max(getHeight(root->left),getHeight(root->right))+1;
    newroot->height = max(getHeight(newroot->left),getHeight(newroot->right))+1;
    return newroot;
}

核心插入代码

Node* insert(Node* root,int data){
    if(root == NULL){
        root = createNode(data);
        return root;
    }

    //输入的值小于根节点
    if(data < root->data){
        root->left = insert(root->left,data);//插入左子树
    }
    //输入的值如果大于根节点
    else if(data > root->data){
        root->right = insert(root->right,data);//插入右子树
    }
    //如果值相等
    else{
        return root;
    }
 
    //由于子树的高度发生了变化，所以需要更新当前节点的高度
    root->height = max(getHeight(root->left),getHeight(root->right))+1;

    //获取平衡因子
    int bf = getBalaceFactor(root);

    //左孩子插入
    if(bf > 1){
        //获取左孩子的平衡因子
        int Lbf = getBalaceFactor(root->left);
        //左子树插入
        if(Lbf > 0){//LL型
            root = rotateRight(root);
        }
        //右子树插入
        else{//LR型
            //先左旋左子树
            root->left = rotateLeft(root->left);
            //再右旋整个树
            root = rotateRight(root);
        }
    }
    //右孩子插入
    else if(bf < -1){
        //获取右孩子的平衡因子
        int Rbf = getBalaceFactor(root->right);
        //左子树插入
        if(Rbf > 0){//RL型
            //先右旋右子树
            root->right = rotateRight(root->right);
            //再左旋整个树
            root = rotateLeft(root);
        }
        //右子树插入
        else{//RR型
            root = rotateLeft(root);
        }
    }
    return root;
}

删除

删除是AVL中最复杂的操作，它相当于将整个AVL的操作结合。仔细锊一锊思路会发现一个特点，之前讲过普通的二叉搜索树的删除，可以根据度分为三类情况处理，AVL作为优化版本的二叉搜索树，也遵循这个处理方式，但是还有增加一项维持树平衡的操作。

维持树的平衡和插入到操作类似，也是在递归阶段通过平衡因子使用LL、RR、LR、RL四种类型进行旋转，不过需要补充一点：

这两种情况或者说是一种类型，它属于平衡因子出现了失衡，但是四种旋转类型不会出现这种情况。因为在子树形成分支之前，树就已经调整了。但是实际上，这两种情况会在删除中经常出现，不过好在它们可以使用最基础的两种旋转解决。左边的图可以使用LL型，右边的图可以使用RR型。

删除逻辑也利用了树的递归性，在推进过程负责寻找删除节点，然后在找到后进行删除操作。而回溯的过程则是负责进行调整，包括高度重置和节点旋转。

代码示例：

Node* NodeDelete(Node* root, int data) {
    //树的终点
    if(root == NULL) return NULL;

    /*删除节点*/
    //如果小于节点
    if(data < root->data){
        root->left = NodeDelete(root->left,data);
    }
    //如果大于节点
    else if(data > root->data){
        root->right = NodeDelete(root->right,data);
    }
    //如果等于节点
    else{
        /*三种删除类型*/
        //度为0和1的情况
        if( (root->left == NULL) || (root->right == NULL) ){
            //获取一个子节点的指针
            Node* temp = root->left ? root->left : root->right;
            free(root);
            return temp;
        }
        //处理度为2的点
        else{
            //获取右子树值最小的节点
            Node* temp = root->right;
            while(temp->left != NULL){
                temp = temp->left;
            }
            //将这个节点的值替换到根节点上
            root->data = temp->data;
            //从右子树中删除这个节点
            root->right = NodeDelete(root->right,temp->data);
            return root;
        }
    }

    /*树的调整*/
    //由于子节点发生了改变，所以更新当前节点的高度
    root->height = max(getHeight(root->left),getHeight(root->right))+1;
    //检查平衡因子是否出现了失衡
    int bf = getBalaceFactor(root);
    //LL型判定，以及特殊情况（左）
    if(bf > 1 && getBalaceFactor(root->left) >= 0){
        root = rotateRight(root);
    }
    //LR型判定
    else if(bf > 1 && getBalaceFactor(root->left) < 0){
        root->left = rotateLeft(root->left);
        root = rotateRight(root);
    }
    //RR型判定，以及特殊情况（右）
    else if(bf < -1 && getBalaceFactor(root->right) <= 0){
        root = rotateLeft(root);
    }
    //RL型判定
    else if(bf < -1 && getBalaceFactor(root->right) > 0){
        root->right = rotateRight(root->right);
        root = rotateLeft(root);
    }
    return root;
}

这里值得注意点是，删除代码处理度为2的点使用了节点替换的思想，和之前的一边子树嫁接到另外一棵子树最小或最大值方向的方案不同。嫁接方案会大面积改变树的结构，而替换方案很少改变结构，对于代码的实现会容易很多。

代码中替换删除采取的是将右子树最小节点和根节点替换，然后剪切掉已经被替换到枝叶上的原根节点。这个变动最多只可能发生一层树的变动，所以调整幅度小很多，而之前的嫁接方案，会让整棵树嫁接到一个节点上，如果树很庞大，那么会导致出现很繁琐的调整。

红黑树

在了解红黑树之前，已经谈论了AVL树，但是AVL树看似似乎很完美，但是实际上依旧存在一个缺陷，在某些情况下（比如所有数据都是顺序插入），AVL树会高频调整以维护树的结构，从而导致大量的时间浪费在树的维护上。为了解决这个问题，人们开始寻找另外一种调整策略，以平衡查询效率和树的维护效率之间找到一个平衡点，在这个大前提下红黑树应运而生。

红黑树不同于AVL树，它没有近乎严苛的平衡结构条件，而是使用了更加宽松的条件——最深节点的高度最高不能超过最浅节点高度的2倍。

红黑树的特性有四个，也被简化为口诀：

• 左根右：由于红黑树是基于二叉搜索树发展而来，所以它满足二叉搜索树的左节点小于右节点的性质
• 根叶黑：根节点和叶子节点只能是黑色，要注意的是，这个叶子节点指的是空节点，而不是常规意义上的度为0的节点。
• 不红红：相邻的节点之间不能同时出现两个红色节点（但是允许出现两个黑色节点）
• 黑路同：从根节点出发到每个叶子节点之间经过的黑色节点的数量是相同的。

插入

红黑树的插入思路也是与AVL树一致，主要分为三个阶段——查找、插入、调整。同时最重要最核心的也是调整阶段。

红黑树的调整策略也是围绕红黑树的性质诞生的，主要有几种调整策略：

1、默认插入的节点颜色为红色

在正常情况下，默认插入节点是可以为红色节点和黑色节点的，但是红色节点更优所以普遍采用默认红色节点插入，以下可以进行分析。

首先，如果插入的是黑色节点，那么一定会违反红黑树的黑路同性质，接下来就一定需要进行红黑树调整。

反观插入红色节点，则可能违反根叶黑和不红红两个性质，但是当在度为0的黑色节点上插入到时候，红黑树不需要任何调整。而且即便违反了性质，调整起来也要比违反黑路同这样整棵树变动的调整方便得多。所以相比之下默认红色节点更加合适。

2、三类情况调整红黑树

• 情况1：插入节点是根节点
• 情况2：插入节点的叔叔是红色节点
• 情况3：插入节点的叔叔是黑色节点

与AVL树关注高度不同，红黑树引入了一个重要的角色就是叔叔，也就是父亲节点的兄弟节点。

情况1很好解决，只需要在插入后将节点颜色改变为黑色。

情况2已经开始变得复杂了，但是主要考虑的是颜色的变化。当发现插入节点的颜色与父亲节点违反了不红红特性，那么就需要将父亲和叔叔节点以及祖父节点的颜色反转，反转之后再将把祖父节点看作插入节点，如果也出现不红红且叔叔为红色，也将其父亲叔叔和祖父也反转。当然如果向上遍历的过程出现了根节点那么就停止，并且保证根节点为黑色。

核心点1：为什么要调整颜色，这样调整颜色难道不会影响其他子树的颜色排布吗？

出现颜色调整的原因是违反了不红红性质，最让初学者不解的就是这种调整为什么不会影响到其他的颜色排布。

首先，添加红色节点是不会影响到黑路同性质的，因为并没有额外的黑色节点引入。所以这个调整的主要思想是将红色节点插入后重新调整为黑红相间的结构。以情况2为例，10、20、30发生了颜色反转，但是仔细想一想思路，10和30都是20的孩子，本质上可以展开为 20(黑)->10(红) 和20(黑)->30(红)。黑红交换颜色后是20(红)->10(黑) 和20(红)->30(黑)，而20是同一个节点，也就是说变色只不过是两个节点颜色交换顺序，而10如果存在孩子，那么只可能是黑色，那么10变成黑色后，黑色相邻也是满足性质的。而且如果走10的子孩子这一条路，如果之前是黑->红->黑，那么现在变成红->黑->黑，本质上不会对树结构有影响。

而对于根节点的位置会被根叶黑性质纠正，这个也不会影响到整体，因为所有的路径起始点都是根节点，根节点是什么即便应该为红色但是被强制反转成黑色也无妨，因为所有路线增加一个黑节点不影响黑路同性质

情况3：这是最复杂的一种情况，它涉及到了旋转操作，这个操作和AVL中的四种旋转类似,也是[LL型 RR型 LR型 RL型]四种类型。不过与之不同的是，增加了变色这一操作。

首先是LL型，这里的例子使用了一个比较特殊的案例，因为很多常常忽略了NULL节点是黑色的，这里的属叔叔节点本质上是黑色的。

在这个流程中最需要重点关注的是祖父节点，其次为旋转节点，在旋转完成后将这两个节点进行变色。

LR型的作为复杂类型的旋转，需要先旋转左子树，在这个过程完成后成为LL型时才开始考虑变色问题，和LL型一样，先看祖父节点再看旋转点，最后两者进行变色操作。

RR型和LL型一模一样，只是方向相反，同时变色的逻辑依旧是先确认祖父节点再确认旋转节点

这个旋转操作和LR型类似，同时变色也和LR型一样，当RL型转换为RR型开始才考虑变色节点。

核心点2：为什么要进行旋转，而不能像情况2一样进行变色调整呢？

用叶子节点的位置做例子分析

首先第一点，先分析发生旋转的情况。插入的是红色节点，那么父亲节点一定是红色节点，而不违反不红红性质，祖父节点一定是黑色节点。也就是说，发生旋转情况的时候，叔叔节点和祖父节点一定是黑色。

在这个情况下如果按照情况2来变色，就会导致叔叔节点和祖父节点反转成红色从而破坏不红红性质，此外叔叔节点的路径同时会导致失去一个黑色节点，又违反了黑路同性质。为了调整一个结构又多出两个破坏结构的情况，显然是不理智的，所以需要使用另外一个调整思路。

整体的思路思考:

变色调整的思想是将一条路上的颜色往底层挪动一位，这样就相当于把插入的红色一层层往上传递交给交给根节点处理，因为根节点的被所有节点继承，红色节点传递上来会直接被根叶黑性质抹杀掉，从而维持树的结构。不过很多情况下，路径中都存在相邻黑色节点，而他们能直接处理这个传递上来的红色节点。不过它只适用于叔父均为同色，而异色一旦反转，则必定导致触犯黑路同的规则，这个规则的触发就意味着需要进行节点的调整，而不是杀掉一个红色节点这么简单。

而旋转调整的核心思想则更加粗暴，由于无法将颜色传递到根节点抹杀，那么就直接把多出的红色节点插入到叔叔路径的一边，至于为什么可以插入到另外一边，主要原因是发生旋转调整的前提中，叔叔子树和祖父子树一定是两个相邻的黑色节点。详情证明在核心点3中有提到。当然也不是简单的丢过去，同时还会使用旋转维护树的结构，以防树出现失衡。

核心点3：为什么情况3不需要像情况2旋转完成一次后接着回溯调整？

首先，这里有一个易错的点：情况3不需要回溯调整，但是情况2回溯调整是有可能触发情况3的。

现在仔细分析一下出现情况3在时候，具有普遍性的局部的红黑树子树是什么样子。

已知一个叔叔节点一定是黑色，父亲节点一定是红色插入节点位置一定是红色。（注意，由于是普适性，所以以最特性的情况——也就是经过一次情况2调整之后的样子为例）。由于在插入前红黑树一定是遵守规则的，所以此时的祖父节点不可能是红色（不然会与父亲节点冲突），可以得出祖父节点一定是黑色，于是可以得出一个具有普适性的模型：

LL型是RR型的镜像，原理一致。而RR型的基础模型旋转，本质上是根节点变成左孩子右孩子变成根节点。

这样的操作会导致违反黑路同性质，但是接下来的一步至关重要，那就是将新左孩子和根节点颜色互换。

所有最后的结果可以看到旋转之后的根节点一定是黑色，同理RL型模型：

LR型模型和RL型模型是镜像。只分析RL模型，会发现首次旋转的目标是将模型改变为RR型，而这个旋转是发生在两个红色节点之间的，所以对于祖父节点来说，不管如何旋转，始终右孩子都是一个红色节点。而此前所说的祖先节点和旋转中心节点交换颜色，也可以说是各自分别变色，因为不可能出现同色情况。

之后就会转变为RR型，所以最终的分析可以知道，只要是触发了情况3变换，变换结束后的根节点一定是黑色，而又可以知道黑色节点是可以相邻的，所以情况3变换是不可能触发回溯的，一次红黑树调整中最多只会发生一次情况3调整。

代码示例

前置代码

typedef enum{
    RED,
    BLACK
}TreeColor;
//树的定义
typedef struct Node
{
    int data;//树的数据
    TreeColor treeColor;//节点颜色
    struct Node* left;//左孩子
    struct Node* right;//右孩子
    struct Node* parent;//父亲节点
}Node;
//创建节点
Node* createNode(int data){
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->treeColor = RED;//默认为红色节点
    temp->left = NULL;
    temp->right = NULL;
    temp->parent = NULL;
    return temp;
}
//颜色反转
void colorReversal(Node* node){
    if(node == NULL) return;
    node->treeColor = ( node->treeColor == RED ? BLACK : RED );
}
//返回树的根节点
Node* getRoot(Node* node){
    if(node == NULL) return NULL;
    while(node->parent != NULL){
        node = node->parent;
    }
    return node;
}
//获取叔叔节点
Node* getUncleNode(Node* node){
    //检查节点当前节点，父亲节点，爷爷节点是否存在，如果有一个不存在则返回
    if (node == NULL || node->parent == NULL || node->parent->parent == NULL) return NULL;
    Node* father = node->parent;//获取父亲节点
    Node* ancestor = node->parent->parent;//获取祖先节点
    return ancestor->left != father ? father : ancestor->right;//返回叔叔节点
}
//返回节点的叔叔的颜色
TreeColor uncleColor(Node* node){
    Node* temp = getUncleNode(node);//获取叔叔节点
    if(temp == NULL)
        return BLACK;
    else
        return temp->treeColor;
}

旋转调整

//左旋
Node* rotateLeft(Node* root){
    //根节点为NULL则直接退出
    if(root == NULL) return NULL;
    //创建一个新的根节点
    Node* newRoot = root->right;//新根节点不可能出现NULL情况
    //更新新根节点父亲
    newRoot->parent = root->parent;
    //调整旧右孩子左节点的父亲
    root->right = newRoot->left;
    if(newRoot->left != NULL){
        newRoot->left->parent = root;
    }
    //调整旧根节点父亲
    newRoot->left = root;
    root->parent = newRoot;
    return newRoot;
}
//右旋
Node* rotateRight(Node* root){
    //根节点为NULL则直接退出
    if(root == NULL) return NULL;
    Node* newRoot = root->left;//新根节点不可能出现NULL情况
    //更新新根节点父亲
    newRoot->parent = root->parent;
    //调整旧左孩子右节点的父亲
    root->left = newRoot->right;
    if(newRoot->right != NULL){
        newRoot->right->parent = root;
    }
    //调整旧根节点父亲
    newRoot->right = root;
    root->parent = newRoot;
    return newRoot;
}
//对一棵子树进行旋转，并返回旋转后的新根节点
Node* balance(Node* node){
    //获取父亲节点
    Node* father = node->parent;
    //获取祖先节点
    Node* ancestor = node->parent->parent;
    //旋转中心
    Node* rotate_center = NULL;
    //LL型
    if(father == ancestor->left && node == father->left){
        //旋转并更新旋转中心
        rotate_center = rotateRight(ancestor);     
    }
    //RR型
    else if(father == ancestor->right && node == father->right){
        //旋转并更新旋转中心
        rotate_center = rotateLeft(ancestor);
    }
    //LR型
    else if(father == ancestor->left && node == father->right){
        //先旋转子树
        ancestor->left = rotateLeft(ancestor->left);
        rotate_center = rotateRight(ancestor);
    }
    //RL型
    else if(father == ancestor->right && node == father->left){
        //先旋转子树
        ancestor->right = rotateRight(ancestor->right);
        rotate_center = rotateLeft(ancestor);
    }
    //祖先和旋转中心变色
    colorReversal(ancestor);
    colorReversal(rotate_center);
    return rotate_center;
}

//旋转调整,输入插入节点地址，返回根节点
Node* rotateAdjustment(Node* node){
    //如果节点为空、或父亲节点为空、或祖先节点为空，则不满足调整前提
    if(node == NULL || node->parent == NULL || node->parent->parent == NULL){
        return getRoot(node);//直接返回树的根节点
    }
    //获取祖先节点的父亲节点，用于接收旋转之后的子树的地址
    Node* root = node->parent->parent->parent;
    //如果祖先节点的父亲节点存在，那么意味着调整的树局部树
    if(root != NULL){
        if(root->left == node->parent->parent){
            root->left = balance(node);
        }else{
            root->right = balance(node);
        }
        //调整完成，寻找这棵树的根节点并返回
        return getRoot(node);
    }
    //如果祖先节点的父亲节点不存在，则意味着调整的是整棵树
    else{
        //调整的结果就是这棵树的新根节点，直接返回
        return balance(node);
    }
}

变色调整

//变色调整，输入插入节点地址，返回根节点
Node* colorAdjustment(Node* node){
    if(node == NULL) return NULL;
    //没有遍历到根节点，且依旧满足调整前提
    while(node->parent != NULL && node->parent->parent != NULL  && node->parent->treeColor == RED){
        /*检查调整类型*/
        //如果为变色调整
        if(uncleColor(node) == RED){
            //父亲节点变色
            colorReversal(node->parent);
            //爷爷节点变色
            colorReversal(node->parent->parent);
            //叔叔节点变色
            colorReversal(getUncleNode(node));
            //更新node
            node = node->parent->parent;
        }
        //如果为旋转调整
        else{
            return rotateAdjustment(node); 
        }
    }
    //如果遍历到了根节点，则强行变黑
    if(node->parent == NULL){
        node->treeColor = BLACK;
        return node;
    }
    //返回根节点
    return getRoot(node);
}

综合插入函数

//在红黑树末端的对应位置添加一个节点，并且返回这个新节点的地址
Node* RBTree_addNodeAtLocation(Node* root,int data){
    if(root == NULL) return NULL;
    //查找位置
    Node* cur = root;
    Node* parent = NULL;
    //遍历红黑树
    while (cur != NULL) {
        parent = cur;
        //如果数据小于当前节点则往左遍历
        if (data < cur->data) {
            cur = cur->left;
        } 
        //如果数据大于当前节点则往右遍历
        else if (data > cur->data) {
            cur = cur->right;
        } 
        //如果数据等于当前节点则退出
        else {
            return NULL; // 节点已存在
        }
    }
    //创建一个新节点
    Node* temp = createNode(data);
    if (temp == NULL) return NULL;//创建失败则退出
    //判断应该左插还是右插
    temp->parent = parent;
    if (data < parent->data) {
        parent->left = temp;//左插
    } else {
        parent->right = temp;//右插
    }
    //返回节点地址
    return temp;
}
//综合插入函数入口
Node* insert(Node* root,int data){
    /*树没有节点*/
    if(root == NULL){
        root = createNode(data);//添加一个新节点
        root->treeColor = BLACK;//将节点变为黑色
        return root;
    }

    /*树有节点*/
    //先在树的对应的位置添加节点，获取这个节点的地址
    Node* cur = RBTree_addNodeAtLocation(root,data);
    //插入失败或者已经存在节点则返回
    if(cur == NULL) return root;

    /*调整树结构*/
    //检查树是否满足调整前提
    if(cur->parent->parent == NULL || cur->parent->treeColor != RED){
        //树的该路径只有两层，或者父亲节点不是红色，则不满足调整的前提
        return root;
    }

    /*检查调整类型*/
    //叔叔节点为红色，则进行变色调整
    if(uncleColor(cur) == RED){
        root = colorAdjustment(cur);
    }
    //叔叔节点为黑色，则进行旋转调整
    else{
        root = rotateAdjustment(cur);
    }
    return root;
}

在这个代码中，我完全避免了使用递归的方式实现，原因有几点：

• 第一：是递归的数据主要是让树相邻的两个节点直接传递数据，而红黑树设涉及了祖先叔叔节点，处理相对麻烦。
• 第二：是在实际代码中，能不用递归就不要使用递归，递归虽然在很多场合能大幅度减小代码的复杂度，但是递归过深会大幅度占用系统栈，甚至栈溢出导致程序崩溃。
• 第三：实际开发中，红黑树的使用范围远大于AVL树，虽然AVL树搜索效率略高于红黑树，但是其频繁的调整反而浪费很多的资源。AVL树以介绍为主，所以使用了递归讲解，而红黑树可以实际开发，所以偏向实用性为主。

删除

红黑树的删除操作也是红黑树最复杂的操作。不过核心原理依旧不变——维护红黑树的四条性质。其中最容易违反的是不红红和黑路同。对于树的调整，算法研究者给出了两个类型的操作方式——变色和旋转。

对于变色，这个是一个简单的操作，但是它需要一个重要的前提，那就是必需要求存在足够的节点。比如如果一条路缺少一个黑色节点，那么就可以牺牲一个红色节点补全这个黑色节点。同样的如果多余了一个黑色节点则可以将一个黑色节点转化为红色节点重新平衡。但是必须存在一个大前提：必须存在多余的节点。

而旋转操作则是补全变色操作大前提的一种方案。如果一条路径不存在一个节点，那么就从另外一条路匀一个节点到这条路上以满足实现变色操作。

但是实际上，旋转这个行为会带来理解障碍，而换一个概念图会清晰很多。

当然我这里只是一个基本的处理逻辑，就是当节点不够时可以采纳的处理思路，但是在实际实现肯定不能简单地这样做，因为还需要涉及到左根右性质，而旋转操作能相较于平衡操作的优势就体现在了可以维持住树本来的左根右性质。

重新回顾了前置的思想，接下来对于红黑树的处理就容易多了。

首先是删除框架，和之前的各种类型的树一样，经历查找、删除、调整三个过程。这里回顾一下删除操作。删除分为三种情况，依据节点度数分为0、1、2三种，红黑树也遵循这个操作流程。

度为2

度为2的情况比较复杂，可能会导致大量的树结构遭受破坏，所以为了应对这个情况所采取的策略是转移。

节点转移到思路常常是将当前要删除的节点和它的前驱或者后继节点交换。由于二叉树的性质，前驱和后继节点都是度为0或1的叶子节点，通常也是对树整体结构影响最小的节点。两者交换位置后，接下来就可以当做叶子节点删除，避免了之前可能发生的大规模结构变动。

度为1

度为1是最简单的情况，由于不红红和黑路同的约束，只可能出现以下情况：

以下需要介绍几个结论：

度为1的节点一定是黑色

证明：如果度为1的节点是红色，那么它的子节点一定是黑色否则会违反不红红，但是如果存在了一个黑色节点，那么另外一个孩子就不能是空节点，否则就违反了黑路同。而出现两个黑节点，那么度就不能为1而是2。可证，度为1的节点一定是黑色节点。

度为1的节点的孩子一定是红色

证明：由于度为1，所以必须存在且仅能存在一个孩子，如果孩子是黑色则违反黑路同，所以只能是红色节点

调整思路：

还是之前提到的核心——所有调整的最终目的是为了维护红黑树的性质不被破坏。

当节点被删除后，就只剩下红色节点了，此时红色节点取代之前黑色节点的位置。观察后会发现，这条路径的黑色节点减少，那么就意味着必定违反了黑路同性质。所以当务之急是如何产生一个黑色节点。先朝着变色的思路思考，发现存在一个多余红色，那么只需要将红色节点变成黑色节点就能重新平衡红黑树。

于是就有了以下结论：

当删除的节点度为1时，孩子节点取代父亲节点的位置，并且颜色变成黑色。

度为0

度为0的删除操作简单，但是调整操作却很复杂。不过相当于直接删除度为2的节点还是要方便很多，因为度为2的节点如果直接删除，那么不仅调整复杂，删除也很复杂。

删除节点是红色

这类情况很简单，因为删除一个红色的度为0的节点不会出现任何违反性质的可能，所以直接删除便可，无需调整。

删除节点是黑色

这个类别逐渐变得复杂，它也细分为几个小类。

情况1：兄弟节点为黑色

这个情况也比较复杂，首先分为了2个大类——兄弟节点是否存在红色节点。这两个情况并不是空穴来风，它的设计思路依旧遵循变色和旋转。如果存在红色节点，那么就意味着有多余的节点可以在子树内部，流动，就给了变色足够的前置条件。而如果没有红色节点就意味着无法变色，那么只能将思路上移到上一级子树观察是否存在红色节点进行操作。

情况1.1：兄弟节点中存在至少一个红色节点

在模型中，白色节点代表着其颜色不定，可能会出现红色也可能会出现黑色，但是在这个模型中这个颜色并不存在影响，后面会解释。而红色节点的位置并没有固定，它还可能存在与右子树。所以它的旋转方式也分为LL型、RR型、LR型和RL型。

情况1.1.1：LL型与RR型

先谈谈LL型，图示如下

LL型有两种情况，但是都必须有一个左孩子节点。首先要明白整个操作的目的是让右子树多出一个可以用来变色的节点，那么现在所做的目的就是将兄弟节点的左孩子转移到右子树上。于是可以要将红色上移。以图-LL型中的右图为例：

这里要声明一下，动画表达的意思并移动的不是节点本身，而是节点中存储的颜色。接下来就是需要将节点变色旋转，成为一个新的局部子树，如图：

在旋转中有一个特殊的节点，那就是图中的白色的节点。在通常情况下需要考虑新子树根节点的颜色和与它的父亲节点的兼容性，但是在这个旋转中并不需要，因为在整个过程中可以清晰看到，这个白色节点是完全不参与旋转的，它始终处于根节点的位置。（还是要注意，图中变色是节点交换颜色，不是交换节点本身。）

同样的RR型和LL型完全一致，不过是镜像操作而已，而RR型也是以下两种情况：

情况1.1.1：LR型与RL型

同样的LR型和RL型也是镜像操作，所以接下来讲解均以LR型为例子。

LR型的特点是兄弟节点的只有左孩子为红色。和之前的思路一样，这个操作的核心点就是要将这个多余的红色转移到需要黑色节点的右子树上，不过它不能直接上移颜色，因为这会导致左根右的性质被破坏，如下图所示：

在这个错误示范中，可清晰地看到由于红色节点是右孩子的缘故，它在旋转地过程中必然变成了左子树，显然会破坏树的性质，即便是红色节点直接嫁接到右子树的位置也存在问题。为此必须要有一个新的思路，那就是通过旋转先将兄弟节点及其子树转变成某种合理的结构为二次旋转做铺垫，所以最终的思路是将LR型转化为LL型，再处理LL型。

将目光看到兄弟节点，兄弟节点与孩子左旋，则可以将孩子节点转变为左孩子：

经历一次旋转后，现在都树的模型符合LL型，然后进行交换、旋转再变色的操作（变色步骤的位置不需要固定），同样是不需要考虑兼容性变色，因为白色节点始终是根节点。即便颜色交换到了8的位置，但是8作为新的根节点却保留了白色节点的特性，所以不需要考虑任何有关兼容性的情况。

所以可以得出以下结论：

当兄弟节点存在红色节点时，需要选择匹配LL型、RR型、LR型和RL型进行变色旋转。当处于LL或者RR型时，分别需要将左孩子或者右孩子的颜色沿着路径交换到原始根节点，然后变成黑色进行右旋或者左旋。如果是LR型或者RL型则需要将模型转换为LL型或者RR型，然后按照LL型或者RR型处理。

情况1.2：兄弟节点不存在红色节点

不存在红色节点的情况相对来说比较难以处理，因为没有多余的节点补充被删除的黑色节点，而且不能经过简单的直接旋转解决问题。

不过有一点值得关注，在这个模型中兄弟节点是不存在任何孩子节点的（NULL黑节点除外），那么也就意味着如果删除了节点首先考虑的是变色方案。

在这个动图中可以明显的看到，我们主动将兄弟节点变红，让整棵树重新取得了平衡，但是如果这棵树是完整的红黑树那么直接修改根节点为黑色就完成了删除，可如果这是局部子树那么就会出现问题。当祖先节点是红色的时候，此时祖先节点改变颜色为黑色，那么能解决子树共同失去一个黑色节点的难题。但如果祖先节点本来就是黑色，那么就不能变色补充黑色节点。

那么该如何补充黑色节点呢？

既然这棵子树无法自己调整，那么就借助外力。将目标放在祖先节点上，并且将祖先节点的子树融合看作一个节点，然后观察兄弟节点的颜色，此时就变成了一种新的情况——原子树看作了一个需要等待调整的整体节点，就类比成了刚才删除了这个节点（整个子树），如何将这个它所在的更高维度的树进行调整。随后重新进行判断兄弟节点的颜色，根据颜色进行不同类型的调整。如图所示：

所以得出来了一个结论：

当兄弟节点不存在红色孩子时，将兄弟节点变成红色，然后目标转变为祖先节点，如果祖先节点是红色或者是整棵树的根节点，那么就直接变成黑色。如果祖先节点是黑色且不是整颗树的根节点，那么观察祖先节点的兄弟的颜色（#兄弟节点为红色跳转）节点分类处理，并且以此上推直到调整完成或者遇到根节点。

情况2：兄弟节点为红色

兄弟节点为红色时，有一个基本模型：

这个模型同样是基于不红红和黑路同推理出来的，每个叶子节点的位置还可以添加红色孩子。

当目标节点删除后就少了一个黑节点，这条路径就必然违反了黑路同性质。依旧使用之前的思路，先思考变色操作创造一个黑色节点，不过这条路径显然不可能，因为该路径不存在任何节点了。那么接下来就要思考另外一条路——旋转。

通过观察，会发现这个类型属于LL型或者RR型，那么就能通过右旋和左旋地方式将节点匀一个到目标路径，以左图为例，通过旋操作后会如下图所示：

这个旋转分为两步，第一是将兄弟节点和祖先节点变色，然后再进行右旋操作。这里为什么要这样想呢？这同样涉及到维护性质，如果只看图-兄弟节点为红色的基本模型左图的左子树，旋转尽可能不改动左子树，所以那么就需要变色维持左子树的黑色节点的数量，由于右边会转移一个右下角的黑色节点过去，那么总计会出现三个黑色节点，所以需要一个红色节点进行充填，对旋转之后的结果预留修改的位置。

旋转完成后，分析图-旋转中间步骤1 右图的右子树，以红节点为中心，会发现少了一个黑色节点。仔细但是可以看作一个新的状态进行分析，右子树恰好是一个刚删除了一个节点的状态：

那么就可以根据这个状态来进行一个新的转换，进入另外一个大类情况——观察这个不存在的节点的兄弟节点。如果兄弟节点是黑色则进行黑色调整：#兄弟节点为黑色（跳转）

还可能存在其他特殊情况：

同样也是按照兄弟节点观察，并分类进行调整。

于是就有了以下结论：

当兄弟节点是红色时，将红色传递到根节点，然后根据情况进行左旋或者右旋。然后将视角锁定在之前的被删除子树，通过被添加过来的节点的颜色，继续进行新一轮的调整操作。

完整的红黑树代码示例：

基础前置：

//左旋
Node* rotateLeft(Node* root){
    //根节点为NULL则直接退出
    if(root == NULL) return NULL;
    //创建一个新的根节点
    Node* newRoot = root->right;//新根节点不可能出现NULL情况
    //更新新根节点父亲
    newRoot->parent = root->parent;
    //调整旧右孩子左节点的父亲
    root->right = newRoot->left;
    if(newRoot->left != NULL){
        newRoot->left->parent = root;
    }
    //调整旧根节点父亲
    newRoot->left = root;
    root->parent = newRoot;
    return newRoot;
}
//右旋
Node* rotateRight(Node* root){
    //根节点为NULL则直接退出
    if(root == NULL) return NULL;
    Node* newRoot = root->left;//新根节点不可能出现NULL情况
    //更新新根节点父亲
    newRoot->parent = root->parent;
    //调整旧左孩子右节点的父亲
    root->left = newRoot->right;
    if(newRoot->right != NULL){
        newRoot->right->parent = root;
    }
    //调整旧根节点父亲
    newRoot->right = root;
    root->parent = newRoot;
    return newRoot;
}
//返回树的根节点
Node* getRoot(Node* node){
    if(node == NULL) return NULL;
    while(node->parent != NULL){
        node = node->parent;
    }
    return node;
}
//获取兄弟节点
Node* brotherNode(Node* node){
    //校验父亲节点的正确性
    if(node->parent == NULL) return NULL;
    //查询兄弟节点
    if(node != node->parent->left){
        return node->parent->left;
    }
    else{
        return node->parent->right;
    }
}
//获取节点颜色
TreeColor NodeColor(Node* node){
    return (node == NULL) ? BLACK : node->treeColor;
}

节点查找

/*第一部分：节点查找*/
//后继交换函数
Node* HandleNodeWithTwoChildren(Node* node){
    //校验
    if(node == NULL) return NULL;
    //查找
    Node* temp = node;
    node = node->right;
    while(node->left != NULL){
        node = node->left;
    }
    temp->data = node->data;
    return node;
}
//寻找删除节点
Node* FindTargetNode(Node* root, int data){
    //判断红黑树是否存在
    if(root == NULL) return NULL;
    //声明一个用于遍历的变量
    Node* cur = root;
    //遍历
    while(cur != NULL){
        //如果目标节点小于当前节点的值,那么往左遍历
        if(data < cur->data){
            cur = cur->left;
        }
        //如果目标节点大于当前节点的值,那么往右遍历
        else if(data > cur->data){
            cur = cur->right;
        }
        //找到目标节点
        else {
            //如果度为2则要进行额外处理
            if(cur->left != NULL && cur->right != NULL){
                cur = HandleNodeWithTwoChildren(cur);
            }
            //返回找到的节点
            return cur;
        }
    }
    //没有找到目标节点
    return NULL;
}

删除与调整

/*第二部分：删除及其调整*/
//删除度为1的点
Node* DeleteNodeWithOneChild(Node* target){
    //获取孩子节点
    Node* child = (target->left != NULL) ? (target->left) : (target->right);
    //孩子节点变黑
    child->treeColor = BLACK;
    //如果删除的是根节点
    if(target->parent == NULL){
        child->parent = NULL;
        free(target);
        return child;
    }
    //如果删除的节点是普通节点
    child->parent = target->parent;
    //如果target是父亲节点的左孩子
    if(target == target->parent->left){
        target->parent->left = child;
    }
    //如果target是父亲节点的右孩子
    else{
        target->parent->right = child;
    }
    free(target);
    return child;
}

//度为0的大类：如果删除节点是红色
Node* DeleteRedLeafNode(Node* target){
    Node* father = target->parent;
    (father->left == target) ? (father->left = NULL) : (father->right = NULL);
    free(target);
    return father;
}

//如果兄弟节点是黑色并且存在红色节点（返回调整后的局部子树根节点）
Node* DeleteWhenHasRedNephews(Node* brother){
    //获取祖先节点
    Node* ancester = brother->parent->parent;
    //获取父亲节点
    Node* father = brother->parent;
    Node* father_copy = father;

    //LL型
    if(brother == father->left && NodeColor(brother->left) == RED){
        //颜色修改
        brother->left->treeColor = brother->treeColor;
        brother->treeColor = father->treeColor;
        father->treeColor = BLACK;
        //旋转
        father = rotateRight(father);
    }
    //RR型
    else if(brother == father->right && NodeColor(brother->right) == RED){
        //颜色修改
        brother->right->treeColor = brother->treeColor;
        brother->treeColor = father->treeColor;
        father->treeColor = BLACK;
        //旋转
        father = rotateLeft(father);
    }
    //LR型
    else if(brother == father->left && NodeColor(brother->left) == BLACK){
        //首次调整，转化为LL型
        brother = rotateLeft(brother);
        father->left = brother;
        //二次旋转
        father = rotateRight(father);
    }
    //RL型
    else if(brother == father->right && NodeColor(brother->right) == BLACK){
        //首次调整，转化为RR型
        brother = rotateRight(brother);
        father->right = brother;
        //二次旋转
        father = rotateLeft(father);
    }
    //将新father节点与祖先节点连接起来。
    //如果祖先不存在，则直接返回
    if(ancester == NULL){
        return father;
    }
    //如果父亲节点是祖先的左孩子
    if(ancester->left == father_copy){
        ancester->left = father;
    }
    //如果父亲节点是祖先的右孩子
    else{
        ancester->right = father;
    }
    return father;
}

//如果删除的是黑色节点，且兄弟为红色（返回调整后的局部子树根节点）
Node* DeleteBlackLeafNodeWithRedSibling(Node* brother){
    //声明变量
    Node* father = brother->parent;
    Node* ancestor = father->parent;
    Node* resultNode = father;
    //颜色交换
    TreeColor temp = brother->treeColor;
    brother->treeColor = father->treeColor;
    father->treeColor = temp;

    //旋转调整
    if(brother == father->left){//右旋
        father = rotateRight(father);
    }
    else if(brother == father->right){//左旋
        father = rotateLeft(father);
    }
    //父亲节点是整棵树的根节点
    if(ancestor == NULL){
        return resultNode;
    }
    //更新祖先节点与父亲节点的关系
    (ancestor->left == resultNode) ? (ancestor->left = father) : (ancestor->right = father);
    return resultNode;
}

删除调用接口

//删除函数
Node* TreeDelete(Node* root, int data){
    //获取目标节点
    Node* cur = FindTargetNode(root,data);
    if(cur == NULL) return root;//节点查找出错
    //根据度的情况分类处理
    //如果度为0
    if(cur->left == NULL && cur->right == NULL){
        //如果删除的是根节点
        if(cur->parent == NULL){
            free(cur);
            return NULL;
        }
        //观察删除的节点是否为红色，如果删除节点是红色
        if(cur->treeColor == RED){
            cur = DeleteRedLeafNode(cur);
            return getRoot(cur);
        }
        //如果删除节点是黑色
        //获取兄弟节点
        Node* brother = brotherNode(cur);
        //删除操作
        (cur == cur->parent->left) ? (cur->parent->left = NULL) : (cur->parent->right = NULL);
        free(cur);
        cur = NULL;
        //调整
        while(1){
            //观察兄弟节点是否为黑色，如果为黑色
            if(NodeColor(brother) == BLACK){
                //判断兄弟节点是否存在红色孩子，如果不存在红色
                if(NodeColor(brother->left) == BLACK && NodeColor(brother->right) == BLACK){
                    brother->treeColor = RED;//兄弟节点变成红色
                    //检查父亲节点是否为红色
                    if(NodeColor(brother->parent) == RED){
                        brother->parent->treeColor = BLACK;//父亲节点变黑
                        return getRoot(brother);
                    }
                    //如果父亲节点为黑色，并且是整个红黑树的根节点时
                    else if(NodeColor(brother->parent) == BLACK && brother->parent->parent == NULL){
                        return brother->parent;//由于父亲节点是根节点，直接返回
                    }
                    //如果父亲节点为黑色，并且父亲节点之上存在更高维度的树
                    else{
                        //更新兄弟节点，注意点提升到更高层次的维度上
                        Node* father = brother->parent;
                        Node* ancestor = father->parent;
                        brother = father != ancestor->left ? ancestor->left : ancestor->right;
                    }
                }
                //如果为存在红色
                else{
                    //printf("我进入了0度无双黑的位置\n");
                    cur = DeleteWhenHasRedNephews(brother);
                    return getRoot(cur);
                }
            }
            //如果是红色
            else{
                Node*temp = DeleteBlackLeafNodeWithRedSibling(brother);
                brother = temp->left ? temp->left : temp->right;
            }
        }
    }
    //如果度为1
    else{
        cur = DeleteNodeWithOneChild(cur);
        return getRoot(cur);
    } 
}