Data Structures Algorithms 简明教程
Red Black Trees
Red-Black 树是另一种类型的平衡二叉查找树，带有两种颜色的节点：红色和黑色。这是一棵自平衡二叉查找树，它利用这些颜色来在插入和删除操作期间维持平衡因子。因此，在 Red-Black 树操作期间，内存会使用 1 位存储来容纳每个节点的颜色信息。
在 Red-Black 树（也称为 RB 树）中，在为节点分配颜色时有一些不同的条件需要遵循。
-
根节点始终为黑色。
-
任意的两个相邻节点都不得为红色。
-
树中的每条路径（从根节点到叶节点）都必须包含相同数量的黑色节点。
尽管 AVL 树比 RB 树更平衡（AVL 树中的平衡算法比 RB 树中的严格），但通过 RB 树可以更有效地进行多次且快速的插入和删除操作。
Fig: RB trees
Basic Operations of Red-Black Trees
对 Red-Black 树的操作包括通常在二叉查找树上执行的所有基本操作。RB 树的一些基本操作包括：
-
Insertion
-
Deletion
-
Search
Insertion operation
Red-Black 树的插入操作遵循二叉查找树的相同插入算法。该元素按照二叉查找属性插入，另外，对节点进行红黑颜色编码以根据红黑树属性对树进行平衡。
按照以下给定的程序将元素插入红黑树，同时维护二叉查找树和红黑树属性。
Case 1 - 检查树是否为空；如果树为空，则将当前节点作为根，并将该节点着色为黑色。
Case 2 - 但如果树不为空，则创建一个新节点并将其着色为红色。此处我们面临两种不同的情况：
-
如果新节点的父级为黑色节点，则退出操作，树保持原样。
-
如果此新节点的父节点为红色，且父节点兄弟节点的颜色为黑色或不存在，我们应用合适的旋转并相应地重新着色。
-
如果此新节点的父节点为红色，且父节点兄弟节点的颜色为红色，则将父节点、兄弟节点和祖先节点重新着色为黑色。祖先节点仅当它是 not 根节点时重新着色；如果是根节点，则仅重新着色父节点和兄弟节点。
Example
让我们构造一棵 RB 树以详细了解插入操作的前 7 个整数：
检查树是否为空，因此添加的第一个节点是根，并将其着色为黑色。
现在，树不为空，因此我们创建一个新节点，并用红色添加下一个整数，
节点不违反二叉查找树和 RB 树属性，因此我们继续添加另一个节点。
树不为空；我们用下一个整数创建一个新的红色节点。但新节点的父节点不是黑色节点，
现在树违反了二叉搜索树和 RB 树的属性；因为父节点的兄弟节点是 NULL，我们应用了合适的旋转并重新给节点着色。
现在 RB 树属性已恢复，我们向树中添加另一个节点 −
树再次违背 RB 树的平衡属性，因此我们检查父节点的兄弟节点颜色，在本例中为红色，因此我们只需重新给父节点和兄弟节点着色。
接下来，我们插入元素 5，这使树再次违反 RB 树的平衡属性。
并且由于兄弟节点是 NULL，我们应用了合适的旋转并重新给颜色。
现在，我们插入元素 6，但 RB 树属性被违反，需要应用插入案例之一 −
父节点的兄弟节点是红色的，因此我们重新给父节点、父节点的兄弟节点和祖父节点着色，因为祖父节点不是根节点。
现在，我们添加最后一个元素 7，但这个新节点的父节点是红色的。
因为父节点的兄弟节点是 NULL，我们应用合适的旋转（RR 旋转）
最终的 RB 树已完成。
Deletion operation
红黑树上的删除操作必须以一种方式执行，这种方式必须恢复二叉搜索树和红黑树的所有属性。按照以下步骤在红黑树上执行删除操作 −
首先，我们基于二叉搜索树属性执行删除。
Case 1 - 如果要删除的节点或节点的父节点为红色，则直接删除它。
Case 2 - 如果节点是双黑色，则只需删除双黑色（双黑色发生在待删除节点为黑色叶节点时，因为它添加了也被视为黑色节点的 NULL 节点）
Case 3 - 如果双黑节点的兄弟节点也是黑色节点并且其子节点也是黑色，请按照以下步骤操作 −
-
Remove double black
-
将其父节点重新着色为黑色（如果父节点为红色节点，它将变为黑色；如果父节点已经是黑色节点，它将变成双黑色）
-
将父节点的兄弟节点重新着色为红色
-
如果双黑节点仍然存在，我们应用其他情况。
Case 4 − 如果双黑节点的兄弟节点为红色，则执行以下操作 −
-
交换父节点和父节点兄弟节点的颜色。
-
向双黑色方向旋转父节点
-
重新应用合适的情况。
Case 5 − 如果双黑节点的兄弟节点是黑节点，但兄弟节点的一个最近的子节点为红色，则按照以下步骤进行 −
-
交换双黑色兄弟节点和相应兄弟节点子节点的颜色
-
旋转兄弟节点和双黑节点在相反的方向（也就是说，如果双黑节点是右子节点，则进行左旋转，反之亦然）
-
Apply case 6.
Case 6 − 如果双黑节点的兄弟节点是黑节点，但兄弟节点的一个更远的子节点为红色，则按照以下步骤进行 −
-
交换双黑色的父节点和兄弟节点颜色
-
向双黑色方向旋转父节点（即，如果双黑色是右侧子节点，则应用右侧旋转，反之亦然）
-
Remove double black
-
将红色子节点的颜色更改为黑色。
Example
考虑以上构建的红黑树，让我们从树中删除一些元素。
从树中删除元素 4、5、3。
要删除元素 4，让我们首先执行二元查找删除。
执行二元查找删除后，红黑树属性不受干扰，因此树保持原样。
然后，我们使用二元查找删除来删除元素 5
但是在执行二元查找删除后，红黑属性被破坏，即树中的所有路径未保存相同数量的黑节点；因此，我们交换颜色来平衡树。
然后，我们从获得的树中删除节点 3 −
应用二进制查找删除，我们正常删除节点 3，因为它是一个叶节点。由于 3 是一个黑色节点，我们得到了一个双重节点。
我们应用情况 3 删除，因为双重黑色的兄弟节点是黑色，其子节点也是黑色。在这里，我们删除双重黑色，为双重黑色的父级和兄弟节点重新着色。
所有所需的节点都被删除，并且 RB 树属性得到了保持。