红黑树

当我们在使用二叉搜索树时，如果树的高度较高，对其的操作并不比对链表操作要快。原因是二叉搜索树在插入顺序基本有序时会退化为一个排序链表，所以说是不平衡的。

对二叉搜索树的改进有 AVL 树和红黑树。先来看红黑树，它广泛应用在 STL 的 set 和 map，Java 库和 Linux 内核中。

红黑树是一颗平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是 RED 或 BLANK。通过对任何一条从根节点到叶子节点的简单路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出 2 倍，因而是近似平衡的。

红黑树的约束如下：

• 每个节点要么是红色的，要么是黑色的；
• 根节点是黑色的；
• 如果一个节点是红色的，那么它的两个子节点都是黑色的；
• 对每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含数目相同的黑色节点；
• 每个叶子节点是黑色的(这里的叶子节点指的是 NIL 节点，即空节点)。

红黑树的插入操作步骤如下：

• 先按照搜索树的步骤将节点插入到相应位置，并置该节点颜色为红色。设该节点指针为 cur；
• 如果破坏了以上某些条件，则对该树进行相应的调整，步骤如下：
  • 情况1：若 cur 的父亲结点和叔叔节点都为红色，则进行红色提升；
  • 情况2：若父红叔黑或叔叔不存在，且 cur 为其父节点的右孩子，则令 cur = parent 并以父节点为根进行旋转；
  • 情况3：若父红叔黑或叔叔不存在，且 cur 为其父节点的左孩子，则将父节点变为黑色，祖父节点变为红色并以祖父节点为根进行旋转；

代码如下：

#pragma once

#include<iostream>
using namespace std;

enum Color
{
    RED,
    BLANK,
};

template<typename K,typename V>
struct RBTreeNode{
    K _key;
    V _value;

    RBTreeNode<K,V>* _left;
    RBTreeNode<K,V>* _right;
    RBTreeNode<K,V>* _parent;

    Color _color;

    RBTreeNode(const K& key=K(),const V& value=V())
        :_key(key),_value(value)
         ,_left(NULL),_right(NULL)
         ,_parent(NULL)
         ,_color(RED)
    {}
};

template<typename K,typename V>
class RBTree{
    typedef RBTreeNode<K,V> Node;

public:
    RBTree()
        :_root(nil)
    {}

    bool Insert(const K& key,const V& value)
    {
        Node* s=new Node(key,value);
        Node* parent=nil;
        Node* cur=_root;
        while(cur!=nil)
        {
            parent=cur;
            if(cur->_key>cur->_key)
                cur=cur->_left;
            else
                cur=cur->_right;
        }
        cur->_parent=parent;
        if(parent==nil)
            _root=s;
        else if(s->_key>parent->_key)
            parent->_right=s;
        else 
            parent->_left=s;
        s->_left=s->_right=nil;
        //s->_color=RED;
        RB_INSERT_FIX(s);
    }

    bool Remove(const K& key);
    Node* Find(const K& key);
    bool IsBalance();

protected:
    void RotateL(Node* root)
    {
        if(root==NULL)
            return;
        Node* parent=root;
        Node* subR=parent->_right;
        Node* subRL=subR->_left;
        parent->_right=subRL;
        if(subRL!=NULL)
            subRL->_parent=parent;
        Node* ppNode=parent->_parent;
        subR->_left=parent;
        parent->_parent=subR;
        if(ppNode!=NULL)
        {
            if(ppNode->_left==parent)
                ppNode->_left=subR;
            else
                ppNode->_right=subR;
        }
        else
        {
            _root=subR;
        }
        subR->_parent=ppNode;
        parent->_bf = subR->_bf = 0;
    }

    void RotateR(Node* root)
    {
        if(root==NULL)
            return;
        Node* parent=root;
        Node* subL=parent->_left;
        Node* subLR=subL->_right;
        parent->_left=subLR;
        if(subLR!=NULL)
            subLR->_parent=parent;
        Node* ppNode=parent->_parent;
        subL->_right=parent;
        parent->_parent=subL;
        if(ppNode!=NULL)
        {
            if(ppNode->_left==parent)
                ppNode->_left=subL;
            else
                ppNode->_right=subL;
        }
        else
        {
            _root=subL;
        }
        subL->_parent=ppNode;
        parent->_bf = subL->_bf = 0;
    }

    void RB_INSERT_FIX(Node* cur)
    {
        while(cur->_parent._color==RED)
        {
            Node* parent=cur->_parent;
            Node* grandfather=parent->_parent;
            Node* uncle;
            if(parent=grandfather->_left)
            {
                uncle=grandfather->_right;
                if(uncle->_color=RED)
                {
                    parent->_color=BLANK;
                    uncle->_color=BLANK;
                    grandfather->_color=RED;
                    cur=grandfather;
                }
                else if(cur=parent->_right)
                {
                    cur=parent;
                    rotateL(cur);
                }
                else
                {
                    parent->_color=BLANK;
                    grandfather->_color=RED;
                    rotateR(grandfather);
                }
            }
            else
            {
                uncle=grandfather->_left;
                if(uncle->_color=RED)
                {
                    parent->_color=BLANK;
                    uncle->_color=BLANK;
                    grandfather->_color=RED;
                    cur=grandfather;
                }
                else if(cur=parent->_left)
                {
                    cur=parent;
                    rotateR(cur);
                }
                else
                {
                    parent->_color=BLANK;
                    grandfather->_color=RED;
                    rotateL(grandfather);
                }
            }
        }
        _root->_color=BLANK;
    }

private:
    Node* _root;
    static Node* nil;
};

template<typename K,typename V>
RBTreeNode<K,V>* RBTree<K,V>::nil=new RBTreeNode<K,V>();

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码在github上：点我前往