摘自 https://blog.csdn.net/qq_26323323/article/details/79643216
1.红黑树
红黑树本身也是一种二叉树，只不过是一种比较特殊的二叉树
二叉树如果插入的数值是有序时，二叉树就是非平衡的，基本跟链表类似了（时间复杂度O(N)）
针对这种情况，就产生了红黑树，这种树在插入的过程中，会通过一系列的方式来保持树的平衡，使其时间复杂度一直维持在O(logN)
2.红黑树规则
* 每一个节点不是黑色就是红色
* 根节点总是黑色的
* 如果节点是红色的，则它的子节点必须是黑色的（反之则不一定）
* 从根到叶节点的每条路径，包含的黑色节点数目必须相同
3.红黑树修正违规操作简介
红黑树之所以能够保持平衡，是因为严格遵守了上述规则
在插入的过程中，如果某节点违反了以上规则，则需要进行修正，修正的方式包括：改变颜色、旋转
1）术语
为了平衡一棵树，需要对某些节点进行重新排列，将一些节点上升，将一些节点下降，以此来帮助树平衡。
切记：在树平衡操作的过程中不能破坏二叉树的特点（一个节点的左子节点的关键字值小于这个节点，右子节点的关键字值大于或等于这个父节点）
旋转之前先了解一些基本概念：
* 外侧子孙
12在18的左侧，18在25的左侧，它们的相对父节点位置相同，则称新插入的节点12为外侧子孙节点
38在35的右侧，35在25的右侧，它们的相对父节点位置相同，则称新插入的节点38为外侧子孙节点
* 内侧子孙
22在18的右侧，18在25的左侧，它们的相对父节点位置不同，则称新插入的节点22为内侧子孙节点
30在35的左侧，35在25的右侧，它们的相对父节点位置不同，则称新插入的节点30为内侧子孙节点
可以看到，在插入新节点之前的树都是平衡的，但是插入新节点之后就会违反规则3，故需要对这些树进行修正（看到子节点和父节点都是红色的，就要想到使用旋转来保持树的平衡）
* 右旋转
当以35为顶端元素进行右旋转时，需要注意：该顶端元素必须有一个左子元素
右旋结果如下：
35下移，30上移到35的位置，20位置不变，依旧是30的左子元素
* 左旋转
当以30为顶端元素进行左旋转时，需要注意：该顶端元素必须有一个右子节点
左旋结果如下：
30下移到左侧，35上移到30的位置，45位置不变，依旧是35的右子节点
2）颜色变换
场景：当在插入的过程中遇到一个黑色节点下有两个红色节点，则需要进行颜色变换
示例：
当前场景下，是符合红黑树规则的，如果此时再插入一个节点，按照规则3，则新节点只能是黑色的，但是这样就会违反规则4，所以对现有节点进行变色
* 把25、75两个子节点变色为黑色
* 再新插入节点为红色即可
操作完成之后的树为
3）外侧子孙的旋转平衡术
上述这种情况，找到新插入节点38的祖父节点25，以25为顶端，进行左旋转
4）内侧子孙的旋转平衡术
上述这种情况，找到新插入节点22的父节点18，然后以18位顶端，进行左旋转，旋转后结果如下
然后以22的父节点25进行右旋转，旋转结果如下
再修改22和18、25节点的颜色，即保持树的正确
总结：外侧子孙和内侧子孙的平衡都是需要进行旋转，不同的是外侧子孙只需要进行一次旋转即可，而内侧子孙则需要进行两次旋转，第一次旋转后变成外侧子孙的模式，再根据外侧子孙的方式来进行平衡即可
3.插入新节点
红黑树插入新节点的过程中，会遇到违背红黑树规则的情况，为了保持树的平衡，则需要使用以上的几种方式来保持树平衡
下面介绍下以下几种插入新节点过程中遇到的问题及其解决方案：
为什么这种情况是会违背红黑树规则呢？因为根据规则3，红色节点下的子节点必须为黑色节点，那么插入黑色子节点后就会违背规则4，所以碰到这种情况，需要对这三个节点进行颜色变换
当再插入12节点时，就会与18节点产生颜色冲突，所以需要对18 25 30三个节点进行颜色变换，变换成如下，再插入12节点即可
2）插入节点后发生颜色冲突
接着上个树来继续添加节点6
发现6节点和12节点都是红色，违背规则3，则根据上述外侧子孙节点处理方案对6的祖父节点18进行右转
此时12和25节点都是红色，同样违背规则3，对12的祖父节点50节点进行右转
再对上述节点颜色错误的进行颜色变换，25、12、6节点都变成黑色，即变成一颗复合规则的红黑树
3）插入过程中发生颜色冲突
以上节点属于平衡状态，此时如果再插入节点3，则需要对12、6、18节点进行颜色变换操作
再改变25和12的颜色为黑色，以符合规则2和4
此时已经平衡，再插入节点3即可，结果如下
总结：针对于红红冲突，需要找到合适的祖父节点，然后进行旋转，再进行节点颜色变换，则就可以保持树的平衡
至于代码实现，可以参考TreeMap
参考：Java数据结构和算法（第二版）