从二叉查找树到二叉平衡树
二叉查找树：左子树都比根小右子树都比根大，但是极端情况下二叉查找树会变成一棵单链表，查找时间复杂度会变成O(n)。为了解决这个问题引出平衡二叉树。----》为了查找的时间复杂度
平衡二叉树：具备二叉查找树的一切特性，但是其 每个节点 的左右子树高度差之多为1.
队友有n个节点的平衡二叉树，最坏的查找时间复杂度也为O(logn).
所以为什么还需要红黑树呢？
虽然平衡二叉树解决了 二叉查找树会退化成单链表的问题，能够把查找时间复杂度控制在O(logn),但是平衡二叉树严格要求 每个节点的左右子树高度差至多等于1，导致每次插入删除节点几乎都会破坏平衡二叉树的平衡，需要左旋右旋来调整，
显然如果插入、删除频繁的场景中平衡树需要跟着频繁的调整，会使平衡树的性能大很大的折扣。
----》为了解决插入删除需要频繁调整的问题
红黑树：具有二叉查找树的特点。{
根节点是黑色的，每个叶子节点都是黑色的空节点
红色节点不能毗邻，也就是说红色节点需要被黑色节点隔离开
每个节点 到达它 所有可达叶子路径上都包含有相同的黑色节点，
}
红黑树和AVL树类似都是在插入和删除操作时通过特定的操作保持二叉树的平衡，从而获得较高的查找性能。
红黑树Red Black Tree，也是一种自平衡的二叉查找树。除了满足二叉查找树的特性外，还应有：
1.结点是 红色或黑色
2.根结点是 黑色
3.每个叶子结点都是 黑色的 空结点(nil)
4.每个红色结点的两个子结点都是 黑色(从 每个叶子结点到根的所有路径上不能有连续的两个红色结点)
//保证路径不能有两个毗pi连的红色结点
//最短的路径可能都是 黑色结点。最长的路径可能是 交替的红色、黑色结点。
//结合5，没有路径能是其他路径的两倍长。
5.从任一结点到 其 每个叶子的所有路径都包含相同数目的黑色结点。
//一棵空的红黑树就是就是一棵满足所有性质要求的红黑树。插入
1.每个新插入的结点都 赋为红色。因为如果赋黑色 就一定会 破坏性质5.
但是如果插入红色的话可能会 破坏性质4.2.如果破坏了性质4，就需要调整部分结点。
2.1 如果插入的是根节点。因为这个时候插入的是 红色，会破坏性质2。|简单的改变根节点颜色即可。
2.2 插入的不是根结点，且这个结点 父结点是黑色。没有破坏。不需要调整。
2.3 插入的不是根节点，父结点 是红色--它爷爷只能是黑色。破坏了性质4.这个时候还可以再细分3种情况。
1.z是左孩子，且z叔叔是红色
它爹和它叔都是红色，所有它爷爷一定存在且是黑色。
可以将它 爸和它叔 都改为黑色，再将它爷爷改为红色。//这样保证了性质5
但是它爷爷变成了红色可能会破坏性质4，同样的问题就向上转移了。
如果还是 1，则继续向上转移。直到不再是1.
这可能会有新的 四种可能：
一：变为2
二：变为3
三：结点上移到根的子结点，因为根是黑色的，所有结束。
四：上移到根结点。这里需要将根节点重新改色为黑色。
2.z是左孩子，z叔叔是黑色
z的父结点左旋，即可转为3.
3.z是右孩子，z叔叔是黑色
z爹改为黑色，z爷爷改为红色，再对爷爷右旋，即可恢复性质4.