【数据结构】：红黑树RB Tree

红黑树是近似平衡的二叉搜索树。
红黑树的性质:
1，每个节点不是红色就是黑色
2，根节点必须是黑色
3，没有连续的红节点
4，每条路径上黑色节点数目相等

红黑树保证最长路径不超过最短路径的两倍。那么，为什么满足以上这些条件就能保证呢？
最短路径一定是节点全黑，要保证每条路径的黑节点数量相等，只能在两个黑节点之间添加红节点，所以最长路径不会超过最短路径的两倍。
红黑树保证效率为log2^N

如上图所示是一棵简单的红黑树，红黑树的插入要通过旋转和变色来调节平衡。

当parent是grandfather的左孩子，uncle是grandfather的右孩子时，插入可分为以下情况：

1，叔叔节点存在且为红色

Node* grandfther = parent->_parent;
            if (parent == grandfther->_left)
            {
                Node* uncle = grandfther->_right;
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = BLACK;
                    uncle->_col = BLACK;
                    grandfther->_col = RED;

                    cur = grandfther;
                    parent = cur->_parent;
                }

2，叔叔节点不存在或存在且为黑

将parent变黑，grandfather变红，进行右单旋

else // u 不存在 u黑
                {
                    if(cur == parent->_right) // 双旋
                    {
                        RotateL(parent);
                        swap(cur,parent);
                    }

                    RotateR(grandfther);
                    parent->_col = BLACK;
                    grandfther->_col = RED;
                    break;
                }

3，cur是parent的右孩子，需要双旋

当parent是grandfather的右时，需要分析的情况还是以上三种，只是方向相反而已。

完整代码：

#pragma once
#include<iostream>
using namespace std;

enum Colour
{
    RED,BLACK,};

template<class K,class V>
struct RBTreeNode
{
    K _key;
    K _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<class K,class V>
class RBTree
{
    typedef RBTreeNode<K,V> Node;
public:
    RBTree()
        :_root(NULL)
    {}

    RBTree(const RBTree<K,V>& tree)
    {
        _copy(tree._root);
    }


    ~RBTree()
    {
        _Destroy(_root);
    }

    RBTree<K,V>& operator = (const RBTree<K,V>& tree)
    {
        RBTree<K,V> tmp(tree);
        swap(_root,tree._root);
        return *this;
    }


    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->_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 // u 不存在 u黑
                {
                    if (cur == parent->_right) // 双旋
                    {
                        RotateL(parent);
                        swap(cur,parent);
                    }

                    RotateR(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                    break;
                }
            }
            //parent = grandfather->right
            else if (parent == grandfather->_right)
            {
                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 (cur == parent->_right)
                    {
                        RotateR(parent);
                        swap(parent,cur);
                    }
                    RotateL(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                    break;
                }
            }
        }
        _root->_col = BLACK;
        return true;
    }

    void Inorder()
    {
        _Inorder(_root);
    }

    bool IsBalance()
    {
        Node* cur = _root;
        if (_root == NULL)
        {
            return true;
        }
        //根节点是黑色
        if (_root->_col == RED)
        {
            return false;
        }
        int BlackNode = 0;
        //统计最左路径上黑色节点的数量
        while (cur)
        {
            if (cur->_col == BLACK)
            {
                ++BlackNode;
            }
            cur = cur->_left;
        }
        //一条路径上黑色节点的数量
        int num = 0;
        return _IsBlance(_root,BlackNode,num);
    }
protected:
    void _copy(Node* root)
    {
        Node* newNode = NULL;
        Node* cur = root;
        while (cur)
        {
            newNode = new Node(cur->_key,cur->_value);
            newNode->_left = _copy(cur->_left);
            newNode->_right = _copy(cur->_right);
        }
    }

    void _Destroy(Node* root)
    {
        Node* cur = root;
        if (root == NULL)
            return;
        _Destroy(cur->_left);
        _Destroy(cur->_right);
        delete cur;
        cur = NULL;
    }


    bool _IsBlance(Node* root,const int BlackNode,int num)
    {
        //一条路径已经走完
        if (root == NULL)
        {
            if (num != BlackNode)
            {
                cout << "黑色节点数量不相等" << endl;
                return false;
            }
            else
            {
                return true;
            }
        }
        if (root->_col == BLACK)
        {
            ++num;
        }
        if((root->_col == RED) && (root->_parent) && (root->_parent->_col == RED))
        {
            cout << "有连续的红节点" << root->_key << endl;
            return false;
        }
        return _IsBlance(root->_left,num)
            && _IsBlance(root->_right,num);
    }

    //右旋
    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 = subL;

        if (ppNode == NULL)
        {
            _root = subL;
            subL->_parent = NULL;
        }
        else
        {
            if (ppNode->_left == parent)
            {
                ppNode->_left = subL;
            }
            else
            {
                ppNode->_right = subL;
            }
            subL->_parent = ppNode;
        }
    }

    //左旋
    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;
            subR->_parent = NULL;
        }
        else
        {
            if (ppNode->_left == parent)
            {
                ppNode->_left = subR;
            }
            else
            {
                ppNode->_right = subR;
            }
            subR->_parent = ppNode;
        }
    }

    void _Inorder(Node* root)
    {
        Node* cur = root;
        if (cur == NULL)
            return;
        _Inorder(cur->_left);
        cout << cur->_key << " ";
        _Inorder(cur->_right);
    }
private:
    Node* _root;
};

void TestRBTree()
{
    RBTree<int,int> t;
    int a[] = { 16,3,7,11,9,26,18,14,15 }; for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { t.Insert(a[i],i); } t.Inorder(); cout << endl; cout << "IsBalance?" << t.IsBalance() << endl; } 

我们知道，红黑树是近似平衡的二叉树，那么为什么不直接使用平衡二叉树呢？
原因是红黑树最坏的情况也是log2^N,但它不像平衡二叉树需要严格控制平衡因子，红黑树只需控制节点的颜色，因此它的旋转次数相对于平衡二叉树能少一些，因此，实际中，红黑树的应用更为广泛。

红黑树的应用： 1. C++ STL库 – map 2. Java 库 3. linux内核 4. 其他一些库