【c++/数据结构】红黑树-RBTree

小咪咪 2022-07-15 02:41 140阅读 0赞

# 什么叫红黑树？ #

同AVL树一样，红黑树也是近似平衡的二叉搜索树，与AVL树不同的是红黑树没有了平衡因子，但增加了一个枚举变量，来标明结点的颜（RED or BLACK）。因为红黑树可以保证它的最长路劲不超过它最短路径的两倍，所以它近似平衡。

红黑树具有以下几点性质：  
1. 每个结点都必须具有一种颜色（RED or BLACK）。  
2. 根结点为黑色。  
3. 如果一个结点为红色，那么它的两个孩子结点均为黑色（没有连续的红结点）。  
4. 对于每个结点，该结点到其所有后代叶子结点的路径上，黑色结点的数量相同。  
5. 每个空结点（NIL结点）都当作一个黑色结点。

下图为一棵简单的红黑树：  
![这里写图片描述][20161030135055871]

# 如何去创建并维护一棵红黑树？ #

红黑树的难点与AVL树相同，插入一个结点并不难，难点在于插入一个结点后，很容易破坏这棵树的平衡，我们就需要做一些***调整工作***让这棵树恢复平衡 。  
那么什么时候需要我们做调整工作呢？看上面红黑树性质第三点，一棵红黑树需要满足没有连续的红结点。  
需要调整的两种情况：  
1. 当我们对一个红结点下插入一个红结点时，出现了连续的红结点。调整。  
2. 调整需要改变结点的颜色，当我们把一个黑结点变为红结点，而恰好这个结点的父亲是一个红结点。又出现了连续的红结点。继续调整。

同时，性质第4点也很重要， 对于每个结点，该结点到其所有后代叶子结点的路径上，黑色结点的数量相同。当我们对一棵子树进行调整，这棵子树也可能拥有一棵兄弟子树，所以我们不能改变当前子树上黑色节点的数量，即路径上黑结点的数量不能改变。  
总结下来，调整方案就是：***遇到连续红结点就调整，调整的同时要保证路径上黑色节点的数量不变。***

PS：①在下面的讲解中会改变结点的颜色，当我们遇到连续的红结点并进行调整时，我们并不知道这个红结点怎么来的，可能是新插入的，也可能是之前的调整由黑结点变过来的。②叔叔结点（uncle）。③a、b、c、d、e均为子树，若一个为空，则都为空，此时cur为新插入结点。若不为空，则都不为空，此时cur为被调整改变的结点。注意这个三个概念，会帮助我们理解下面的讲解。

### 插入情况1： ###

当前结点cur为红，父亲结点parent为红，gparent为黑，***叔叔结点uncle存在且为红***。  
①  
![这里写图片描述][20161030144029842]  
②  
![这里写图片描述][20161030170830097]

这种情况我们只需要改变结点颜色，不需要挪动结点位置。  
颜色调整：将parent与叔叔结点uncle的颜色变为黑色，将gparent的颜色变为红色。  
继续向上调整：令cur = gparent，parent = gparent->\_parent。继续向上调整。

代码

uncle->_col = parent->_col = BLACK;
    Gparent->_col = RED;// Gparent 可能为子树，保证黑色节点数量不变
    
    //继续向上调整
    cur = Gparent;
    parent = cur->_parent;

### 插入情况2： ###

当前结点cur为红色，parent为红色，gparent为红色，***叔叔结点uncle不存在或者为黑***。(ps：当uncle结点不存在时，所有子树都不存在，cur为新插入结点，当uncle存在且为黑时，cur为被调整改变的结点。***以下我们以uncle存在且为黑为例***。)

这个情况又可分为两种小情况：  
① parent为gparent的左孩子，cur为parent的左孩子。  
![这里写图片描述][20161030151035305]  
这种情况需要对gparent进行右单旋操作，看过之前我写的AVL树讲解的朋友们相信已经对旋转操作不再陌生了，这里我再讲一下。  
旋转操作：将parent的右子树变成gparent的左子树，将gparent以及其子树变成parent的右子树。将gparent的父亲结点指向parent。  
颜色调整：将parent的颜色变成黑色，将gparent的颜色变成红色。  
继续向上调整：令cur = parnet， parent = parent->\_parnet.

代码：

void RotateR(Node* parent)
    {
        Node* SubL = parent->_left;
        Node* SubLR = SubL->_right;
        parent->_left = SubLR;
    
        if (SubLR)
        {
            SubLR->_parent = parent;
        }
    
        Node* ppNode = parent->_parent;
    
        SubL->_right = parent;
        parent->_parent = SubL;
    
        if (ppNode)
        {
            if (ppNode->_left == parent)
                ppNode->_left = SubL;
            else
                ppNode->_right = SubL;
            SubL->_parent = ppNode;
        }
        else
        {
            SubL->_parent = NULL;
            _root = SubL;
        }
    }

② parent为gparent的右孩子，cur为parent的右孩子。  
![这里写图片描述][20161030153418164]  
这种情况需要对gparent进行左单旋操作。  
旋转操作：将parent 的左子树变为gparent的右子树，将gparent以及其子树变成parent的左子树，将gparnet的父亲结点指向parent。  
颜色调整：将parent变为黑色，将gparent变为红色。  
继续向上调整：令cur = parent，parent = parent->\_parent。

代码

void RotateL(Node* parent)
    {
        Node* SubR = parent->_right;
        Node* SubRL = SubR->_left;
        parent->_right = SubRL;
    
        if (SubRL)
        {
            SubRL->_parent = parent;
        }
    
        Node* ppNode = parent->_parent;
    
        SubR->_left = parent;
        parent->_parent = SubR;
    
        if (ppNode)
        {
            if (ppNode->_left == parent)
                ppNode->_left = SubR;
            else
                ppNode->_right = SubR;
            SubR->_parent = ppNode;
        }
        else
        {
            SubR->_parent = NULL;
            _root = SubR;
        }
    }

### 插入情况3： ###

当前节点cur为红色，parent为红色，gparent为黑色。***叔叔uncle结点不存在或为黑***(ps：当uncle结点不存在时，所有子树都不存在，cur为新插入结点，当uncle存在且为黑时，cur为被调整改变的结点。***以下我们以uncle存在且为黑为例***。)

这种情况也可分成两种：  
①parent为gparent左孩子，cur为parent右孩子。  
![这里写图片描述][20161030162030227]  
这种情况需要先对parent进行左单旋操作，转换为情况2的第①种情况。  
再进行情况2的①操作。注意：左单旋之后，parent指针指向的位置，与cur指针指向的位置已经改变。再进行情况2的②操作之前需要交换parent与cur指针。调用swap函数swap（parent，cur）。

代码：

if (cur == parent->_right)
    {
        RotateL(parent);
        swap(parent, cur);//保证parent指针所指向的位置不变
    }
    RotateR(Gparent);
    
    //保证左右子树的黑色节点数量不变
    parent->_col = BLACK;
    Gparent->_col = RED;
    //继续向上调整
    
    cur = parent;
    parent = cur->_parent;

②parent为gparent右孩子，cur为parent左孩子。  
![这里写图片描述][20161030161920592]  
这种情况需要先对parent进行右单旋操作，转换为情况2的第②种情况。  
再进行情况2的②操作。同上，交换parent与cur指针。调用swap函数swap（parent，cur）。

代码

if (cur == parent->_left)
    {
        RotateR(parent);
        swap(parent, cur);
    }
    RotateL(Gparent);
    
    parent->_col = BLACK;
    Gparent->_col = RED;
    
    cur = parent;
    parent = cur->_parent;

# 总结 #

到此，红黑树的插入调整算法已经讲完。关于红黑树的删除算法，我后序会继续发表。  
红黑树与AVL树都是高效的平衡二叉树，增删查改时间复杂的都为O（lgN），但是红黑树并不追求完全平衡，可以保证最长路径不超过最短路径的2倍，相对而言，降低了旋转要求，性能相对优于AVL树，所以实际运用中红黑树运用较多。

# 完整代码 #

## 头文件 RBTree.h ##

#pragma once
    #include<iostream>
    using namespace std;
    
    enum Colour
    {
        RED,
        BLACK
    };
    
    template<typename K,typename V>
    struct RBTreeNode
    {
        K _key;
        V _value;
    
        RBTreeNode<K, V>* _left;
        RBTreeNode<K, V>* _right;
        RBTreeNode<K, V>* _parent;
    
        Colour _col;
    
        RBTreeNode(const K& key, const V& value)
            :_key(key)
            , _value(value)
            , _left(NULL)
            , _right(NULL)
            , _parent(NULL)
            , _col(RED)
        {}
    };
    
    template<typename K, typename V>
    class RBTree
    {
        typedef RBTreeNode<K, V> Node;
    public:
        RBTree()
            :_root(NULL)
        {}
        bool Insert(const K& key,const V& value)
        {
            if (_root == NULL)
            {
                _root = new Node(key, value);
                _root->_col = BLACK;
                return true;
            }
    
            Node* cur = _root;
            Node* parent = cur;
            while (cur)
            {
                if (key > cur->_key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (key < cur->_key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;
                }
            }
    
            cur = new Node(key, value);
            if (key > parent->_key)
            {
                parent->_right = cur;
                cur->_parent = parent;
            }
            else
            {
                parent->_left = cur;
                cur->_parent = parent;
            }
    
            //调整
            //parent肯定不为空
            //如果parent为黑色，则不用调整
    
            while (cur != _root && parent->_col == RED)//保证下一次循环parent不为空
            {
                Node* Gparent = parent->_parent;
                if (parent == Gparent->_left)
                {
                    //判断叔叔节点的颜色
                    //叔叔节点为RED
                    //叔叔节点为BLACK或者不存在
                    Node* uncle = Gparent->_right;
    
                    if (uncle && uncle->_col == RED)//叔叔节点为RED
                    {
                        uncle->_col = parent->_col = BLACK;
                        Gparent->_col = RED;// Gparent 可能为子树，保证黑色节点数量不变
    
                        //继续向上调整
                        cur = Gparent;
                        parent = cur->_parent;
                    }
                    else//叔叔节点为BLACK或者不存在
                    {
                        if (cur == parent->_right)
                        {
                            RotateL(parent);
                            swap(parent, cur);//保证parent指针所指向的位置不变
                        }
                        RotateR(Gparent);
    
                        //保证左右子树的黑色节点数量不变
                        parent->_col = BLACK;
                        Gparent->_col = RED;
                        //继续向上调整
    
                        cur = parent;
                        parent = cur->_parent;
                    }
                }
                else
                {
                    Node* uncle = Gparent->_left;
    
                    if (uncle && uncle->_col == RED)
                    {
                        uncle->_col = parent->_col = BLACK;
                        Gparent->_col = RED;
    
                        cur = Gparent;
                        parent = cur->_parent;
                    }
                    else
                    {
                        if (cur == parent->_left)
                        {
                            RotateR(parent);
                            swap(parent, cur);
                        }
                        RotateL(Gparent);
    
                        parent->_col = BLACK;
                        Gparent->_col = RED;
    
                        cur = parent;
                        parent = cur->_parent;
    
                    }
                }
            }
            _root->_col = BLACK;
            return true;
        }
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }
        bool IsRBTree()
        {
            if (_root == NULL)
            {
                return true;
            }
            if (_root->_col == RED)
            {
                return false;
            }
    
            Node* cur = _root;
            size_t count = 0;
            while (cur)
            {
                if (cur->_col == BLACK)
                    count++;
                cur = cur->_left;
            }
            size_t k = 0;
            return _IsRBTree(_root, count, k++);
        }
    protected:
        void RotateL(Node* parent)
        {
            Node* SubR = parent->_right;
            Node* SubRL = SubR->_left;
            parent->_right = SubRL;
    
            if (SubRL)
            {
                SubRL->_parent = parent;
            }
    
            Node* ppNode = parent->_parent;
    
            SubR->_left = parent;
            parent->_parent = SubR;
    
            if (ppNode)
            {
                if (ppNode->_left == parent)
                    ppNode->_left = SubR;
                else
                    ppNode->_right = SubR;
                SubR->_parent = ppNode;
            }
            else
            {
                SubR->_parent = NULL;
                _root = SubR;
            }
        }
        void RotateR(Node* parent)
        {
            Node* SubL = parent->_left;
            Node* SubLR = SubL->_right;
            parent->_left = SubLR;
    
            if (SubLR)
            {
                SubLR->_parent = parent;
            }
    
            Node* ppNode = parent->_parent;
    
            SubL->_right = parent;
            parent->_parent = SubL;
    
            if (ppNode)
            {
                if (ppNode->_left == parent)
                    ppNode->_left = SubL;
                else
                    ppNode->_right = SubL;
                SubL->_parent = ppNode;
            }
            else
            {
                SubL->_parent = NULL;
                _root = SubL;
            }
        }
        void _InOrder(Node* root)
        {
            if (root == NULL)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_key << " ";
            _InOrder(root->_right);
        }
        bool _IsRBTree(Node* root, const size_t& count, size_t k)
        {
            if (root == NULL)
            {
                return count == k;
            }
    
            Node * parent = root->_parent;
            if (parent && parent->_col == RED && root->_col == RED)
            {
                return false;
            }
    
            if (root->_col == BLACK)
            {
                k++;
            }
    
            return _IsRBTree(root->_left, count, k) && _IsRBTree(root->_right, count, k);
    
        }
    protected:
        Node* _root;
    };
    
    void TestRBTree()
    {
        RBTree<int, int> tree;
        int a[9] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; for (int i = 0; i < 9; i++) { tree.Insert(a[i], i); cout << tree.IsRBTree() <<"->"<<a[i]<< endl; } tree.InOrder(); cout << tree.IsRBTree() << endl; }

## test.cpp ##

#include"RBTree.h"
    
    int main()
    {
        TestRBTree();
        system("pause");
        return 0;
    }

[20161030135055871]: /images/20220715/234b06378c8f484ba3a8e3570c47d783.png
[20161030144029842]: /images/20220715/58b560add94d47e48fe37276fd00c7e4.png
[20161030170830097]: /images/20220715/c17a7ba437d2403caf0244fd34992653.png
[20161030151035305]: /images/20220715/492999c770a647ab8133ac25c95a303f.png
[20161030153418164]: /images/20220715/55484cf1699e4b5c9ef1365ed58386ed.png
[20161030162030227]: /images/20220715/16f1d25ac9a54316b82802a0f7024824.png
[20161030161920592]: /images/20220715/aa0e71a5b042495499caa2d0bb6c1f08.png