红黑树原理

二叉搜索树

二叉搜索树的定义

二叉搜索树（Binary Search Tree），它或者是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。

二叉搜索树：通俗地讲，以当前节点为根，其左右子树的特点：左小右大。当前节点为50时，其左子树所有节点均小于50，右子树所有节点均大于50：

节点50的左右子树也同样符合这种特点，以左子树为例（以30为根的树）：

同样的，其他的子树、子树的子树等均符合该规律（类似递归）。

二叉搜索树的查找

根据左小右大的特点，查找一个元素时，从根节点出发：

如果查找的元素比当前节点小，则到左子树找；
如果查找的元素比当前节点大，则到右子树找；
如果查找的元素等于当前节点，说明找到了；
如果直至叶子节点都找不到对应的，说明该元素不存在该树中。

二叉搜索树的插入

插入元素时，主要是找到合适的位置进行插入（类似查找）：

插入的树为空树（无节点），直接创建节点即可；
插入的树非空树：
- 如果插入的元素比当前节点小，则到左子树插入；如果左子树/节点为null，插入该处；
- 如果插入的元素比当前节点大，则到右子树插入；如果右子树/节点为null，插入该处；
- 如果插入的元素和当前节点相等，说明该元素已经存在了，直接返回。

插入节点的例子：

二叉搜索树的删除

前继节点和后继节点

二叉搜索树因为自身的特性（左小右大），中序遍历的结果必然是有序的。比如以下这棵树，其遍历的结果为：【20, 30, 35, 40, 45, 50, 55, 60, 65 70, 80】

在二叉搜索树中，前继节点表示比当前节点小的最大值，后继节点表示比当前节点大的最小值，看例子就很容易明白：比如上面【20, 30, 35, 40, 45, 50, 55, 60, 65 70, 80】中，节点50的前继节点为45，后继节点为55。在二叉搜索树中，寻找前后继节点很简单：

寻找前继节点，当前节点左转一下，然后右转一直走到底（右子节点为null时终止）：

寻找后继节点，当前节点右转一下，然后左转一直走到底（左子节点为null时终止）：

根据子节点数量进行删除处理

删除前首先要找到该节点，如果找不到，直接结束即可。找到后，可以分为以下三种情景：

无子节点，即叶子节点，直接删除即可；
只有一个子节点，用该子节点接到删除节点的父节点即可；
有两个子节点，使用前或后继节点作为替换节点，对删除节点进行数据替换，然后转移至删除替换节点即可。而此时删除后继节点时，必然是情景1或2了。如下图：

情景1：

情景2：

情景3 ：

关于情景3，无论使用前继节点还是后继节点，均可以达到同样的目的，选其一即可。

二叉搜索树的问题

极端时，搜索的时间复杂度将会降低到 O(n)，比如以下这个例子，连续插入10,20,30,40,50：

而平衡二叉搜索树（AVL树、红黑树等）就是为了解决这个问题：平衡二叉树在进行插入、删除后，会进行自平衡，从而保证其查询的时间复杂度接近于O(log2n)。如红黑树连续插入10,20,30,40,50：

红黑树

红黑树的定义

红黑树在二叉搜索树的基础上，还要求有以下性质：

节点是红色或黑色；
根节点是黑色；
不能有连续的两个红色节点。
从任一节点到其每个叶子的简单路径都包含相同数目的黑色节点。

性质3表明：红色节点的父、左子、右子只能是黑色节点，红色和红色不能直接连一起；而黑色无论红黑都可以连一起。（红色暴脾气互不相容，黑色和蔼可亲谁来都行）
性质4表明：随便选一个节点，不论从怎么走，走到最后叶子节点时，其经过路径的黑色节点数量都是相等的（所谓完全黑平衡）。
性质3和4共同决定了：最长路径的节点总数量不会超过最短路径的两倍。因为黑色节点数量要一样，红色不能连着来，从而路径全黑时最短，红黑交替时最长。
因为路径长度/高度差有了一定限制，所以称红黑树是有一定平衡性的，不会出现极端倾斜的情况。
有一些红黑树定义（比如维基百科），还有一个性质：“叶子是黑色的NULL节点”。如下所示：

引入黑色的NULL节点并不会对之前的定义产生影响（各路径都增加一个黑色节点，黑色数量依然相等），其目的更多是为了简化平衡操作的情况，平衡时可以认为：null就是黑色节点。此时只需要考虑红和黑这两种情况就行，而不用考虑非红非黑的null。

旋转

说插入之前，先来看看旋转：

旋转后，原来“左小右大”的特点不会受到影响，影响的是左右子树的高度，右旋左子树高度-1，右子树+1；左旋右子树高度-1，左子树+1。
比如某棵树的左子树高度已经达到3，而右子树只有1，只需要右旋一下，左右子树高度都将调整为2。整棵树来看，高度就相当于降低了1（3 -> 2），这就是高度的“平衡”。
旋转前首先要确定旋转的节点（姑且叫支点）是哪个，这个非常重要。比如上图右旋前，要以X为支点才能转成右侧那样，如果选择Y作为支点，则要往下一层看了（X节点将以P的角色出现）。
另外留意一下b：
- 右旋前，b是挂在Y的右子，而右旋后，挂到了X的左子了；
- 左旋前，b是挂在X的左子，而左旋后，挂到了Y的右子了。

插入平衡

开始之前，我们先约定一下名称：

红黑树属于二叉搜索树，插入动作也与二叉搜索树一致，只不过红黑树在插入之后，多了平衡动作（旋转与涂色）。

新插入的节点均为红色节点，因为红色不会影响路径上黑色节点的数量，保持性质4。如果父节点为黑色，就直接结束了；如果父节点为红色，则需要另外处理了。

以新插入的节点为当前平衡节点N，插入平衡大体上分为以下情形：

情形1. N为根节点（父节点为NULL）

当前平衡节点N为根节点时，直接涂黑根节点即可。

情形2. 父黑

父节点为黑色时，无需其他操作，已然平衡。

情形3. 父红-叔红

父红-叔红时，将父/叔节(P/U)点涂黑，祖父节点(GP)涂红；而后以祖父节点(GP)作为新的平衡节点N，递归执行平衡操作。

情形4. 父红-叔黑

情形4.1 父节点和N同一边

情形4.1.1 父N同左

“父N同左”指的是：父节点为祖父节点的左子，N为父节点的左子。此时以祖父节点(GP)为支点进行右旋；然后将P涂黑，将GP涂红。

旋转后，P涂黑是因为要涂为原GP的黑色（往上兼容GP的父节点）；而GP涂红则是因为右旋后，经过U的路径的黑色节点数量+1，涂红进行数量平衡；下同。

情形4.1.2 父N同右

“父N同右”指的是：父节点是祖父节点的右子，N为父节点的右子。此时以祖父节点(GP)为支点进行左旋；将P涂黑，将GP涂红。

情形4.2 父节点和N不在同一边

情形4.2.1 父左N右

“父左N右”指的是：父节点是祖父节点的左子，N为父节点的右子。此时，以父节点(P)进行左旋，旋转后，以P作为新的平衡节点N，转至 [情形4.1.1 父N同左] 处理。

情形4.2.2 父右N左

“父右N左”指的是：父节点是祖父节点的右子，N为父节点的左子。此时，以父节点(P)进行右旋，旋转后，以P作为新的平衡节点，此时再进行【情形4.1.2 父N同右】处理。

插入总结与实例

首先是将节点先插入再说，插入后，以刚插入的节点作为当前平衡节点N，进行平衡操作。现在回头看插入平衡的这几种情形，其实并不复杂：

N为根：涂黑完事；
父黑：啥事不用管；
父红叔红：父/叔涂黑，祖父涂红，然后把祖父当成新的平衡节点递归处理（我们下面平衡了，让他老人家和上面沟通吧）；
父红叔黑：父节点和新插入节点同一边的话，扭一下就完事了（同左右旋，同右左旋，顺便涂色）；不在同一边的话，先扭到同一边吧。

实例说明：为了简化，图中没有画出null的黑色节点。插入 10、20、15、30、5、8：

红黑树删除动作

红黑树和二叉搜索树的删除类似，只不过加上颜色属性（这里的子节点均指非NULL节点）：

无子节点时，删除节点可能为红色或者黑色：
1. 如果为红色，直接删除即可，不会影响黑色节点的数量；
2. 如果为黑色，则需要进行删除平衡的操作了。
只有一个子节点时，删除节点只能是黑色，其子节点为红色，无法满足红黑树的性质了。此时用删除节点的子节点接到父节点，且将子节点颜色涂黑，保证黑色数量。
有两个子节点时，与二叉搜索树一样，使用后继节点作为替换的删除节点，情形转至为1或2处理。

我们发现，删除情形3总是会转换为情形1和2，而情形1.1和情形2处理平衡非常简单，本文主要讨论的是情形1.2：删除黑色的叶子节点。因为一旦该节点被拿掉，红黑树中通过该节点的路径黑色节点数量将会减1，而且无法像情形2那样将子节点涂黑来达到平衡。此时只能自底向上进行平衡操作。

这里的图特意将黑色的NULL节点给加上，这是因为删除节点被摘掉后，我们可以用一个黑色的节点接上，从而进行统一处理。

删除后的平衡

我们先约定一下节点名称：

h(A->B->叶子)表示从A走到B再走到某一个叶子路径的黑色节点数量（A与B，B与叶子之间可能间隔了多个节点）。

本文余下内容均指的是删除黑色的叶子节点后引发的一系列平衡操作。比如P->D->N，删除D（黑色）后，N接至父节点：P->N。

因为删除了一个黑色节点（N的父节点D），经过N的路径的黑色数量减1，即h(P->N->叶子) 比 h(P->S->叶子) 少1。平衡的方式有：

h(P->N->叶子)不变，h(P->S->叶子)减1，此时已经子平衡，然而h(GP->P->叶子)还是会比h(GP -> U ->叶子)少1，此时需要将P当作新的N，向上递归处理；
h(P->N->叶子)加1，h(P->S->叶子)不变，也就是恢复了原来的状态，此时已经平衡，因为h(GP->P->叶子)=h(GP -> U ->叶子)。

本文下面平衡的思路主要就是基于以上两种方式，另外要注意的是，红色和红色不能连一起的约束也不能违反。理解这个比较重要。

GP->P->叶子的路径，要么经过N，要么经过S，如果h(P->N->叶子)和h(P->S->叶子)均少1了，自然h(GP->P->叶子)会少1。

删除平衡情形，主要根据 [兄节点的位置/颜色]、[兄的子节点的颜色]、[父节点颜色] 进行分类：

N节点的位置知道后，S的位置自然也就知道了，相反亦可；这里以S位置作为分类，主要是为了便于理解和记忆。

情形1 当前节点为根节点（父节点为NULL）

比较特殊的情况，无需平衡操作。因为经过根节点的黑色数量少一个，意味着所有路径都少一个，已然平衡。

情形2 兄弟节点为黑色（S=黑）

情形2.1 兄弟的子节点全黑

兄弟节点的子节点全为黑色（SL/SR=黑），也就意味着兄弟节点（S）可以涂红而不会和子冲突。S涂红后，也就实现了子平衡，这时候我们看父节点是红是黑，再做处理。

情形2.1.1 父节点为黑色（P=黑）

此时将S涂红，父节点作为新的平衡节点N，递归上去处理。这个也就是之前提到的h(P->N->叶子)不变，h(P->S->叶子)减1，而h(GP->P->叶子)，依然会比h(GP -> U ->叶子)少1，所以要递归上去处理。

情形2.1.2 父节点为红色（P=红）

此时将S涂红，P涂黑，平衡结束。S涂红后，h(P->N->叶子)不变，h(P->S->叶子)-1，实现子平衡，因为P节点是红色的，如果将它涂黑，h(P->N->叶子)和h(P->S->叶子)均会+1，就可以恢复原来的状态了，而不用递归上去。

情形2.2 兄弟的子节点不全黑

所谓的不全黑包括：[SL红, SR红]、[SL黑，SR红]、[SL红，SR黑]。如果其中一个为黑，另外一个肯定是红。以全黑/非全黑作为分类，是因为全黑时无论N是在左子还是右子，其处理方式是一样的。而非全黑则要看N所处的位置（或者说S所处的位置）进行特定方向的旋转。

为了方便理解和记忆，以S进行分组：

S为左子时（即N为右子），主要分两组 [SL=红]、[SL=黑]；
S为右子时（即N为左子），主要分两组 [SR=红]、[SR=黑]。
【S为左子，SL红】与【S为右子，SR红】处理方式对称；【S为左子，SL黑】与【S为右子，SR黑】处理方式对称。
【S为左子，SL黑】与【S为右子，SR黑】处理方式对称。

情形2.2.1 S为左子，SL红；S为右子，SR红

情形(1) S为黑色，S为左子，SL红时：以P为支点右旋，交换P和S颜色，SL涂黑；平衡结束。

这里的平衡思路其实就是：h(P->S->叶子)不变（因为SL涂黑补回来了），h(P->N->叶子)+1（因为多了个黑色P）。

通常旋转后，新的P节点往往都会涂成原P的颜色：一是为了让GP-P不会颜色冲突；二是保持经过P的路径黑色数量不变。

对称的情形(2)：S为黑色，S为右子，SR红时：以P为支点左旋；交换P和S颜色（S涂为P原颜色，P涂黑），SR涂黑；平衡结束。

情形2.2.2 S为左子，SL黑；S为右子，SR黑

情形(1) S为黑色，S为左子，SL黑：以S为支点左旋，交换S和SR颜色（SR涂黑，S涂红），此时转至情形2.2.1-(1) S左-SL红进行处理。

S涂红是为了使h(原S->SR->叶子)不变。

对称的情形(2) S为黑色，S为右子，SR黑：以S为支点右旋，交换S和SL颜色（SL涂黑，S涂红），此时转至2.2.1-(1) S右-SR红进行处理。

情形3 兄弟节点为红色（S=红）

情形(1) S为左子时，以P进行右旋；
情形(2) S为右子时，以P进行左旋。
旋转后交换P和S的颜色（S涂黑，P涂红），N兄弟节点变为黑色，进入情形2-兄弟节点为黑色进行处理。

删除总结与实例

删除动作（移除节点）之后，看看这个节点是不是黑色的叶子节点，如果不是，简单处理就可以达到平衡了；
先看N是不是根节点，是的话啥都不用管；不是的话看兄弟什么颜色：
1. 兄弟是红色：进行旋转涂色，去到兄弟为黑色那里处理；
2. 兄弟是黑色，看看兄弟子节点是不是全部都是黑。
  - 全黑的话，看父什么颜色进行对应处理；
  - 不全黑，看兄在的位置，兄在左的话，看兄的左子是不是红色，进行对应处理；兄在右的话，看兄的右子是不是红色，进行对应处理。

现在我们有一颗红黑树：