红黑树 RB Tree

系统管理员 2022-07-14 21:28 56阅读 0赞

# 前言 #

前面我们已经提到过了二叉搜索树和AVL树两种查找树，二叉搜索树最好情况下(为完全二叉树)查找的时间复杂度为O(lgN)，最坏情况下(类似于单链表)的时间复杂度为O(N)。而AVL树则是对二叉搜索树的一种优化，他保证一个节点的左右子树的高度差不超过+-1的绝对值，从而减小了一棵树的高度，通过减小树的高度的方式来减小查找数据的时间复杂度。而今天所要提到的红黑树是通过一系列的负责设置确保没有一条路径能超过其他路径的两倍从而保证树的平衡的。

## 红黑树的定义 ##

红黑树是满足下面红黑性质的二叉搜索树  
1 . 每个节点，不是红色就是黑色的  
2 . 根节点是黑色的  
3 . 如果一个节点是红色的，则它的两个子节点是黑色的  
4 . 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。  
5.每个NIL节点都是黑色的（NIL节点指的是空节点）  
![红黑树][20161029115448198]

## 红黑树的结构 ##

template<class K,class V>
    struct RBTreeNode
    {
        
        RBTreeNode<K, V>* _Parent;
        RBTreeNode<K, V>* _Left;
        RBTreeNode<K, V>* _Right;
    
        K _Key;
        V _Value;
        Colour _Col;
    
        RBTreeNode(const K& Key, const V& Value)
            :_Parent(NULL)
            , _Left(NULL)
            , _Right(NULL)
            , _Key(Key)
            , _Value(Value)
            , _Col(RED)
        {}
    };

我们定义Key,Value结构的三叉红黑树（左孩子指针，右孩子指针，指向父节点的指针），它还包括了一个标志红节点还是黑节点的结构体变量，我们一开始创建的节点都默认为红节点。

## 平衡的调整 ##

当我们新插入的节点与红黑树的相关性质冲突时，这棵树就不平衡了，这时，我们需要来调节相关节点的位置或者节点的颜色来使红黑树重新平衡。

### 插入情况1 ###

![插入情况1][1]  
上图中，cur是新插入的节点，此时，cur和parent节点都为红色，这颗树中出现了连续的红节点，这时我们需要对这颗子树重新进行调整。  
我们把这颗树的parent和UncleNode节点改成黑节点，把GrandNode改成红节点，在继续向上调整，这颗子树便符合红黑树的性质，并且每条路劲的黑色节点的数目不改变。  
![这里写图片描述][20161029121937635]

### 插入情况2 ###

![这里写图片描述][20161029123243386]  
如上图，如果UncleNode不存在或者存在且为黑色。  
UncleNode不存在时，这时cur为新插入节点，它和parent都是红节点，于是出现了相邻红节点的情况。  
UncleNode存在且为黑色时，这时cur为从下往上调整上来的情况。c和a,b子树上一定含有黑色的节点。  
这时，我们队GrandNode节点进行左旋把GrandNode改成红色，把parent改成黑色。

![插入情况二解决之后的情况][20161029123751326]

### 插入情况3 ###

![插入情况3][3]  
插入情况3和插入情况二不同的是插入节点或者是从下面的子树向上调整的节点相对于parent节点位置不一样，我们需要对上图中的parent节点先进行旋转，再采用第二种方法处理问题。  
![第三种问题的解决办法][20161029135414619]

## 代码 ##

#pragma once
    
    #include <iostream>
    using namespace std;
    #include <cassert>
    
    enum Colour
    {
        RED,
        BLACK,
    };
    
    template<class K,class V>
    struct RBTreeNode
    {
        RBTreeNode<K, V>* _Parent;
        RBTreeNode<K, V>* _Left;
        RBTreeNode<K, V>* _Right;
    
        K _Key;
        V _Value;
        Colour _Col;
    
        RBTreeNode(const K& Key, const V& Value)
            :_Parent(NULL)
            , _Left(NULL)
            , _Right(NULL)
            , _Key(Key)
            , _Value(Value)
            , _Col(RED)
        {}
    };
    
    
    template<class K,class 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* parent = NULL;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_Key > Key)
                {
                    parent = cur;
                    cur = cur->_Left;
                }
                else if (cur->_Key < Key)
                {
                    parent = cur;
                    cur = cur->_Right;
                }
                else
                    return false;
            }
    
            cur = new Node(Key, Value);
            if (parent->_Key < Key)
            {
                parent->_Right = cur;
                cur->_Parent = parent;
            }
            else
            {
                parent->_Left = cur;
                cur->_Parent = parent;
            }
    
            //进行调整
            //如果当前节点不为根节点并且parent的颜色为红色则进行调整
    
            while (cur != _root && parent->_Col == RED)
            {
                Node* GrandNode = parent->_Parent;          //定义祖父节点
                //parent 为左树
                if (parent == GrandNode->_Left)
                {
                    Node* UncleNode = GrandNode->_Right;
                    //情况1
                    if (UncleNode&&UncleNode->_Col == RED)
                    {
                        parent->_Col = UncleNode->_Col = BLACK;
                        GrandNode->_Col = RED;
    
                        cur = GrandNode;
                        parent = cur->_Parent;
                    }
                   //情况二和三
                    else
                    {
                        if (cur == parent->_Right)
                        {
                            _RotateL(parent);
                            swap(parent, cur);
                        }
                        _RotateR(GrandNode);
                        GrandNode->_Col = RED;
                        parent->_Col = BLACK;
    
                        cur = parent;
                        parent = cur->_Parent;
                    }
                }
                //parent 在右树
                else
                {
                    Node* UncleNode = GrandNode->_Left;
                    //情况1
                    if (UncleNode&&UncleNode->_Col == RED)
                    {
                        parent->_Col = UncleNode->_Col = BLACK;
                        GrandNode->_Col = RED;
    
                        //继续向上调整
                        cur = GrandNode;
                        parent = cur->_Parent;
                    }
                    //情况2、3
                    else
                    {
                        if (cur == parent->_Left)
                        {
                            _RotateR(parent);
                            swap(cur, parent);
                        }
                        _RotateL(GrandNode);
                        GrandNode->_Col = RED;
                        parent->_Col = BLACK;
    
                        cur = parent;
                        parent = cur->_Parent;
                    }
                }
            }
            _root->_Col = BLACK;
            return true;
        }
    
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }
    
        bool IsBalance()
        {
    
            if (_root == NULL)
                return true;
    
            //根节点不能为红色
            if (_root->_Col == RED)
                return false;
    
            //统计一条路径上的黑色节点的个数
            int RefCount = 0;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_Col == BLACK)
                    RefCount++;
                cur = cur->_Left;
            }
            int count = 0;
            return _IsBalance(_root,RefCount,count);
    
        }
    protected:
        bool _IsBalance(Node* root,const int RefCount,int count)
        {
            //_root->_Col = RED;
            //如果root为空则比较当前节点到根节点路径的黑色节点的数目是否与REF相等
            if (root == NULL)
            {
                return RefCount == count;
            }
    
            //相邻节点不能为红色
            Node* parent = root->_Parent;
            if (parent && (parent->_Col == RED&&root->_Col == RED))
                return false;
    
            if (root->_Col == BLACK)
                count++;                     //遇到黑节点 count++
    
            return _IsBalance(root->_Left, RefCount, count)
                && _IsBalance(root->_Right, RefCount, count);
        }
    
        void _RotateL(Node* parent)
        {
            Node* SubR = parent->_Right;
            Node* SubRL = SubR->_Left;
            Node* ppNode = parent->_Parent;
    
            parent->_Right = SubRL;
            if (SubRL)
                SubRL->_Parent = parent;
            SubR->_Left = parent;
            parent->_Parent = SubR;
            if (ppNode == NULL)
            {
                SubR->_Parent = NULL;
                _root = SubR;
            }
            else
            {
                SubR->_Parent = ppNode;
                if (ppNode->_Left == parent)
                    ppNode->_Left = SubR;
                else
                    ppNode->_Right = SubR;
            }
        }
    
        void _RotateR(Node* parent)
        {
            Node* SubL = parent->_Left;
            Node* SubRL = SubL->_Right;
            Node* ppNode = parent->_Parent;
    
            parent->_Left = SubRL;
            if (SubRL)
                SubRL->_Parent = parent;
            SubL->_Right = parent;
            if (ppNode == NULL)
            {
                SubL->_Parent = NULL;
                _root = SubL;
            }
            else
            {
                SubL->_Parent = ppNode;
                if (ppNode->_Left == parent)
                    ppNode->_Left = SubL;
                else
                    ppNode->_Right = SubL;
            }
            parent->_Parent = SubL;
        }
    
        void _InOrder(Node* root)
        {
            if (root == NULL)
                return;
    
            _InOrder(root->_Left);
            cout << root->_Key << " ";
            _InOrder(root->_Right);
        }
    protected:
        Node* _root;
    };

[20161029115448198]: /images/20220715/457ed0082a444846bc70b82bfadcc42a.png
[1]: /images/20220715/85197d25764249f888e26e573579c368.png
[20161029121937635]: /images/20220715/84a45fa7e7344450a0a6747ff5edb753.png
[20161029123243386]: /images/20220715/6fede3ca3609409c8d09f5b8c25c46b9.png
[20161029123751326]: /images/20220715/9cc3da5a4f5d4bf99d1425461d52130e.png
[3]: /images/20220715/dc7f19a0027b4d4699460b60e469d5b3.png
[20161029135414619]: /images/20220715/fc17bdeca374461189be25bd865b3ec7.png