红黑树的插入与删除

1、何为红黑树？

开门见山地说，红黑树是一种平衡的二叉查找树。与AVL树类似，它对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。在基础的二叉搜索树的插入与删除所需的时间下，它只需要对节点的旋转、对节点变色等等的额外操作，因此在操作时间可维持在 O ( log ? n )下。

2、红黑树维持的规则？

红黑树在满足基础的二叉搜索树的规则下（即每个节点都大于它的左子树，小于它的右子树），还需要满足如下规则：

规则	内容
规则1	节点为红色或黑色
规则2	根节点为黑色
规则3	所有的叶节点都为黑色（指向空指针nullptr）
规则4	每个红色节点的儿子都为黑色
规则5	任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点

通过以上规则，我们可以总结出来以下一些结论：

结论	内容
结论1	任意两个红色节点不能够相连。（因为红色节点的孩子必须是黑色的，因此可以推出它的父亲节点必须是黑色的）；
结论2	每个节点的黑高必须相同。（在这里的黑高指该节点到它所能够到达的所有叶节点的简单路径所包含的黑色结点数目）。

3、红黑树的插入节点时的维护？

在对红黑树进行插入节点操作时，我们讨论以下何时它的规则会遭到破坏：

规则1、2、3不会收到破坏；
规则4在增加红色节点、将黑节点涂红，旋转时被破坏；
规则5在增加黑色节点、将红节点涂黑，旋转时被破坏；

而我们发现，在进行插入时会破坏的规则4、5与推导出来的结论1、2是完全等价的，我们在接下来的维护过程中会反复使用这些规则。

对于不同的情况，我们分情况对其进行维护；
首先，我们规定新插入的节点必定涂成红色，并且定义新插入的节点为 N、它的父亲节点为 P、它的祖父节点为 G、它的叔叔节点（父亲节点的兄弟）为 U。

情况一：

若插入时树是个空树，即没有父节点，那么将节点涂黑，直接插入。
情况二：

若插入时父节点为黑色，那么我们发现规则1、2都没有被破坏（插入的是红色节点但是父亲节点是黑色，并且任意一个节点的黑高不变），直接插入即可。
情况三：

若插入时其父节点为红色，且其叔节点为红色，那么根据结论1，其祖父节点必然为黑色。如图：

此时新增节点破坏了结论1，我们该考虑的是如何在解决破坏的结论（两红相邻）1的同时不破坏结论2（黑高相同）。
很显然，我们只需要将父亲节点和叔叔节点涂成黑色，将祖父节点涂成红色，这样维持了两个红色节点不相邻且黑高不变。如图：
但是，这样就大功告成了吗？显然没有。因为我们将祖父节点重新涂色，并不能保证祖父节点带来的改变会维持整个红黑树的性质。
因此，我们需要将祖父节点作为目标节点，从头开始进行各种情况的判断。
情况四：

若插入新节点时其父节点为红色，且其叔节点为黑色 且该节点与父亲节点的关系和父亲节点与祖父节点的关系相同（这里以该节点与父亲节点都是其父节点的左孩子为例），那么根据结论1，其祖父节点必然为黑色。

如图：

此时新增的节点破坏了结论1，而我们讨论该如何维持二叉树的性质呢？

很显然，单纯的变色操作已经不能维持二叉树使其同时满足结论1和2，那么我们尝试采用另一种搜索二叉树采用的、可以改变树的拓扑结构且不会改变搜索二叉树的性质的操作——旋转。

我们尝试对父亲节点向右旋转 （当然，如果你的情况是“该节点与父亲节点都是其父节点的左孩子”，那么要进行左旋转），并且重新将父节点涂成黑色，祖父节点涂成红色满足 黑高不变。

如图：
情况五：若插入新节点时其父节点为红色，且其叔节点为黑色 且该节点与父亲节点的关系和父亲节点与祖父节点的关系不相同（这里以该节点是父亲的左节点，且父亲节点是祖父节点的右孩子为例），那么根据结论1，其祖父节点必然为黑色。

我们很容易发现，这种情况与情况四只相差了一个字，即该节点与父亲节点的关系和父亲节点与祖父节点的关系不相同。

如图：

此时，与情况四相同，结论1受到了破坏的威胁。

我们可以对父亲节点做一次左旋，那么我们发现此时就与情况四类似了。于是我们把旋转后的父节点当作此节点，对其进行一次情况四的操作。如图：（当然，我们可以理解为整个操作为一次左右双旋。）

如图：删除操作过几日更新~