红黑树是一种自平衡的二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组(C++ STL 中的map/set)。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。红黑树虽然很复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目(来源百度百科)。

算法导论对R-B Tree的介绍：

    红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

    由于红黑树也是一颗二叉查找树/二叉排序树树, 因此红黑树也满足二叉查找树的一般性质(关于二叉查找树的一般性质请参考博客:http://blog.csdn.net/zjf280441589/article/details/42611161)

    但由于普通的二叉查找树不具备自动平衡的功能, 因此普通的二叉查找树树很有可能会退化成为一条链表, 若二叉树退化成了一棵具有n个结点的线性链后，则插入/删除/查找操作最坏情况运行时间就变为了O（n）。

    因此就有了红黑树, 他的最终查找、插入、删除的时间复杂度最坏情况下依然为O（logn）, 而红黑树之所以这么牛的原因就是它在二叉查找树的基础上增加了着色和相关的性质, 这就是红黑规则:

红黑规则

    1.每一个节点不是红色的就是黑色的;

    2.根总是黑色的;

    3.每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的;

    4.如果节点是红色的, 则它的子节点必须是黑色的;

    5.从根到叶节点的每条路径, 必须包含相同数目的黑色节点;

如果在红黑树中插入/删除了节点之后不满足了红黑规则,则采用以下修正方法:

    1.改变节点的颜色;

    2.旋转;

红黑树结点

template <typename Type>
class RedBlackNode
{
    friend RedBlackTree<Type>;
public:

private:
    RedBlackNode(const Type &_element = Type(),
                 RedBlackNode *_left = NULL,
                 RedBlackNode *_right = NULL,
                 int _color = RedBlackTree<Type>::BLACK)
        : element(_element), left(_left), right(_right), color(_color) {}

private:
//为了在红黑树尚未完成的时候进行测试
//故将之作为public, 待红黑树完成之时,
//就是将其改为private之时;
public:
    Type            element;   //节点值
    RedBlackNode    *left;
    RedBlackNode    *right;
    //红黑树的颜色
    int             color;
};

红黑树

template <typename Type>
class RedBlackTree
{
public:
    //为结点定义别名
    typedef RedBlackNode<Type> Node;

    enum {RED, BLACK};

public:
    //此时红黑树所支持的操作尚不完全,
    //而且函数功能(如析构函数, insert操作)
    //实现的也并不理想,
    //但随着红黑树代码的不断演进,
    //这些代码会不断的完善
    RedBlackTree(const Type &negInf);
    ~RedBlackTree();

    void insert(const Type &data);

private:
//为了在红黑树尚未完成的时候进行测试
//故将之作为public, 待红黑树完成之时,
//就是将其改为private之时;
public:
    //指向红黑树的头(伪根节点)
    //RedBlackNode<Type> *header;
    Node *header;
    //空节点
    Node *nullNode;

    //在插入过程中需要的指针
    Node *current;  //当前节点
    Node *parent;   //父节点
    Node *grand;    //祖父节点(爷爷)
    Node *great;    //曾祖父节点(爷爷的爸爸)

    /* 单旋转 */
    //带着左孩子旋转: 向右旋转
    void rotateWithLeftChild(Node *& k2) const;
    //带着有孩子旋转: 向左旋转
    void rotateWithRightChild(Node *& k1) const;

    /* 双旋转 */
    //向右转
    void doubleRotateWithLeftChild(Node *& k3) const;
    //向左转
    void doubleRotateWithRightChild(Node *& k1) const;
};

构造与析构

//构造函数
template <typename Type>
RedBlackTree<Type>::RedBlackTree(const Type &negInf)
{
    nullNode = new Node();
    header = new Node(negInf, nullNode, nullNode);
}
//这一版的析构函数实现并不完善
template <typename Type>
RedBlackTree<Type>::~RedBlackTree()
{
    delete nullNode;
    delete header;
}

一个二叉查找树的insert

//这时的insert其实就是一个普通的
//二叉查找树的insert, 完全没要照顾到
//二叉树的平衡, 以及红黑规则的实现
template <typename Type>
void RedBlackTree<Type>::insert(const Type &data)
{
    great = grand = parent = current = header;
    //在此处令nullNode成为data, 以作哨兵
    nullNode->element = data;

    while (current->element != data)
    {
        //让祖父成为曾祖父, 父亲成为祖父, 自己成为父亲
        //每个人都长了一辈
        great = grand;
        grand = parent;
        parent = current;

        current = (data < current->element) ? current->left
                  : current->right;
    }

    //如果树中包含相同的元素
    if (current != nullNode)
        throw DuplicateItemException();

    current = new Node(data, nullNode, nullNode);
    if (data < parent->element)
        parent->left = current;
    else
        parent->right = current;


    //在后续的版本上,需要加上自动平衡(即实现红黑规则) -> 红黑树
}

单旋转

注意点:内侧孙子节点横向移动(注意下图结点37);

左(单)旋:

    当在某个结点k1上，做左旋操作时，我们假设它的右孩子k2不是NIL[T](k1可以是任何不是NIL[T]的左孩子结点); 左旋以k1到k2之间的链为“支轴”进行，它使k2成为该子树新的根，而k2的左孩子B则成为k1的右孩子。 

//实现
//向左转
template <typename Type>
void RedBlackTree<Type>::rotateWithRightChild(Node *& k1) const
{
    Node *k2 = k1->right;
    //结点B横向移动
    k1->right = k2->left;

    //令k2提领k1
    k2->left = k1;
    //令k2为根(使k2替代k1的位置)
    k1 = k2;
}

右(单)旋:

过程与左旋类似;

//实现
//向右转
template <typename Type>
void RedBlackTree<Type>::rotateWithLeftChild(Node *& k2) const
{
    //首先将B横向移动
    Node *k1 = k2->left;
    k2->left = k1->right;

    //令k1提领k2
    k1->right = k2;
    //令k1为根(使k1替代k2的位置)
    k2 = k1;
}

测试(在完成单旋转之后):

     (构造一颗二叉查找树树如图所示, 左边为尚未旋转之前, 右为旋转之后)

//测试代码如下:
int main()
{
    //用NEG_INF来代表负无穷大
    const int NEG_INF = -999999;
    RedBlackTree<int> tree(NEG_INF);

    //单旋转时候的测试数据
    tree.insert(30);
    tree.insert(15);
    tree.insert(70);
    tree.insert(20);

    cout << tree.header->right->element << endl;
    cout << tree.header->right->left->element << endl;
    cout << tree.header->right->right->element << endl;
    cout << tree.header->right->left->right->element << endl;   //20

    //向右旋转
    cout << "向右旋转" << endl;
    tree.rotateWithLeftChild(tree.header->right);
    cout << tree.header->right->element << endl;    //15
    cout << tree.header->right->right->element << endl; //30
    cout << tree.header->right->right->left->element << endl;   //20
    cout << tree.header->right->right->right->element << endl;   //70

    //然后再向左转(又转了回来)
    cout << "向左旋转" << endl;
    tree.rotateWithRightChild(tree.header->right);
    cout << tree.header->right->element << endl;
    cout << tree.header->right->left->element << endl;
    cout << tree.header->right->right->element << endl;
    cout << tree.header->right->left->right->element << endl;   //20

    return 0;
}

数据结构基础(18) --红黑树的设计与实现(1)