定义
红黑树是一棵二叉搜索树，在其每个节点上增加了一个属性表示节点的颜色，对任意一条从根到叶子的简单路径上各节点颜色的约束，使得红黑树不存在一条路径比其它路径长出两倍。
性质
- 每个节点是红色或者是黑色
- 根节点是黑色
- 每个叶节点(NIL)是黑色
- 如果一个节点是红色的，则它的两个子节点都是黑色的
- 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
[注] 这里所谓的叶节点指的是正常的叶节点下的节点，为NIL，属性为黑色,也就是说正常的叶节点的黑高一定是1
定理证明
一棵有n个内部节点的红黑树的高度至多为2lg(n+1)
先说明一下定义：
叶子结点：前面有讲到，指的是NIL
内部节点：排除NIL后的节点，即x为根的内部节点是包括x的
先证明任一节点x为根的子树中至少包含2^bh(x)-1个内部节点
使用归纳法可证
当bh(x)=0时，表示x为叶节点，x没有子树，成立
对一个有左右子树的x节点分析，其左右子树的黑高为bh(x)或者是bh(x-1) 【这里我不知道为什么要分析既有左子树又有右子树的情况】
假设以x的子节点为根的子树中至少包含2^bh(x-1)-1个内部节点成立，对于x而言，其包含的节点数为(2^bh(x-1)-1)+(2^bh(x-1)-1)+1=2^bh(x)-1,得证。
继续分析，上面证明中bh(x)表示的是黑高，由性质4可以得出，从x到叶子节点的路径上至少有一半的黑色节点，因此对于以x为根节点高度为h的树一定有：bh(x)>=h/2
假设以x为根的树有n个节点，可得n>=2^bh(x)-1，有n>=2^(h/2)-1
即h<=2lg(n+1),证明原命题
旋转
旋转分为左旋和右旋，旋转时按照二叉树的性质来安排节点的位置，旋转的意义在于改变了节点的黑高
