从理论到实践：使用C语言构建红黑树的方法解析与代码原理解释

红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的

在这里插入图片描述

概念总结：
红黑树是二叉搜索树的升级，结点里面存放的成员col标记当前结点的颜色，它的最长路径最多是最短路径的二倍，红黑树通过各个结点着色方式的限制接近平衡二叉树，但是不同于AVL的是AVL是一颗高度平衡的二叉树，红黑树只是接近平衡

红黑树的性质

每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的，则它的两个孩子结点是黑色的对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

红黑树性质总结：

1、红黑树结点的颜色只能是红色或者黑色
2、红黑树根节点必须是黑色
3、红黑树并没有连续的红色结点
4、红黑树中从根到叶子的每一条路径都包含相同的黑色结点
5、叶子是黑色，表示空的位置

最长路径和最短路径概念：

最短路径：从根结点到叶子结点每一条路径的结点颜色都是黑色的不包含红色

最长路径：红黑交替，黑色结点和红色结点的个数相等

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

假设结点个数为N，那么最短路径就是logN，最长路径就是2 * logN，所有并不存在最长路径超过最短路径2倍的情况

红黑树的定义与树结构

//枚举红黑颜色
enum colour 
{
    RED,
    BLACK,
};
 
//定义红黑树结点结构
template<class K,class V>
struct RBTreeNode 
{
    //构造
    RBTreeNode(const pair<K, V>& kv = {0,0})
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        ,_col(BLACK)
    { }
    //定义三叉链
    RBTreeNode<K, V>* _left; //左孩子
    RBTreeNode<K, V>* _right;//右孩子
    RBTreeNode<K, V>* _parent;  //父亲
    pair<K, V> _kv;  //pair对象
    //节点的颜色
    colour _col;  //定义枚举变量
};
 
 
//定义红黑树
template<class K, class V>
class RBTree 
{
        typedef RBTreeNode<K, V> Node;
    public:
        //构造
        RBTree() 
            :_root(nullptr)
        {}
    private:
        Node* _root;  //定义树的根节点
};

免费讲解

插入

插入过程类似搜索树的插入，重要的是维护红黑树的性质

100

101

102

103

104

105

106

107

108

109

110

111

pair<Node*, bool> Insert(const pair<K, V>& kv)
{
    if (!_root) //空树处理
    {
        _root = new Node(kv);
        _root->_col = BLACK;
        return { _root, true };
    }
    //二叉搜索树的插入逻辑
    Node* cur = _root, * parent = nullptr;
    while (cur)
    {
        if (cur->_kv.first < kv.first)//插入结点比当前结点大 
        {
            parent = cur;
            cur = cur->_right; 
        }
        else if (cur->_kv.first > kv.first) //插入结点比当前结点小 
        {
            parent = cur;
            cur = cur->_left; 
        }
        else
        {
            return { cur, false }; //插入失败
        }
 
    }
    cur = new Node(kv);
    cur->_col = RED;  //新增结点颜色默认设置为RED
    //判断插入结点是否在parent的左边或者右边
    if (parent->_kv.first > kv.first)  //左边
    {
        parent->_left = cur;
        cur->_parent = parent;
    }
    else     //右边   
    {
        parent->_right = cur;
        cur->_parent = parent;
    }
     
    /* 红黑树性质处理：
        如果这棵树一开始是符合红黑树的性质，但在新增结点之后，
        导致失去了红黑树的性质，这里需要控制结点的颜色和限制
        每条路径上黑色结点的个数，以上情况都要处理
    */
 
    while (parent && parent->_col == RED) //父亲存在且父亲为红色
    {
        Node* grandfather = parent->_parent;  //祖父
        //父亲出现在祖父的左边需要考虑的情况
        if(parent == grandfather ->left)
        {
            //1、uncle存在，uncle为红色
            /*
               如果parent和uncle都存在并且都为红色这是情况一，
               需要将parent和uncle的颜色变成红色，祖父颜色变成黑色
               更新cur、parent、grandfather、uncle 继续向上调整
            */
     
     
            //2、uncle不存在
            /*  这里考虑两种旋转情况，直线单旋转，折线双旋
                /*
                    cur出现在parent的左边 ,右单旋转
                    经过右单旋后，parent去做树的根,祖父做为右子树
                    //调节结点颜色
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                */
                 
                /*
                    cur出现在parent的右边，左右双旋
                    经过双旋后，cur作为树的根，grandfather为右子树
                    调节结点颜色
                    cur->_col = BLACK;
                    grandfather->_col = RED;  
                */
            */ 
             
        }
        else  //父亲出现在祖父的右边
        {
            Node* uncle = grandfather->_left; //叔叔在左子树 
            /*
            情况一：叔叔存在，且叔叔和父亲都是红色，那么就需要将父亲
            和叔叔结点的颜色变成黑色，再将祖父的颜色变成红色，
            继续向上调整，更新孩子、父亲、祖父、叔叔的位置
            */
 
            /*
                情况二：叔叔不存在
                /*
                    1、新增结点出现在父亲的右边，直线情况，左单旋处理
                    旋转完后parent去做父亲的根，grandfather做父亲
                    的左子树
                            //调节颜色，根为黑，左右孩子为红
                    2、新增结点出现在父亲的左边，会出现折现的情况，
                    引发双旋，旋转完后，cur变成根，
                    parent和grandfaher去做cur的左右孩子
                           //调节颜色,根结点为黑，左右孩子为红
                */
            */  
        }
         
    }
 
    //如果父亲不存在为了保证根结点是黑色的，这里一定得将根结点处理为黑色
    _root->_col = BLACK;
}

免费讲解

新增结点插入后维护红黑树性质的主逻辑

//1、父亲一定存在的情况，叔叔存在/不存在 父亲叔叔结点颜色为红色
while (parent && parent->_col == RED) //父亲存在且父亲为红色
{
    Node* grandfather = parent->_parent;  //祖父
    //如果父亲和叔叔结点颜色都是红色
    if (parent == grandfather->_left)  
    {
        Node* uncle = grandfather->_right;  
        if (uncle && uncle->_col == RED)  //对应情况：uncle存在且为红
        {
            //处理：父亲和叔叔变成黑色，祖父变成红色，继续向上调整
            uncle->_col = parent->_col = BLACK; 
            grandfather->_col = RED;
 
            //向上调整
            cur = grandfather;  //调整孩子
            parent = cur->_parent;//调整父亲
             
        }
        else   //uncle不存在，uncle存在且为黑
        {
            //直线情况(cur在parent的左边)：只考虑单旋，以grandfather为旋转点进行右单旋转，
            //旋转完后将祖父的颜色变成红色，将父亲的颜色变成黑色
            if (parent->_left == cur) 
            {
                RotateR(grandfather);
                parent->_col = BLACK;
                grandfather->_col = RED;
            }
            else  //parent->_right == cur 
            {   
                //折线情况(cur在parent的右边)：这里会引发双旋
                RotateL(parent);  //以parent为旋转点进行左单旋
                RotateR(grandfather); //以grandfather为旋转点进行右单旋转
                //旋转完后cur会去做树的根，那么设置为黑色，
                //为了保证每条路径的黑色结点个数相同，grandfather结点颜色设置为红
                cur->_col = BLACK;
                grandfather->_col = RED;  //黑色   结点个数相同
            }
        }
    }
    else //父亲在右子树
    {
            Node* uncle = grandfather->_left; //叔叔在左子树 
            if (uncle&& uncle->_col == RED)  //情况一处理：叔叔存在，且叔叔的颜色是红色的（包含了父亲的颜色是红色的情况）
            {
                //根据情况一处理即可：叔叔和父亲变黑，
                //祖父变红(目的是为了每条路径的黑色结点个数相同)，继续向上
                cur = grandfather;  //孩子
                parent = cur->_parent;//父亲
                 
            }
            else //叔叔不存在 
            {
                if (cur == parent->_right)  //新增结点在父亲的右边，直线情况左单旋处理
                {
                    //左单旋转，以grandfather为旋转点，旋转完后parent去做新的根，grandfather去做左子树
                    RotateL(grandfather);
                    //调节颜色
                    grandfather->_col = RED;
                    parent->_col = BLACK;
                }
                else //新增结点在父亲的左边，折线情况，引发双旋
                {
                    //处理：以parenrt为旋转点做右单旋，再以grandfather为旋转点做左单旋
                    RotateR(parent);  //右旋
                    RotateL(grandfather); //左旋
                    parent->_col = grandfather->_col = RED;
                    cur->_col = BLACK;
                }
                break;
            }
             
        }
 
    _root->_col = BLACK;
}

免费讲解

拆解讨论：

以下只列举parent在grandfather左边的情况，而parent在grandfather右边的情况处理方式只是反过来的，读者可以自行画图，这里仅留参考代码

Node* uncle = grandfather->_right;  
if (uncle && uncle->_col == RED)  //对应情况：uncle存在且为红
{
    //处理：父亲和叔叔变成黑色，祖父变成红色，继续向上调整
    uncle->_col = parent->_col = BLACK; 
    grandfather->_col = RED;
 
    //向上调整
    cur = grandfather;  //调整孩子
    parent = cur->_parent;//调整父亲
         
}

免费讲解

在这里插入图片描述

else   //uncle不存在，uncle存在且为黑
{
    //直线情况(cur在parent的左边)：只考虑单旋，以grandfather为旋转点进行右单旋转，
    //旋转完后将祖父的颜色变成红色，将父亲的颜色变成黑色
    if (parent->_left == cur) 
    {
        RotateR(grandfather);
        parent->_col = BLACK;
        grandfather->_col = RED;
    }
    else  //parent->_right == cur 
    {   
        //双旋转
    }
}

免费讲解

在这里插入图片描述

//折线情况(cur在parent的右边)：这里会引发双旋
RotateL(parent);  //以parent为旋转点进行左单旋
RotateR(grandfather); //以grandfather为旋转点进行右单旋转
//旋转完后cur会去做树的根，那么设置为黑色，
//为了保证每条路径的黑色结点个数相同，grandfather结点颜色设置为红
cur->_col = BLACK;
grandfather->_col = RED; 

免费讲解

在这里插入图片描述

旋转

void RotateR(Node* parent) //右单旋
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
 
        parent->_left = subLR;
        if (subLR) subLR->_parent = parent;  //防止subLR为nullptr
 
        subL->_right = parent;
        Node* parent_parent = parent->_parent; //指针备份
        parent->_parent = subL;
        if (_root == parent) //如果parent就是树的根 
        {
            _root = subL;  //subL取代parent
            _root->_parent = nullptr;
        }
        else  //如果parent并不是树的根
        {
            if (parent_parent->_left == parent) parent->_left = subL;
            else parent_parent->_right = subL;
 
            subL->_parent = parent_parent; //subL去做parent_parent的孩子
        }
    }
     
    //左单旋
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
 
        parent->_right = subRL;
        if (subRL) subRL->_parent = parent;
 
        subR->_left = parent;
        Node* parent_parent = parent->_parent;
        parent->_parent = subR;
 
        if (_root == parent)
        {
            _root = subR;
            _root->_parent = nullptr;
        }
        else
        {
            if (parent_parent->_left == parent) parent_parent->_left = subR;
            else parent_parent->_right = subR;
 
            subR->_parent = parent_parent;
        }
    }

免费讲解

验证

/*
    红黑树的几点性质在于：
    1、根结点必须是红色的
    2、不会出现连续的红色结点
    3、所有路径的黑色结点个数是相同的
*/
bool _CheckBlance(Node* root, int isBlackNum, int count) 
{
    if (!root) 
    {
        if (isBlackNum != count) 
        {
            printf("黑色结点个数不均等\n");
            return false;
        }
        return true; //遍历完整棵树，如果以上列举的非法情况都不存在就返回true
    }
    //检查是否出现连续的红色结点
    if (root->_col == RED && root->_parent->_col == RED) 
    {
        printf("出现了连续的红色结点\n");
        return false;
    } 
    //走前序遍历的过程中记录每一条路径黑色结点的个数
    if (root->_col == BLACK) count++;
     
    //递归左右子树
    return _CheckBlance(root->_left, isBlackNum, count) && 
            _CheckBlance(root->_right, isBlackNum, count);
}
 
//验证红黑树
bool CheckBlance()
{
    if (!_root) return true;  //树为null
 
    //根结点是黑色的
    if (_root->_col != BLACK) 
    {
        printf("根结点不是黑色的\n");
        return false;
    }
    //每一条路径黑色结点的个数必须是相同的，
    int isBlcakNum = 0;
    Node* left = _root; 
    while (left) 
    {
        if (left->_col == BLACK) isBlcakNum++; // 统计某一条路径的所以黑色结点个数
        left = left->_left;
    }
    //检查连续的红色结点，检查每一条路径的黑色结点个数是否相等
    return _CheckBlance(_root, isBlcakNum ,0);
}

免费讲解

红黑树与AVl树的比较

红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的
时间复杂度都是O( log n)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。