红黑树

[bosthhe1]

红黑树是以接近平衡搜索二叉树产生的，红黑树并不是完全的平衡搜索二叉树 红黑树的5大特性 1， 根节点必须是黑的 2，可以连续黑色节点，不能连续红色节点 3，每一条路劲上的黑色节点数是相同的 4，红黑树最长路劲，不超过最短路劲的两倍(长：一红一黑 短：全黑) 5，红黑树的叶子节点都是黑色的(这里所谓的叶子节点和平时的叶子节点不同，这里的叶子节点代表的是空节点)

[bosthhe1]

#include<iostream>
using namespace std;
#include<time.h>
#include<assert.h>
namespace hxh
{
    enum color
    {
        RED,
        BLACK
    };
    template<class K,class V>
    struct RBTreeNode
    {
        RBTreeNode* left;
        RBTreeNode* right;
        RBTreeNode* parent;
        pair<K,V> _kv;
        color col;
        RBTreeNode(const pair<K,V>& kv)
            :left(nullptr)
            , right(nullptr)
            , parent(nullptr)
            , _kv(kv)
            , col(RED)
        {}
    };
    template<class K, class V>
    class RBTree
    {
        typedef RBTreeNode<K,V> Node;
    public:
        RBTree()
            :_root(nullptr)
        {}
        bool insert(const pair<K,V>& tmp)
        {
            Node * newNode = new Node(tmp);
            Node* cur = _root;
            Node* _parent = _root;
            if (_root == nullptr)
            {
                _root = newNode;
                _root->col = BLACK;
                return true;
            }
            else
            {
                while (cur)
                {
                    _parent = cur;
                    if (cur->_kv.first> newNode->_kv.first)
                        cur = cur->left;
                    else if (cur->_kv.first< newNode->_kv.first)
                        cur = cur->right;
                    else
                        return false;
                }
                if (_parent->_kv.first>newNode->_kv.first)
                {
                    _parent->left = newNode;
                    newNode->parent = _parent;
                }
                else
                {
                    _parent->right = newNode;
                    newNode->parent = _parent;
                }
                while (_parent != nullptr&&_parent->col == RED)
                {
                    Node* GrandParent = _parent->parent;
                    if (_parent->left == newNode&&GrandParent->left == _parent)
                    {
                        Node* uncle = _parent->parent->right;
                        if (uncle == nullptr)
                        {
                            RRotate(GrandParent);
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            break;
                        }
                        else if (uncle->col == RED)
                        {
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            uncle->col = BLACK;
                            newNode = GrandParent;
                            _parent = newNode->parent;
                        }
                        else if (uncle->col == BLACK)
                        {
                            RRotate(GrandParent);
                            _parent->col = BLACK;
                            GrandParent->col = RED;
                            break;
                        }
                        else
                        {
                            assert(false);
                        }
                    }
                    else if (_parent->right == newNode&&GrandParent->right == _parent)
                    {
                        Node* uncle = _parent->parent->left;
                        if (uncle == nullptr)
                        {
                            LRotate(GrandParent);
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            break;
                        }
                        else if (uncle->col == RED)
                        {
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            uncle->col = BLACK;
                            newNode = GrandParent;
                            _parent = newNode->parent;
                        }
                        else if (uncle->col == BLACK)
                        {
                            LRotate(GrandParent);
                            _parent->col = BLACK;
                            GrandParent->col = RED;
                            break;
                        }
                        else
                        {
                            assert(false);
                        }
                    }
                    else if (_parent->left == newNode&&GrandParent->right == _parent)
                    {
                        Node* uncle = _parent->parent->left;
                        if (uncle == nullptr)
                        {
                            LRPotate(GrandParent);
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            break;
                        }
                        else if (uncle->col == RED)
                        {
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            uncle->col = BLACK;
                            newNode = GrandParent;
                            _parent = newNode->parent;
                        }
                        else if (uncle->col == BLACK)
                        {
                            LRPotate(GrandParent);
                            _parent->col = RED;
                            GrandParent->col = RED;
                            newNode->col = BLACK;
                            break;
                        }
                        else
                        {
                            assert(false);
                        }
                    }
                    else if (_parent->right == newNode&&GrandParent->left == _parent)
                    {
                        Node* uncle = _parent->parent->right;
                        if (uncle == nullptr)
                        {
                            RLPotate(GrandParent);
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            break;
                        }
                        else if (uncle->col == RED)
                        {
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            uncle->col = BLACK;
                            newNode = GrandParent;
                            _parent = newNode->parent;
                        }
                        else if (uncle->col == BLACK)
                        {
                            RLPotate(GrandParent);
                            _parent->col = RED;
                            GrandParent->col = RED;
                            newNode->col = BLACK;
                            break;
                        }
                        else
                        {
                            assert(false);
                        }
                    }
                }
            }
            _root->col = BLACK;
            return true;
        }
        void RRotate(Node* parent1)
        {
            Node* parent = parent1;
            Node* Grandparent = parent1->parent;
            Node* Sub = parent->left;
            Node* Subr = Sub->right;
            parent->left = Subr;
            if (Subr)
                Subr->parent = parent;
            Sub->right = parent;
            parent->parent = Sub;
            Sub->parent = Grandparent;
            if (Grandparent)
            {
                if (Grandparent->left == parent)
                    Grandparent->left = Sub;
                else
                    Grandparent->right = Sub;
            }
            else
            {
                Sub->parent = nullptr;
                _root = Sub;
            }
        }
        void LRotate(Node* parent1)
        {
            Node* parent = parent1;
            Node* Grandparent = parent1->parent;
            Node* Sub = parent->right;
            Node* Subl = Sub->left;
            parent->right = Subl;
            if (Subl)
                Subl->parent = parent;
            Sub->left = parent;
            parent->parent = Sub;
            Sub->parent = Grandparent;
            if (Grandparent)
            {
                if (Grandparent->left == parent)
                    Grandparent->left = Sub;
                else
                    Grandparent->right = Sub;
            }
            else
            {
                Sub->parent = nullptr;
                _root = Sub;
            }
        }
        void RLPotate(Node* cur)
        {
            RRotate(cur->right);
            LRotate(cur);
        }
        void LRPotate(Node* cur)
        {
            LRotate(cur->left);
            RRotate(cur);
        }
        bool testCorrect()
        {
            int k = 0;
            Node* cur = _root;
            while (cur)
            {
                if (cur->col == BLACK)
                    k++;
                cur = cur->left;
            }
            int t = 0;
            return _testCorrect(_root, k, t);
        }
    private:
        bool _testCorrect(Node* root, int k, int t)
        {
            if (root == nullptr)
            {
                if (k == t)
                    return true;
                return false;
            }
            if (root->col == BLACK)
                t++;
            return _testCorrect(root->left, k, t) &&
                _testCorrect(root->right, k, t);
        }
    private:
        Node* _root;
    };
}