红黑树的概念与实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了红黑树的概念与实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、红黑树的概念

1.什么是红黑树

2.红黑树满足的性质

3.红黑树存在的意义

二、红黑树的实现

1.类的构建

2.插入函数

（1）插入一个节点

（2）调整节点

（3）旋转

三、红黑树的检验

一、红黑树的概念

1.什么是红黑树

红黑树是一种二叉搜索树，每个结点增加一个变量表示结点的颜色，颜色只能是Red或Black。通过对所有从根到叶子节点的路径上各个结点颜色的限制，保证没有一条路径会比其他路径长出两倍，因而红黑树是一种接近平衡的二叉搜索树。

2.红黑树满足的性质

（1）每个结点不是红色就是黑色

（2）根节点是黑色的

（3）如果一个节点是红色的，则它的两个子结点是黑色的（可以出现连续的黑节点，但不可以出现连续的红节点）

（4）对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

（5）每个叶子结点都是黑色的(此处的叶子结点指的是null结点)

红黑树的五个规则使得搜索树成为了一个不严格的AVL树。

红黑树的概念与实现

3.红黑树存在的意义

对于AVL树，由于它是绝对平衡的，所以为了维持这样的结构它就需要大量地对节点进行旋转，而红黑树对平衡的要求不是很严格，需要旋转的次数就减少了。同时，AVL树相比红黑树的搜索效率也并没有明显提高，比如说在同样的多个数据中查找一个数据，AVL树查找需要10次递归，在红黑树中查找可能需要递归15次（大于等于十次），但是对于一个每秒能计算一亿次的计算机而言，这五次查找根本就没有时间的影响。

所以红黑树是一种接近平衡的二叉搜索树，它不如AVL树的结构严格平衡，也解决了普通二叉搜索树的极端情况搜索效率下降的问题。

二、红黑树的实现

1.类的构建

只要是树就一定需要节点类BRTreeNode和整棵树的类BRTree，并将它们放在一个命名空间内。

BRTreeNode类中的成员变量包括，一个pair键值对（_kv），父指针（_parent），左子节点指针（_left），右子节点指针（_right），还有一个表示颜色的变量（_col），用枚举变量实现。

这里有个小问题，我们在构造函数中_col应该初始化为红还是黑呢？如果我们把这个默认颜色设置为黑，那么只要增加一个黑节点那一定会违背第四个规则。（对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点）而设为红节点，在后来的调整中还可以改，故默认颜色为红。

#include<assert.h>
namespace MY_BRTree
{
    //节点只有黑色和红色
    enum Colour
    {
        RED,
        BLACK,
    };
    
    template<class K, class V>
    struct BRTreeNode
    {
        std::pair<K, V> _kv;
        BRTreeNode* _parent;
        BRTreeNode* _left;
        BRTreeNode* _right;
        Colour _col;
        
        BRTreeNode(const std::pair<K, V>& kv)
            :_kv(kv)
            , _left(nullptr)
            , _right(nullptr)
            , _parent(nullptr)
            , _col(RED)
        {}
        //除了键值对直接初始化，指针为空，默认颜色设置为红
    };
    
    template<class K, class V>
    class BRTree
    {
        typedef BRTreeNode<K, V> Node;
    public:
        //成员函数
    private:
        Node* _root = nullptr;
    }                

}

2.插入函数

我们的红黑树依旧只学习插入函数

（1）插入一个节点

bool insert(std::pair<K, V>& kv)
{
    //空树特殊处理
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK;//根是黑色的
        return true;
    }
    //非空树
    else
    {
        Node* parent = nullptr;
        Node* cur = _root;//父子指针查找迭代，小往左走，大往右走
        while (cur)
        {
            if (kv.first < cur->_kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (kv.first > cur->_kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                return false;
            }
        }
        
        //此时已经找到了空节点
        cur = new Node(kv);
        cur->_col = RED;//设置初始颜色为红
        
        //将新节点与其父节点连接起来
        if (kv.first < cur->_kv.first)
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        
    }  
    //到这里我们完成了节点的插入，后续还需要对树进行调整，主要是对节点颜色的调整                                                                                                                                                                                                    

                    
}

（2）调整节点

红黑树的节点颜色调整参考新插入节点的祖父节点的另一棵子树的根节点，也就相当于我们辈分中的叔叔节点。情况总共分为六种：

红黑树的概念与实现

（3）旋转

上面的六种需要旋转的情形中当然也需要六种不同的解决方式。

所有的旋转只需要使用AVL树的左右单旋函数即可，这里我们只讲解4、5、6三种情况。

首先，图4，uncle节点在右且为红。

将parent和uncle节点变红且grandfather节点变红，如果grandfather的父节点也为红就继续向上更新至不会出现连续红节点即可。

红黑树的概念与实现

其次，uncle在右为黑或者为空（空也为黑，这里仅以存在举例）而且cur、parent、grandfather在一条直线上。先对grandfather节点进行右单旋，然后改cur和grandfather为红节点，parent为黑节点即可。

红黑树的概念与实现

然后，uncle在右为黑或者为空（空也为黑，这里仅以存在举例）而且cur、parent、grandfather不在一条直线上。先对parent节点进行左单旋变成上面的情况，然后再对grandfather右单旋再正确改变节点的颜色即可。

红黑树的概念与实现

最后，uncle在左边的情况沿用上面的解法，将旋转方向改变一下，以同样的方式改变颜色就可以了。

最后的代码实现：

bool insert(std::pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK;//根是黑色的
        return true;
    }
    else
    {
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (kv.first < cur->_kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (kv.first > cur->_kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                return false;
            }
        }
        
        cur = new Node(kv);
        cur->_col = RED;

        if (kv.first < cur->_kv.first)
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_right = cur;
            cur->_parent = parent;
        }

        while (parent && parent->_col == RED)
        {
            //可以存在多个连续的黑节点，单不能出现连续的红节点
            //红黑树对于树的处理只取决于插入节点的祖父节点的另一个子节点，相当于叔叔节点

            Node* grandfater = parent->_parent;
            //叔叔节点在右侧
            if (parent == grandfater->_left)
            {
                Node* uncle = grandfater->_right;
                //uncle存在且为红
                if (uncle && uncle->_col == RED)
                {
                    uncle->_col = BLACK;
                    parent->_col = BLACK;
                    grandfater->_col = RED;

                    cur = grandfater;
                    parent = cur->_parent;
                }
            }
            else
            {
            //uncle存在且为黑或者uncle不存在
            //cur是parent的左子节点
            if (cur == parent->_left)
            {
                RotateR(grandfater);
            parent->_col = BLACK;
            grandfater->_col = RED;
            }
            //cur是parent的右子节点
            else
            {
                RotateL(parent);
            RotateR(grandfater);
            cur->_col = BLACK;
            grandfater->_col = RED;
            }
            break;
            }
            }
            //叔叔节点在左侧
            else
            {
                Node* uncle = grandfater->_right;
                //uncle存在且为红
                if (uncle && uncle->_col == RED)
                {
                    uncle->_col = BLACK;
                    parent->_col = BLACK;
                    grandfater->_col = RED;

                    cur = grandfater;
                    parent = cur->_parent;
                }
                else
                {
                    //uncle存在且为黑或者uncle不存在
                    //cur是parent的右子节点
                    if (cur == parent->_left)
                    {
                        RotateL(grandfater);
                        parent->_col = BLACK;
                        grandfater->_col = RED;
                    }
                    //cur是parent的左子节点
                    else
                    {
                        RotateR(parent);
                        RotateL(grandfater);
                        cur->_col = BLACK;
                        grandfater->_col = RED;
                    }
                    break;
                }    
            }
         }
        _root->_col = BLACK;//不管我改没改根，我都把根置为黑，保证根必为黑
        return true;
    }
}

三、红黑树的检验

我们之前学过AVL树的检测（平衡一因子正确且为-1，0，1其一），红黑树的检验就比较复杂了。

红黑树必须满足红黑树的四个必要条件：

根节点是黑色的
如果一个节点是红色的，则它的两个子结点是黑色的（可以出现连续的黑节点，但不可以出现连续的红节点）
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
每个叶子结点都是黑色的(此处的叶子结点指的是null结点)

所以我们可以从这四条的方向考虑。

其中，由于所有的叶子节点都是nullptr，它一定为黑节点，所以第四条不需要写入判断。

bool IsBalance()
{
    if (_root == nullptr)//空树不是红黑树
    {
        return true;
    }

    if (_root->_col != BLACK)//根节点不为黑一定不是红黑树，条件1
    {
        return false;
    }
    
    int ref = 0;//ref用于储存最左侧路径上的黑节点数目
    Node* left = _root;
    while (left)
    {
        if (left->_col == BLACK)
        {
            ++ref;
        }
        left = left->_left;
    }
    return Check(_root, 0, ref);
    //Check函数用于检验其他路径上黑节点数是否相同以及是否有连续红节点，条件2和3
}

再来看看Check，Check会一直向下通过黑节点的个数检测各个子树是否为红黑树。文章来源地址https://www.toymoban.com/news/detail-431352.html

bool Check(Node* root, int blackNum, const int ref)
{
    if (root == nullptr)//找到了空树，此时已经统计完了一条路径上的黑节点数
    {
        if (blackNum != ref)//黑节点数与当前路径不同就不是红黑树
        {
            std::cout << "该路径上的黑节点数不等于最左侧路径的黑节点数" << std::endl;
        return false;
        }
        return true;
    }
    
    if (root->_col == RED && root->_parent->_col == RED)//不能有连续红节点
    {
        std::cout << "出现连续的红节点，不符合规范" << std::endl;
        return false;
    }

    if (root->_col == BLACK)//走到这里就一定没统计完整个路径，继续统计
    {
        ++blackNum;
    }

    return Check(root->_left, blackNum, ref) && Check(root->_left, blackNum, ref);
    //继续递归左树和右树
}

到了这里，关于红黑树的概念与实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！