红黑树(Red-Black Tree)

1.来由

         二叉搜索树在一般情况下，均可以以O(log n)的效率高效的维护查找，插入，删除这三个操作；

        但是当数据本来就有序的极端情况下就会使得构建的二叉搜索树变成链表的状态，使得效率退化成O(n);

        而平衡二叉树(AVL树)通过旋转的操作时刻使二叉搜索树保持平衡的状态以位置最佳的效率，从而避免二叉搜索树出现向上的极端情况；

       而红黑树和AVL树一样都是一种二叉搜索树，是对二叉搜索树的平衡的另一种思想。

2.定义

2.1左根右

前提是其为二叉搜索树，也即左子树<根结点<右子树。

2.2根叶黑

根和叶子结点都是黑色。

2.3不红红

红色结点的左右孩子必须是黑色，也即从上到下不能出现两个连续的红色结点。

2.4黑路同

任意结点到叶所有路径中的黑色结点数量必须相同。

3.性质

最长路径绝对不会超过最短路径的两倍。

        因为不能连续出现两个红色结点，所以必然在一条路径上是间隔出现黑红两种结点的，这样最长路径断然不可能超过最短路径的两倍。 

可以看到AVL树对平衡控制的更加严格，这就导致了红黑树的查找速率略低于AVL树；

       而正是因为这个原因，也导致AVL树在构建，插入，删除时需要进行旋转调整的次数更多。

也即：

AVL树	红黑树
查询高效	插入和删除高效

4.插入

4.1默认插入的结点为红色

插入结点的颜色为红色的影响更小，且只会违反“根叶黑”和“不红红”的性质。 

4.2三种失衡情况 

 4.2.1插入的结点是根节点

直接变黑即可： 

4.2.2插入的结点的叔叔是红色 

叔父变色，爷爷变插入结点： 

这个时候就继续判定和调整： 

4.2.3插入的结点的叔叔是黑色 

判断是需要(LL,RR,LR,RL)旋转,然后变色： 

LL

旋转点和中心点变色： 

RR

旋转点和中心点变色： 

LR

 

旋转点和中心点变色： 

RL 

然后对旋转点和旋转中心点变色： 

5.构建

……