红黑树

1. 红-黑树的特征

平衡二叉搜索树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树.

时间复杂度：
常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^{2)、立方阶O(n}3)、k次方阶O(n^{k)、指数阶O(2}n)。
https://blog.csdn.net/m0_37854317/article/details/70491581

二叉搜索树作为一种数据结构，其查找、插入和删除操作的时间复杂度都为O(logn),底数为2。
如果插入的数据是随机的，则效率很高，但是如果插入的数据是有序的，比如10,20,30,40,50插入到二叉搜索树中：
这和链表没有任何区别了，查找的时间复杂度为O(N)，而不是O(logN)。
当然这是在最不平衡的条件下，实际情况下，二叉搜索树的效率应该在O(N)和O(logN)之间，这取决于树的不平衡程度。

红黑规则
1.每个节点不是红色就是黑色的；
　　2.根节点总是黑色的
　　3.如果节点是红色的，则它的子节点必须是黑色的（反之不一定）,(也就是从每个叶子到根的所有路径上不能有两个连续的红色节点)；
　　4.从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）
新插入的节点颜色总是红色的，这是因为插入一个红色节点比插入一个黑色节点违背红-黑规则的可能性更小

效率
红黑树的查找、插入和删除时间复杂度都为O(log2N)，额外的开销是每个节点的存储空间都稍微增加了一点，因为一个存储红黑树节点的颜色变量。
插入和删除的时间要增加一个常数因子，因为要进行旋转，平均一次插入大约需要一次旋转，因此插入的时间复杂度还是O(log2N)
(时间复杂度的计算省略常数)，但实际上比普通的二叉树是要慢的。

大多数应用中，查找的次数比插入和删除的次数多，所以应用红黑树取代普通的二叉搜索树总体上不会有太多的时间开销。
而且红黑树的优点是对于有序数据的操作不会慢到O(N)的时间复杂度。

2. 红-黑树的自我修正
   在新增节点或者删除节点之后，可能会破坏二叉树的平衡。通过三种方式对平衡进行修正
   改变颜色是为了帮助判断何时旋转，而旋转是为了保证树的平衡。光改变节点颜色是不能起到任何作用的，旋转才是关键的操作，
   节点本身是不会旋转的，旋转改变的是节点之间的关系。选择一个节点作为旋转的顶端，如果做一次右旋，
   这个顶端节点会向下和向右移动到它右子节点的位置，它的左子节点会上移到它原来的位置。

①、改变节点颜色
　　②、右旋
　 右旋的顶端节点必须要有左子节点。
　　③、左旋
左旋的顶端节点必须要有右子节点。

3. 插入
   如果是第一次插入，由于原树为空，所以只要把根节点涂黑即可；
   如果插入节点的父节点是黑色的，那不会违背红-黑树的规则，什么也不需要做；
   但是插入节点的父节点是红色的，有如下三种情况，就要开始变色和旋转：

①、插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色。

此时肯定存在祖父节点，但是不知道父节点是其左子节点还是右子节点，但是由于对称性，我们只要讨论出一边的情况。
这种情况，将当前节点(4) 的父节点(5) 和叔叔节点(8) 涂黑，将祖父节点(7)涂红。
再将当前节点指向其祖父节点，再次从新的当前节点开始算法（具体看下面的步骤）。这样上右图就变成情况2了。

②、插入节点的父节点是红色的，叔叔节点是黑色的，且插入节点是其父节点的右子节点。

③、插入节点的父节点是红色的，叔叔节点是黑色的，且插入节点是其父节点的左子节点。