5分钟了解二叉树之红黑树

转载请注明出处：https://i.cnblogs.com/posts/edit;postId=16032891

书接上一回。上一篇已经讲解到了AVL树，这一篇会接着讲另一个重量级的数据结构：红黑树。

红黑树

红黑树是一种自平衡二叉搜索树。每个节点存储一个表示“颜色”（“红色”或“黑色”）的额外位，用于确保树在插入和删除期间保持平衡。

从历史上看，红黑树并不是从AVL树推导出来的，而是跟以后会说的B树有关，所以从AVL树看到红黑树可能会有点懵。但是红黑树是AVL树很流行的一个替代数据结构，而且可以通过更小的代价实现与AVL树相近的查找性能。

红黑树是具有下列着色性质的二叉查找树：

1. 每一个节点或着色成红色，或者着色成黑色。
2. 根是黑色的（维基百科里的条件2是：所有 null 节点都被视为黑色。根是不是黑色影响不大）。
3. 如果一个节点是红色的，那么他的子节点必须是黑色的。
4. 从一个节点到一个null指针的每条路径必须包含相同数目的黑色节点。

继续讲解红黑树之前，先了解下红黑树的应用场景

广泛的应用

• Linux内核和epoll系统调用实现中使用的完全公平调度器
• Linux内核虚拟内存管理
• C++标准库里的map、multimap、multiset
• Java 中的 java.util.TreeMap， java.util.TreeSet
• Java 8 开始用于存储HashMap具有冲突hash码的不同元素
• 网卡数据

也就是说，对于程序员而言，其实已经无时无刻都要跟红黑树打交道了，红黑树对我们的重要性不言而喻，红黑树也是众多数据结构中面试最常见的数据结构之一。

基本操作

前面已经说明了红黑树的定义，从这个定义得到的红黑树高最多是2log(N+1)，所以查找操作的时间复杂度可以保证是对数的。困难的点在于如何插入一个新数据。通常把新数据作为叶子节点放到树中，如果该数据涂成黑色，则违反了条件4，因为会建立一条更长的黑节点的路径。因此新数据必须涂成红色。如果他的父节点是黑色的，那么不需要进一步处理；如果父节点已经是红色的，那么违反了条件3，需要调整树确保条件3满足而且条件4不被破坏。完成这样的调整的基本操作是颜色的改变和树的旋转。其中违反条件3称为红色违规（red-violation），违反条件4称为黑色违规（black-violation）。

插入

自底向上的插入

上面提到，如果新插入的数据父节点是红色的，那么插入就完成了。

如果父节点是红色的，那么有几种情形（每种都有一个镜像对称）需要考虑。

1.假设父节点兄弟是黑色的（或者null，因为null也是黑色的）。见下图。X是新添加的叶子节点（扩展到一般情况，X有可能是中间某个节点），P是他的父节点，S是父节点的兄弟节点（叔叔节点），G是祖父节点。G肯定是黑色的，因为P是红色的，相邻父子节点不可能同为红色。我们要做的是想办法把左边多出来的一个红色节点塞到右边的连续黑节点中间。可以通过上面AVL树提到的单旋转和双旋转完成。

图中上部分对应P和G之间的单旋转，下部分对应双旋转。因为子树新根是黑色的，所以即使原来的曾祖父是红色的，也可以满足条件3，并且旋转后通向ABC各子树路径上的黑节点数没有改变，也不会违反条件4。

2.如果父节点的兄弟节点是红色的怎么办？

如果父节点的兄弟节点是红色，父节点和其兄弟节点P和S可以直接涂成黑色，祖父节点G相应地涂成红色来保证条件4。因为任何通过父母或叔叔的路径都必须通过祖父母，因此这些路径上的黑色节点的数量没有改变。但是，如果祖父母G如果有一个红色父母，它现在会违反条件3。把祖父节点G当做是新插入节点X，可以在更高的一个级别（= 2 个树级别）上迭代重新调整，一直到达根为止。这个过程称之为上滤（percolate）。

总结一下，插入操作可以有以下几种场景：

1. 当前节点的父节点P是黑色，插入完成
2. 如果父节点P和叔叔节点U都是红色的，那么他们都可以涂成黑色，而祖父节点G变成红色。如果祖父节点G有一个红色父节点，N=G，在更高的一个黑色级别（2 层）上迭代重新平衡；直到N是根节点时，结束迭代。
3. 父节点P是红色和根，切换P的颜色为黑色，树的黑色高度增加 1。
4. 父节点P是红色的，但叔叔U是黑色的，如果N是G的外部孙子节点（P是G左儿子且N是P左儿子，反之亦然），通过单旋转处理；如果N是H的内部孙子节点（P是G左儿子且N是P右儿子，反之亦然），通过双旋转处理。

自顶向下红黑树

上面提到如果新插入节点的父亲节点和叔叔节点都是红色时，需要进行上滤操作。上滤的实现需要用一个栈或用一些父链保存路径。可以通过自顶向下的方法更有效地解决。从树的根节点向下，如果发现有节点X的两个儿子是红色的，则改变自己和两个儿子的颜色，如下图所示

如果X是根节点，则违反了条件2，需要将X改为黑色（也可以不管）。

如果X的父节点是红色的，这会破坏条件3。因为我们是自顶向下的处理方式，X的父节点和叔叔节点不可能同时是红色，所以可以使用上面说的旋转来解决。

删除

删除跟二叉树的删除操作类似，假设N是待删除的节点。

简单情形

1. 如果N是没有子节点的根，则将其替换为 null。

2. 如果N有两个子节点，则找到其右子树最小节点（后继节点）作为替换节点。假设R是这个替换节点，作为子树的最大或最小元素，至多有一个子节点。交换N和R所有与红黑树相关的数据，包括两个节点的颜色和指向和来自两个节点的指针。（修改后的红黑树与之前相同，只是N和R顺序相反，这个问题可以通过删除N立即解决。）现在N最多有一个子节点。

3. 如果N恰好有一个子节点，它一定是红色孩子，因为如果它是黑色孩子，只有一个子节点的N会破坏条件4。

4. 如果N是红色节点，则它不能有子节点，因为根据条件3这必须是黑色的。此外，正如上面所讨论的，它不可能只有一个黑色子节点。因此，红色节点N没有任何子节点，可以简单地删除。

5. 如果N是一个黑色节点，它可能有一个红色的子节点或根本没有子节点。如果N有一个红色的子节点，则在将后者涂成黑色后，将其简单地替换为该子节点。

删除黑色非root叶子节点

6. 如果N不是根节点，颜色是黑色的并且没有子节点。在第一次迭代中，N被替换成null。假设P表示N的父节点，S表示N的兄弟节点，C（表示近侄）表示S与N方向相同的子节点，D（表示远侄）表示S的另一个子节点 ( S在第一次迭代中不能是 null，因为它必须有黑色高度1，这是N在删除之前的黑色高度，但C和D可能是null)。

6.1. 案例 1 : P、S 和S的孩子都是黑色。在将S涂成红色之后，所有通过S的路径，也就是那些不通过N的路径，都少了一个黑色节点。现在以P为根的子树中的所有路径都有相同数量的黑色节点，但比不通过P的路径少一个，因此仍然会违反条件4,。将P标记为N，在更高的黑色级别（= 1 树级别）上迭代重新平衡，直到当前节点N是新的根，结束迭代，树的黑色高度减 1。

 6.2. 案例 2 : 兄弟姐妹S是红色的，所以P和侄子C和D必须是黑色的。在P处的单旋转将S变成N的祖父母。然后在翻转P和S的颜色后，通过N的路径仍然短一个黑色节点。但是N现在有了一个红色的父节点P和一个黑色的兄弟S。

6.3. 案例 3 : 兄弟节点S和S的孩子是黑色的，但P是红色的。交换S和P的颜色，交换后经过S的路径上的黑色节点的数量不变，经过N的路径上的黑色节点的数量上加一，从而弥补这些路径上已删除的黑色节点。

6.4. 案例 4 :  兄弟节点S是黑色的，S的亲近孩子C是红色，S的远亲孩子D是黑色。在S的一个单旋转之后，侄子C成为S的父母和N的新兄弟。交换S和C的颜色。所有路径仍然有相同数量的黑色节点，但现在N有了一个黑色兄弟，其远方的孩子是红色的。N及其父P都不受这种转换的影响，并且P可能是红色或黑色。

6.5. 案例 5 : 兄弟姐妹S是黑色的，S的远亲孩子D是红色的。在P处单旋转后，兄弟S成为P和S的远亲孩子D的父母。P和S的颜色互换，D变成黑色。子树在其根部变换前后的颜色相同。变换后符合条件3。子树中的路径不经过N（在图中通过D和节点3）通过与以前相同数量的黑色节点，但N现在有一个额外的黑色祖先：要么P变成黑色，要么它是黑色的并且S被添加为黑色祖父母. 这样，经过N的路径又加上了一个额外的黑色节点，因此条件4被恢复。

引用：

《数据结构与算法分析——C++语言描述（第四版）》

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

https://www.bilibili.com/video/BV1hp4y1B7Uf/

https://developpaper.com/understand-the-origin-of-red-black-tree-and-understand-the-essence-of-red-black-tree/