红黑树的用途、红黑树的插入删除操作 红黑树首先是一棵二叉查找树（BST），BST 满足的性质如下： 左子树上所有节点的值均小于或等于它的根节点的值； 右子树上所有节点的值均大于或等于它的根节点的值； 左右子树䦹 BST。 考虑向一棵 BST 中多次插入新节点的情况，如果插入的总是最大（小）值，会导致 BST 严重不平衡。为了解决这个问题，引入了自平衡的二叉查找树——红黑树（BR-Tree）。红黑树的附加特性： 节点为黑色或红色； 根节点为黑色； 每个叶子节点都是黑色的空节点（NIL）； 每个红色节点的两个孩子节点都是黑色（保证从每个叶子到根的所有路径上不能有两个连续的红色节点）； 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（保证了红黑树从根到叶子的最长路径不会超过最短路径的两倍）。 红黑树的用途 1）广泛应用在 C++ 的 STL 中，如 map 和 set 都是用红黑树实现的。 2）linux 进程调度，用红黑树管理进程控制块 3）epoll 在内核中的实现，用红黑树管理事件块 4）nginx 中，用红黑树管理 timer 等 红黑树的插入 插入的新节点 N 初始化为红色。 case 0.0： N 为根节点，直接变为黑色。over。 case 0.1： N 的父节点为黑色，无需调整。over。
case 0.0 与 case 0.1 示意图 case 1： N 的父节点为红色，无叔叔节点（父节点的兄弟节点）或叔叔节点为黑色，且 N 为右子。以父节点为新红色节点 N，并以 N 为支点进行左旋。继续判定旋转后的节点 N 是否满足性质。
case 1 示意图 – 1 
case 1 示意图 – 2 case 2： N 的父节点为红色，无叔叔节点（父节点的兄弟节点）或叔叔节点为黑色，且 N 为左子。将 N 的父节点变为黑色，祖父节点变为红色，以祖父节点为支点进行右旋。
case 2 示意图 
case 1 与 case 2 示意图 case 3： N 的父节点为红色，叔叔节点（父节点的兄弟节点）也为红色，将父节点与叔叔节点都变为黑色，祖父节点变为红色。若祖父节点仍不满足性质，则将祖父节点当做新红色节点递归调整。最后强制根节点为黑色。
case 3 示意图 红黑树的删除 case 1： 如果需要删除的节点有两个孩子，我们的做法是找到这个节点的中序后继，将后继节点中的数据拷贝至待删除结点，然后删除后继节点。而后继节点必然最多只有一个子节点，这样我们就把删除两个孩子的节点转为删除一个孩子的节点（case 2）。 case 2： 删除只有一个孩子的节点，如果它两个孩子都为空，即均为叶子，我们任意将其中一个看作它的孩子。（这里体现出来，在红黑树里特别指定叶子结点为 NIL 节点的作用，NIL 节点经常可以充当正常节点使用以使得算法的表达更加容易。） case 2.1： 若被删除节点是红色，它的父亲和孩子一定是黑色的。所以我们可以简单地用它的黑色孩子替换它。 case 2.2： 若被删除节点是黑色而它的孩子是红色。用它的红色孩子顶替上来并重绘为黑色。 case 2.3 若待删除节点和它的子节点都是黑色，情况比较多，由简单到复杂分为六小类。 先来约定涉及到的节点的名称。我们先用待删除节点的孩子代替待删除节点，并且记这个孩子为 N，记它的新的父节点为 P，它的兄弟节点为 S， S的左孩子为 SL，右孩子为 SR。 case 2.3.1： 若 N 是新的根。无需改动，所有属性都保持着。over。 case 2.3.2： P 为红色，S 和 S 的两个孩子都是黑色的。将 P 置为黑色，S 置为红色。这样，不经过 N 的路径上的黑色结点数目并没有发生变化，而经过 N 结点的路径上黑色结点的数目增加了 1，刚好添补了这条路径上删除的黑色结点。所以红黑树又重新达到了平衡。 
case 2.3.2 示意图 case 2.3.3： S 是黑色，S 的右孩子是红色，而 N 是它父亲的左儿子。以 P 为支点左旋，这样 S 成为 P 和 R 的父亲。接着交换 N 的父亲和 S 的颜色，并使 S 的右儿子为黑色。 
case 2.3.3 示意图（白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色） case 2.3.4： S 是黑色，S 的左孩子是红色，S 的右儿子是黑色，而 N 是它父亲的左儿子。在这种情况下我们在 S 上做右旋，这样 S 的左儿子成为 N 的新兄弟。我们接着交换 S 和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在N有了一个右儿子是红色的黑色兄弟，所以我们进入了 case 2.3.3。N 和它的父亲都不受这个变换的影响。 
case 2.3.4 示意图 case 2.3.5： S 是红色。在这种情况下我们在 P 上做左旋，把红色兄弟转换成 N 的祖父。我们接着对调 N 的父亲和祖父的颜色。尽管所有的路径仍然有相同数目的黑色节点，现在 N 有了一个黑色的兄弟和一个红色的父亲，所以我们可以接下去按 case 2.3.2、case 2.3.3、case 2.3.3 来处理。 
case 2.3.5 示意图 case 2.3.6： P、S 和 S 的儿子都是黑色的。在这种情况下，我们简单的重绘 S 为红色。结果是通过 S 的所有路径，都少了一个黑色节点。 因为删除 N 的初始的父亲使通过 N 的所有路径少了一个黑色节点，这使事情都平衡了起来。 但是，通过 P 的所有路径现在比不通过 P 的路径少了一个黑色节点。要修正这个问题，我们要转到 case 2.3.1，把 P 当做新的 N 重新平衡处理。 
case 2.3.6
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/56869.html
