红黑树

     在学习红黑树之前，先看一下二叉排序树及平衡二叉树的特性：

一、二叉排序树

1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3. 它的左、右子树也分别为二叉排序树。

 

二、平衡二叉树

     它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

三、红黑树

    红黑树首先是一颗二叉排序树，除此之外它还具有如下特性：

        1.节点非红即黑；

        2.根节点是黑色；

        3.所有NULL结点称为叶子节点，且认为颜色为黑；

        4.所有红节点的子节点都为黑色；

        5.从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点；

关于红黑树的详细介绍请参见：http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html

构建红黑树步骤请参见：http://blog.csdn.net/jimoshuicao/article/details/8618043

                               http://wangkuiwu.github.io/2013/02/05/rbtree01/