红黑树RB-Tree
红黑树是类似于AVL树，那为什么还需要引入红黑树呢？
红黑树可以保证的是最长路径不超过最短路径的2倍，从而保证近似平衡。这样做有什么好处呢，因为这样可以使得旋转次数相比AVL树较少，同时也可以保证树高是O(log n)，使得查找速度是O(log n)，在实作上效率比较高。
首先明确下红黑树满足的性质有：
结点为黑色或者红色
根结点为黑色
每个叶子结点都是黑色
一个结点为红色的话，它的两个孩子都是黑色
一个结点到任一叶子结点的路径中黑色结点个数相同（不包含该结点）
左旋中的“左”，意味着“被旋转的节点将变成一个左节点”。
右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。
插入结点的时候为什么是将结点涂成红色而不是黑色呢？
原因是为了处理的方便，回顾红黑树的性质我们知道，红黑树的任一结点到叶子结点的黑色结点个数是相同的，所以如果插入了黑色结点，那么立马就不满足这个性质了，导致处理起来较为麻烦。如果插入的是红色，就不会违反这个性质，剩下的只需要调整满足其他性质即可。
这里我们需要根据性质来思考，首先如果插入黑节点，这个可以直接插入无论它的父亲是什么颜色，但是红黑树的性质是每条路径的黑色节点数目相同这个时候你再想想那其他路径的黑色节点数目一定比你现在少一个节点，所以调整起来是非常繁琐的. 插入红节点不需要调整其他路径，如果它的父亲为黑，那么直接插入，如果他的父亲为红那么在该路径上面开始分情况调整. 所以插入节点默认颜色一定要为红.如果为黑调节成本太大了。
插入为红色的结点为违背那些特性呢？
性质(1)：插入结点涂成红色，显然满足。
性质(2)：显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。
性质(3)：插入的话不会影响到叶子结点。
性质(4)：就有可能违背了。
插入的调整过程和AVL树很类似，但是触发旋转或者着色调整的判断条件不一样，在AVL树中是根据树的平衡因子绝对值大于1则需要进行旋转。而红黑树判断则是插入红色结点后出现两个连续红色结点，则需要进行结点调整，以及重新涂色。调整的结点位置和调整方式和AVL树是类似的，有差别的地方就是红黑树的上色问题。
为什么有n个结点的红黑树高度<=2log2(n+1)?
1) 对于一棵不同的二叉树，如果k为根节点到叶节点的最短距离，那么，由此我们可以得到
2) 依据红黑树的性质，每条路径上的黑色结点数量相同，那么可以得到n个结点的红黑树，根节点到NIL结点的路径上至多有个黑色结点。
3) 依据红黑树的性质，不能有两个连续红色的结点，可以得到黑色结点的数量至少是n/2.
以上，我们可以得到结论，n个结点的红黑树的高度是
reference
Last updated
