红黑树(RBTree)

印象里面在数据查找当中，常见的数据结构有 红黑树、哈希表、b/b+树、跳表。

一、红黑树

1.1、应用场景

个人印象里面，在以下场景中使用较多：

• C++ STL中的map，set
• epoll底层数据结构之一
• Linux的进程调度(CFS)
• nginx的定时器管理
• 各种含有key,value的数据查找场景

1.2、定义

红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过2。

1.3、特性

• 每个节点都是红的或者黑的
• 根节点是黑的
• 每个叶子节点是黑的
• 如果一个节点是红的，则它的两个子节点都是黑的
• 对每个节点，从该节点到其子孙节点的所有路径上包含相同数量的黑节点------决定红黑树的高度
  

1.4、从根节点出发，最长路径最大能包含多少节点？

从根节点出发，红黑树的最短路径和最长路径的节点数差异是2倍。这意味着，如果最短路径包含n个节点，那么最长路径将包含最多2n-1个节点。

二、具体实操

2.1、如何定义红黑树?

typedef struct _rbtree_node{
    int key;
    void* value;

    struct _rbtree_node* left;
    struct _rbtree_node* right;

    struct _rbtree_node* parent;

    unsigned char color; // 0: red, 1: black
}rbtree_node;

// 叶子节点都是黑色的，可以定义为空节点，为了好判断，不能定义为NULL，否则是非法操作
typedef struct _rbtree{
    struct _rbtree_node* root;
    struct _rbtree_node* nil; // 叶子节点，黑色的空节点
    int size; // 树中节点的数量
}rbtree;

2.2、旋转：

• 红黑树性质被破坏的时候会发生旋转
  

void leftRotate(rbtree* tree, rbtree_node* x)
{
    rbtree_node* y = x->right; // 右子节点
    
    // 断x与y的父子关系
    x->right = y->left; // 让左子节点成为右子节点的父节点
    if(y->left != tree->nil) // 如果左子节点不是叶子节点，则更新父节点的指向
    {
        y->left->parent = x;
    }

    // 断x与x父节点的父子关系，并建立x父节点与y的父子关系
    y->parent = x->parent; // 让y的父节点指向x的父节点
    if(x->parent == tree->nil) // 如果x是根节点，则更新根节点的指向
    {
        tree->root = y;
    }else if(x == x->parent->left) // 如果x是其父节点的左子节点，则更新其父节点的左子节点
    {
        x->parent->left = y;
    }else // 如果x是其父节点的右子节点，则更新其父节点的右子节点
    {
        x->parent->right = y;
    }

    // 更新x与y的父子关系
    y->left = x; // 让x成为y的左子节点
    x->parent = y; // 更新父节点的指向
}

// 将左旋反过来，x变y，left变right，right变left
void rightRotate(rbtree* tree, rbtree_node* y)
{
    rbtree_node* x = y->left; // 左子节点
    
    // 断y与x的父子关系
    y->left = x->right; // 让右子节点成为左子节点的父节点
    if(x->right != tree->nil) // 如果右子节点不是叶子节点，则更新父节点的指向
    {
        x->right->parent = y;
    }

    // 断y与y父节点的父子关系，并建立y父节点与x的父子关系
    x->parent = y->parent; // 让x的父节点指向y的父节点
    if(y->parent == tree->nil) // 如果y是根节点，则更新根节点的指向
    {
        tree->root = x;
    }else if(y == y->parent->right) // 如果y是其父节点的右子节点，则更新其父节点的右子节点
    {
        y->parent->right = x;
    }else // 如果y是其父节点的左子节点，则更新其父节点的左子节点
    {
        y->parent->left = x;
    }

    // 更新y与x的父子关系
    x->right = y; // 让y成为x的右子节点
    y->parent = x; // 更新父节点的指向
}

2.3、插入：

• 插入节点默认为红色

void rbtree_insert(rbtree* tree, rbtree_node* node)
{
    rbtree_node* y = tree->nil;  // 记录x的父节点
    rbtree_node* x = tree->root; // 根节点

    // 找到插入的位置
    while(x != tree->nil) // 如果不是叶子节点，则继续查找
    {   
        y = x; // 记录父节点
        if(node->key < x->key) // 如果插入节点的键小于当前节点的键，则向左子节点查找
        {
            x = x->left;
        }else if(node->key > x->key) // 如果插入节点的键大于等于当前节点的键，则向右子节点查找
        {
            x = x->right;
        }else{      // 如果插入节点的键等于当前节点的键，则替换当前节点
            x->value = node->value;
        }
    }

    // 如果是空红黑树，则直接插入
    if(y == tree->nil) // 如果y是叶子节点，则直接插入
    {
        tree->root = node; // 更新根节点
    }else{
        if(y->key > node->key) // 如果插入节点的键小于父节点的键，则将插入节点设置为左子节点
        {
            y->left = node;
        }else // 如果插入节点的键大于父节点的键，则将插入节点设置为右子节点
        {
            y->right = node;
        }
    }

    node->parent = y; // 更新父节点

    node->left = tree->nil;
    node->right = tree->nil;
    node->color = 0 ; // 新插入的节点默认为红色，不改变黑高

    // 插入之后，进行旋转和变色
    insertFixup(tree, node);
}

以N-新节点，P-父节点，G-祖父节点，U-叔父节点的命名方式来描述插入之后的调整过程。

默认叶子节点不出现

// 插入之后的调整
void insertFixup(rbtree* tree, rbtree_node* node)
{
    rbtree_node* parent = node->parent;
    rbtree_node* grandparent = NULL;
    rbtree_node* uncle = NULL;
    // 如果节点本身是红色
    while(parent->color == 0) // 如果父节点是红色，那么祖父节点必是黑色，叔父节点可能是红色或黑色
    {
        grandparent = parent->parent; // 获取祖父节点
        if(parent == grandparent->left) // 如果父节点是其祖父节点的左子节点
        {
            uncle = grandparent->right; // 叔父节点
            // 情况2和3：叔父节点是红色
            if (uncle->color == 0)
            {
                parent->color = 1; // 将父节点变为黑色
                uncle->color = 1; // 将叔父节点变为黑色
                grandparent->color = 0; // 将祖父节点变为红色
                node = grandparent; // 继续向上调整
            }else // 叔父节点是黑色
            {
                // 情况4：N是P的左子节点(LL)
                if (node == parent->left)
                {
                    rightRotate(tree, grandparent); // 对祖父节点进行右旋
                    parent = node->parent; // 更新父节点
                }
                // 情况5：N是P的右子节点(LR)
                else
                {
                    leftRotate(tree, parent); // 对父节点进行左旋
                    parent = node->parent; // 更新父节点
                    rightRotate(tree, grandparent); // 对祖父节点进行右旋
                }

                parent->color = 1; // 将父节点变为黑色
                grandparent->color = 0; // 将祖父节点变为红色
                node = parent; // 继续向上调整
            }
        }else // 父节点是其祖父节点的右子节点
        {
            uncle = grandparent->left; // 获取叔父节点

            // 情况2和3：叔父节点是红色
            if (uncle->color == 0)
            {
                parent->color = 1; // 将父节点变为黑色
                uncle->color = 1; // 将叔父节点变为黑色
                grandparent->color = 0; // 将祖父节点变为红色
                node = grandparent; // 继续向上调整
            }
            else // 叔父节点是黑色
            {
                // 情况6：N是P的左子节点(RL)
                if (node == parent->left)
                {
                    rightRotate(tree, parent); // 对父节点进行右旋
                    parent = node->parent; // 更新父节点
                    leftRotate(tree, grandparent); // 对祖父节点进行左旋
                }
                // 情况7：N是P的右子节点(RR)
                else
                {
                    leftRotate(tree, grandparent); // 对祖父节点进行左旋
                    parent = node->parent; // 更新父节点
                }

                parent->color = 1; // 将父节点变为黑色
                grandparent->color = 0; // 将祖父节点变为红色
                node = parent; // 继续向上调整
            }
        }
    }
    tree->root->color = 1; // 将根节点变为黑色
}

三、问题

3.1、map为什么不用avl树?

AVL树是一种严格平衡的二叉树，要求每个节点的左右子树的高度最多相差1，在大量地进行插入和删除操作时，AVL树需要频繁地进行旋转来维持平衡状态，这会导致较高的时间复杂度。

而RB树（红黑树）是非严格的平衡二叉树，只要从根节点到叶子节点的最长路径不超过最短路径的2倍，那么就不用进行频繁地进行平衡调节，使得插入、删除、查找效率稳定在O(logn)级别。

Code
0vice·GitHub