红黑树简介
Contents
R-B Tree，全称 Red-Black Tree，又称“红黑树”，它是一种特殊的二叉查找树。红黑树的每个节点上都有储存位表示节点的颜色，可以是Red或Black。
红黑树的特性：
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶子节点都是黑色的空节点（NIL节点）。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（简称黑高）。
红黑树的应用
红黑苏的应用比较广泛，主要是用它来储存有序数据，它的事件复杂度是O(logn)，效率非常高。 例如，Java集合中TreeSet和TreeMap都是通过红黑树去实现的。
红黑树的时间复杂度和相关证明
红黑树的时间复杂度为：O(logn)
红黑树的操作
旋转操作
旋转操作分为左旋和右旋，左旋是将某个节点旋转为其右孩子的左孩子，而右旋是节点旋转为其左孩子的右孩子。
上图保安了左旋和右旋的示意图，这里以右旋为例进行说明，右旋节点M的步骤如下：
- 将节点M的左孩子引用执行E节点的右孩子
- 将节点E的有孩子引用指向节点M，完成旋转
插入
红黑树的插入过程和二叉查找树的过程基本相似，不同的地方在于，红黑树插入新节点后，需要进行调整，以满足红黑树的性质。 性质1规定红黑树节点的颜色要么是红色要么是黑色，那么插入新节点时，这个节点应该是红色还是黑色呢？答案是红色，原因不难理解。如果插入的节点时黑色，那么这个节点所在的路径比其他路径多出一个黑色节点，这个调整起来会比较麻烦（参考红黑树的删除操作，就知道为啥多一个或少一个黑色节点时，调整起来这么麻烦了）。如果插入的节点时红色，此时所有路径上的黑色节点数量不变，仅可能会可先两个连续的红色节点的情况。这种情况下，通过变色和旋转进行调整即可，比之前简单多了。
接下来，将分析插入红色节点后红黑树的情况，这里假设要插入的节点为N，N的父节点为P，祖父节点为G，叔叔节点为U，插入红色节点后，会出现5种情况，分别如下：
情况一
插入的新节点N为红黑树的根节点，这种情况下，我们把节点N的颜色由红色变为黑色，性质2（根是黑色）被满足。同时N被染成黑色后，红黑树所有路径上的黑色节点数量增加一个，性子5（黑高）仍然满足。
情况二
N的父节点是黑色，这种情况下，性质4（每个节点必须有两个黑色子节点）和性质5没有收到影响，不需要调整。
情况三
N的父节点是红色（节点P为红色，其父节点必然为黑色），叔叔节点U也是红色。由于P和N均为红色，所以性质4被打破，此时需要进行调整。这种情况下，先将P和U的变为黑色。此时经过G的路径上的黑色节点数量不变，性质5仍然满足。但是需要注意的是G被染成红色后，可能会导致它的父节点形成连续的红色节点，此时需要递归向上调整。
情况四
N的父节点为红色，叔叔节点为黑色。节点N时P的右孩子，且节点P是G的左孩子。此时先对节点P进行左旋，调整N与P的位置。接下来按照情况五进行产后处理，以恢复性质4。
情况五
N 的父节点为红色，叔叔节点为黑色。N 是 P 的左孩子，且节点 P 是 G 的左孩子。此时对 G 进行右旋，调整 P 和 G 的位置，并互换颜色。经过这样的调整后，性质4被恢复，同时也未破坏性质5。
插入总结
上面五种情况中，情况一和情况二比较简单，情况三、四、五稍复杂。但如果细心观察，会发现这三种情况的区别在于叔叔节点的颜色，如果叔叔节点为红色，直接变色即可。如果叔叔节点为黑色，则需要选选择，再交换颜色。当把这三种情况的图画在一起就区别就比较容易观察了，如下图：
删除
相较于插入操作，红黑树的删除操作则要更为复杂一些。删除操作首先要确定待删除节点有几个孩子，如果有两个孩子，不能直接删除该节点。而是要先找到该节点的前驱（该节点左子树中最大的节点）或者后继（该节点右子树中最小的节点），然后将前驱或者后继的值复制到要删除的节点中，最后再将前驱或后继删除。由于前驱和后继至多只有一个孩子节点，这样我们就把原来要删除的节点有两个孩子的问题转化为只有一个孩子节点的问题，问题被简化了一些。我们并不关心最终被删除的节点是否是我们开始想要删除的那个节点，只要节点里的值最终被删除就行了，至于树结构如何变化，这个并不重要。
红黑树删除操作的复杂度在于删除节点的颜色，当删除的节点是红色时，直接拿其孩子节点补空位即可。因为删除红色节点，性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点）仍能够被满足。当删除的节点是黑色时，那么所有经过该节点的路径上的黑节点数量少了一个，破坏了性质5。如果该节点的孩子为红色，直接拿孩子节点替换被删除的节点，并将孩子节点染成黑色，即可恢复性质5。但如果孩子节点为黑色，处理起来就要复杂的多。分为6种情况，下面会展开说明。
在展开说明之前，我们先做一些假设，方便说明。这里假设最终被删除的节点为X（至多只有一个孩子节点），其孩子节点为N，X的兄弟节点为S，S的左节点为 SL，右节点为 SR。接下来讨论是建立在节点 X 被删除，节点 N 替换X的基础上进行的。这里说明把被删除的节点X特地拎出来说一下的原因是防止大家误以为节点N会被删除，不然后面就会看不明白。
情况一
N 是新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。
上面是维基百科中关于红黑树删除的情况一说明，由于没有配图，看的有点晕。经过思考，我觉得可能会是下面这种情形：
要删除的节点 X 是根节点，且左右孩子节点均为空节点，此时将节点 X 用空节点替换完成删除操作。
可能还有其他情形，大家如果知道，烦请告知。
情况二
S 为红色，其他节点为黑色。这种情况下可以对 N 的父节点进行左旋操作，然后互换 P 与 S 颜色。但这并未结束，经过节点 P 和 N 的路径删除前有3个黑色节点（P -> X -> N），现在只剩两个了（P -> N）。比未经过 N 的路径少一个黑色节点，性质5仍不满足，还需要继续调整。不过此时可以按照情况四、五、六进行调整。
情况三
N 的父节点，兄弟节点 S 和 S 的孩子节点均为黑色。这种情况下可以简单的把 S 染成红色，所有经过 S 的路径比之前少了一个黑色节点，这样经过 N 的路径和经过 S 的路径黑色节点数量一致了。但经过 P 的路径比不经过 P 的路径少一个黑色节点，此时需要从情况一开始对 P 进行平衡处理。
情况四
N 的父节点是红色，S 和 S 孩子为黑色。这种情况比较简单，我们只需交换 P 和 S 颜色即可。这样所有通过 N 的路径上增加了一个黑色节点，所有通过 S 的节点的路径必然也通过 P 节点，由于 P 与 S 只是互换颜色，并不影响这些路径。
情况五
S 为黑色，S 的左孩子为红色，右孩子为黑色。N 的父节点颜色可红可黑，且 N 是 P 左孩子。这种情况下对 S 进行右旋操作，并互换 S 和 SL 的颜色。此时，所有路径上的黑色数量仍然相等，N 兄弟节点的由 S 变为了 SL，而 SL 的右孩子变为红色。接下来我们到情况六继续分析。
情况六
S 为黑色，S 的右孩子为红色。N 的父节点颜色可红可黑，且 N 是其父节点左孩子。这种情况下，我们对 P 进行左旋操作，并互换 P 和 S 的颜色，并将 SR 变为黑色。因为 P 变为黑色，所以经过 N 的路径多了一个黑色节点，经过 N 的路径上的黑色节点与删除前的数量一致。对于不经过 N 的路径，则有以下两种情况：
- 该路径经过 N 新的兄弟节点 SL ，那它之前必然经过 S 和 P。而 S 和 P 现在只是交换颜色，对于经过 SL 的路径不影响。
- 该路径经过 N 新的叔叔节点 SR，那它之前必然经过 P、 S 和 SR，而现在它只经过 S 和 SR。在对 P 进行左旋，并与 S 换色后，经过 SR 的路径少了一个黑色节点，性质5被打破。另外，由于 S 的颜色可红可黑，如果 S 是红色的话，会与 SR 形成连续的红色节点，打破性质4（每个红色节点必须有两个黑色的子节点）。此时仅需将 SR 由红色变为黑色即可同时恢复性质4和性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。）。
删除总结
红黑树删除的情况比较多，大家刚开始看的时候可能会比较晕。可能会产生这样的疑问，为啥红黑树会有这种删除情况，为啥又会有另一种情况，它们之间有什么联系和区别？和大家一样，我刚开始看的时候也有这样的困惑，直到我把所有情况对应的图形画在一起时，拨云见日，一切都明了了。此时天空中出现了4个字，原来如此、原来如此、原来如此。所以，请看图吧：
参考：
Author zhangwlhaut
LastMod 2019-03-21