红黑树详解
由于****博客的排版实在是太过麻烦，调来调去的也不好看，故使用线下已经排好的截图来发表
前言：
红黑树是在二叉搜索树的基础上添加了对颜色的处理，故如对二叉树不熟悉的可以先了解上一篇对二叉树的介绍http://blog.****.net/a_zhenzhen/article/details/78829892
设红黑树的高为h，则树的黑高最小为h/2; n为红黑树的结点数，则
n >= 2^(h/2)-1
即 n + 1 >= 2^(h/2) -------> lg(n+1)>=h/2 即 h<= 2lg(n+1)
左旋与右旋
左旋伪代码
右旋伪代码
红黑树需要满足的性质
- 每个结点或是红色的，或是黑色的
- 根结点是黑色的
- 每个叶子结点（NIL）都是黑色的
- 如果一个结点是红色的，则它的两个子结点都是黑色的。
- 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的