红黑树

谁践踏了优雅 2022-06-15 12:57 518阅读 0赞

红黑树（Red Black Tree） 是一种自平衡二叉查找树，红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能，它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:  
性质1. 节点是红色或黑色。  
性质2. 根节点是黑色。  
性质3 每个叶节点（NIL节点，空节点）是黑色的。  
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)  
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。  
满足这些性质，那么最长路径一定不超过最短路径的两倍  
通过极端情况来证明：  
![这里写图片描述][SouthEast]

g为cur的祖父节点  
由于第五条性质不易于维护，因此通常选择维护第四条性质  
对红黑树进行插入操作，它相对于AVL树而言，在插入的时候要考虑的情况较多  
第一种情况：这棵树是空的，直接插入，将其颜色修改成为黑色  
第二种情况：这棵树不空，但是插入的节点的父亲是黑色的，也可以直接插入  
第三种情况，插入之后出现了连续红色节点的情况，也就是插入节点cur的父亲为红色，并且叔叔存在且为红色。则将p,u改为黑，g改为红，然后把g当成cur，继续向上调整  
![这里写图片描述][SouthEast 1]

四五情况都是由于子树向上调整变过来的。  
第四种情况：插入之后出现了连续红色节点的情况，也就是插入节点cur的父亲为红色，并且叔叔存在且为黑色或者叔叔不存在。但是p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转 p、g变色–p变黑，g变红。—–（单旋操作）  
![这里写图片描述][SouthEast 2]  
因此必须进行右单旋：  
![这里写图片描述][SouthEast 3]

左单旋也同理：  
![这里写图片描述][SouthEast 4]

第五种情况：插入之后出现了连续红色节点的情况，也就是插入节点cur的父亲为红色，并且叔叔存在且为黑色或者叔叔不存在。但是cur为红，p为红，g为黑，u不存在/u为黑 p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转 则转换成了情况2（双旋操作）  
左右双旋：  
![这里写图片描述][SouthEast 5]  
右左双旋：  
![这里写图片描述][SouthEast 6]

判断一棵树是否为红黑树  
![这里写图片描述][SouthEast 7]、

#include<iostream>
    #include<stdlib.h>
    using namespace std;
    enum colour
    {
        RED,
        BLACK,
    };
    template<class K,class V>
    struct RedBlackTreeNode
    {
    public:
        RedBlackTreeNode(const K &key, const V &value)
            :_left(NULL)
            , _right(NULL)
            , _parent(NULL)
            , _key(key)
            , _value(value)
            , _col(RED)
        {
    
        }
        RedBlackTreeNode<K, V>*_left;
        RedBlackTreeNode<K, V>*_right;
        RedBlackTreeNode<K, V>*_parent;
        K _key;
        V _value;
        colour _col;
    };
    template<class K,class V>
    class RedBlackTree
    {
        typedef RedBlackTreeNode<K,V> Node;
    public:
        RedBlackTree()
            :_root(NULL)
        {
    
        }
        bool Insert(const K&key, const V&value)
        {
            if (_root == NULL)//第一种情况
            {
                _root = new Node(key, value);
                _root->_col = BLACK;
                return true;
            }
            else
            {
                Node*cur = _root;
                Node*parent = NULL;
                while (cur)
                {
                    if (cur->_key < key)
                    {
                        parent = cur;
                        cur = cur->_right;
                    }
                    else if (cur->_key >key)
                    {
                        parent = cur;
                        cur = cur->_left;
                    }
                    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;
                }
                while (parent&&parent->_col == RED)//存在连续的红节点则需要开始分情况考虑
                {
                    Node*grandfather = parent->_parent;
                    if (parent == grandfather->_left)
                    {
                        Node*uncle = grandfather->_right;
                        if (uncle&&uncle->_col == RED)//第二种情况
                        {
                            parent->_col = BLACK;
                            uncle->_col = BLACK;
                            grandfather->_col = RED;//不能改变黑色节点的数目，因为可能是子树,继续向上调整
                            cur = grandfather;
                            parent = cur->_parent;
                        }
                        else if ((uncle&&uncle->_col == BLACK) || uncle == NULL)//可能右旋，可能左右双旋
                        {
                            if (cur == parent->_right)//左右双旋，处理成右旋
                            {
                                RotateL(parent);
                                swap(parent, cur);
                            }
                            RotateR(grandfather);
                            parent->_col = BLACK;
                            grandfather->_col = RED;
                            break;
                        }
                    }
                    else//叔叔节点在右边
                    {
                        Node*uncle = grandfather->_left;
                        if (uncle&&uncle->_col == RED)//第二种情况
                        {
                            parent->_col = BLACK;
                            uncle->_col = BLACK;
                            grandfather->_col = RED;//不能改变黑色节点的数目，因为可能是子树,继续向上调整
                            cur = grandfather;
                            parent = cur->_parent;
                        }
                        else if ((uncle&&uncle->_col == BLACK) || uncle == NULL)//可能左旋，可能右左双旋
                        {
                            if (cur == parent->_left)//右左双旋处理成左旋
                            {
                                RotateR(parent);
                                swap(parent, cur);
                            }
                            RotateL(grandfather); 
                            parent->_col = BLACK;
                            grandfather->_col = RED;
                            break;
                        }
                    }
                }
                _root->_col = BLACK;
            }
        }
        bool IsRedBlackTree()
        {
            if (_root == NULL)
            {
                return true;
            }
            else if (_root&&_root->_col == RED)
            {
                return false;
            }
            else
            { 
                Node *cur = _root;
                int num = 0;//代表从根节点到当前节点黑色节点的数目
                int base_count = 0;//代表基准值
                while (cur)
                {
                    if (cur->_col == BLACK)
                    {
                        ++base_count;
                    }
                    cur = cur->_left;
                }
                return _IsRedBlackTree(_root, num, base_count);
            }
        }
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }
    protected:
        void _InOrder(Node*root)
        {
            if (root == NULL)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_key << " ";
            _InOrder(root->_right);
        }
        bool _IsRedBlackTree(Node*root,int num,int base_count)
        {
            if (root == NULL)
            {
                return true;
            }
            if (root->_col == RED &&root->_parent->_col==RED)
            {
                return false;
            }
            else
            {
                if (root->_col == BLACK)
                {
                    ++num;
                }
                if (root->_left == NULL&&root->_right == NULL)
                {
                    if (num != base_count)
                    {
                        cout << "不是红黑树：";
                        cout << root->_key << " :" << root->_col << endl;
                        return false;
                    }
                }
                _IsRedBlackTree(root->_left, num, base_count);
                _IsRedBlackTree(root->_right, num, base_count);
            }
        }
        void RotateL(Node*&parent)
        {
            Node*SubR = parent->_right;
            Node*SubRL = SubR->_left;
            parent->_right = SubRL;
            if (SubRL)
            {
                SubRL->_parent = parent;
            }
            SubR->_left = parent;
            Node*ppNode = parent->_parent;
            parent->_parent = SubR;
            if (ppNode == NULL)
            {
                _root = SubR;
                _root->_parent = NULL;
            }
            else//考虑这个parent节点可能不是根节点
            {
    
                if (parent == ppNode->_left)
                {
                    ppNode->_left = SubR;
    
                }
                else
                {
                    ppNode->_right = SubR;
    
                }
                SubR->_parent = ppNode;
            }
        }
    
        void RotateR(Node*&parent)
        {
            Node*SubL = parent->_left;
            Node*SubLR = SubL->_right;
            parent->_left = SubLR;
            if (SubLR)
            {
                SubLR->_parent = parent;
            }
            SubL->_right = parent;
            Node*ppNode = parent->_parent;//不确定parent这个节点是不是根节点，要做判断，因此不能随意链接
            parent->_parent = SubL;
            if (ppNode == NULL)
            {
                _root = SubL;
                _root->_parent = NULL;
            }
            else
            {
                if (parent == ppNode->_left)
                {
                    ppNode->_left = SubL;
                }
                else
                {
                    ppNode->_right = SubL;
                }
                SubL->_parent = ppNode;
            }
        }
        Node*_root;
    };
    void FunTest()
    {
        RedBlackTree<int, int>rb;
        int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; //int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (int i = 0; i < (sizeof(arr) / sizeof(arr[0])); i++) { rb.Insert(arr[i], 0); cout << rb.IsRedBlackTree()<<endl; } rb.InOrder(); cout<<rb.IsRedBlackTree(); } int main() { FunTest(); system("pause"); return 0; }

[SouthEast]: /images/20220615/853eae37fc2b491f8ff9caae364b5ac2.png
[SouthEast 1]: /images/20220615/e79a400d08a146cd99d083d6a9ecb2f1.png
[SouthEast 2]: /images/20220615/06f6a6a1b7124de3ae542daf29b1619b.png
[SouthEast 3]: /images/20220615/fa3d2d1cfafd4a558a3bee3ebe5e5bb8.png
[SouthEast 4]: /images/20220615/19a1865e2eea4a1da4c11b471f568f76.png
[SouthEast 5]: /images/20220615/69fef49f66d04f70afa2cc669028b27a.png
[SouthEast 6]: /images/20220615/b679b07ca85a447fb01083e620b07d72.png
[SouthEast 7]: /images/20220615/5d640803fef7469bbf0a70e73a48063c.png