红黑树旋转规则总结

红黑树的定义

1.   任何一个节点非红即黑；
   

2.   树的根为黑色；
   

3.   叶子节点为黑色(注意：红黑树的所有叶子节点都指的是Nil节点)；
   

4.   任何两个父子节点不可能同时为红色；
   

5.   任何节点到其所有分枝叶子的简单路径上的黑节点个数相同；
   

插入

插入的是红色（因为红黑树的性质中有一条，根节点到任意叶子节点的黑色节点相同，插入红色降低调整概率）
①当父节点是黑色，没有问题，直接插入，不会破坏平衡。
②当父节点是红色，且叔父同色（父节点和叔叔节点颜色相同），此时只需要变色
变色规则：把父和叔同时变成黑色，祖父变成红色，然后再把祖父当做当前节点，继续向上判断颜色，知道平衡
③当父节点是红色，且叔父不同色，这种情况需要旋转加变色处理

一次旋转的情况：左左（右旋），右右（左旋）
什么意思呢？即新节点在父节点的左边，父节点也在祖父节点的左边，此时，只需以父节点为轴，一次右旋转即可。然后根据第②点，修正颜色即可
右右的情况刚好相反，不用赘述

两次旋转的情况：右左（先左旋转，再右旋转），左右（先右旋转，再左旋转）
即插入的新节点是父亲的右节点，而父亲是祖父的左节点，此时，先以父节点为轴，左旋转，左旋之后，情况变成了左左，此时，再以父节点为轴，进行一次右旋，然后根据第②点改变颜色即可达到平衡
左右情况和右左情况相反，操作也正好对称，不再赘述
可以根据上述的规则，随意插入一组数据，来验证是否正确，红黑树生成网址https://www.cs.usfca.edu/~galles/visualization/RedBlack.html