红黑树

是一种特殊的平衡二叉树

满足如下几个条件：

1、结点是红色或黑色的
2、根结点始终是黑色的
3、叶子结点也都是黑色的 （当红色结点无左右孩子时，补足空结点是黑色的）
4、红色结点的子结点都是黑色的
5、对任一结点，到叶子结点的所有路径，都包含相同数目的黑色结点

特征： 从根结点到叶子结点的最长路径，不会超过最短路径的两倍

当插入新结点使红黑树失去平衡时，通过两种方式恢复平衡：

旋转和变色 （红变黑 黑变红）

可视化网站：树结构可视化

插入结点到红黑树的逻辑

约定 新插入的结点都设为红色的，可以简化树的平衡过程

假设要插入的结点是X 父结点是P 祖父结点是G 叔父结点是U

1）X是根结点
放入根结点中，将颜色变为黑色

2）X的父结点是黑色的

3）X的父结点是红色的

​ a) 如果叔父结点U也是红色的，可以推断出祖父结点G必是黑色的

​ 当增加新结点时 造成两个红色结点相邻 此时使用变色处理
​ P和U由从红色变为黑色 G由黑色变为红色 如果G是根结点 再次恢复为黑色

​ b) 如果叔父结点U是黑色的，并且X在左侧

​ 以P为中心，向右旋转，G和U下移，此时如果P有右孩子，右孩子R移动到G的左孩子处
​ 将P变为黑色 将G变为红色

此为举例 插入16的场景

c) 如果叔父结点U是黑色的，并且X在右侧

​ 先通过左旋 恢复成第二种情况 然后再右旋和变色

以插入19举例