红黑树
是一种特殊的平衡二叉树
满足如下几个条件：
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举例
