Data Structures Algorithms 简明教程
Red Black Trees
Red-Black 树是另一种类型的平衡二叉查找树，带有两种颜色的节点：红色和黑色。这是一棵自平衡二叉查找树，它利用这些颜色来在插入和删除操作期间维持平衡因子。因此，在 Red-Black 树操作期间，内存会使用 1 位存储来容纳每个节点的颜色信息。
Red-Black Trees are another type of the Balanced Binary Search Trees with two coloured nodes: Red and Black. It is a self-balancing binary search tree that makes use of these colours to maintain the balance factor during the insertion and deletion operations. Hence, during the Red-Black Tree operations, the memory uses 1 bit of storage to accommodate the colour information of each node
在 Red-Black 树（也称为 RB 树）中，在为节点分配颜色时有一些不同的条件需要遵循。
In Red-Black trees, also known as RB trees, there are different conditions to follow while assigning the colours to the nodes.
-
The root node is always black in colour.
-
No two adjacent nodes must be red in colour.
-
Every path in the tree (from the root node to the leaf node) must have the same amount of black coloured nodes.
尽管 AVL 树比 RB 树更平衡（AVL 树中的平衡算法比 RB 树中的严格），但通过 RB 树可以更有效地进行多次且快速的插入和删除操作。
Even though AVL trees are more balanced than RB trees, with the balancing algorithm in AVL trees being stricter than that of RB trees, multiple and faster insertion and deletion operations are made more efficient through RB trees.
Fig: RB trees
Fig: RB trees
Basic Operations of Red-Black Trees
对 Red-Black 树的操作包括通常在二叉查找树上执行的所有基本操作。RB 树的一些基本操作包括：
The operations on Red-Black Trees include all the basic operations usually performed on a Binary Search Tree. Some of the basic operations of an RB Tree include −
-
Insertion
-
Deletion
-
Search
Insertion operation
Red-Black 树的插入操作遵循二叉查找树的相同插入算法。该元素按照二叉查找属性插入，另外，对节点进行红黑颜色编码以根据红黑树属性对树进行平衡。
Insertion operation of a Red-Black tree follows the same insertion algorithm of a binary search tree. The elements are inserted following the binary search property and as an addition, the nodes are color coded as red and black to balance the tree according to the red-black tree properties.
按照以下给定的程序将元素插入红黑树，同时维护二叉查找树和红黑树属性。
Follow the procedure given below to insert an element into a red-black tree by maintaining both binary search tree and red black tree properties.
Case 1 - 检查树是否为空；如果树为空，则将当前节点作为根，并将该节点着色为黑色。
Case 1 − Check whether the tree is empty; make the current node as the root and color the node black if it is empty.
Case 2 - 但如果树不为空，则创建一个新节点并将其着色为红色。此处我们面临两种不同的情况：
Case 2 − But if the tree is not empty, we create a new node and color it red. Here we face two different cases −
-
If the parent of the new node is a black colored node, we exit the operation and tree is left as it is.
-
If the parent of this new node is red and the color of the parent’s sibling is either black or if it does not exist, we apply a suitable rotation and recolor accordingly.
-
If the parent of this new node is red and color of the parent’s sibling is red, recolor the parent, the sibling and grandparent nodes to black. The grandparent is recolored only if it is not the root node; if it is the root node recolor only the parent and the sibling.
Example
让我们构造一棵 RB 树以详细了解插入操作的前 7 个整数：
Let us construct an RB Tree for the first 7 integer numbers to understand the insertion operation in detail −
检查树是否为空，因此添加的第一个节点是根，并将其着色为黑色。
The tree is checked to be empty so the first node added is a root and is colored black.
现在，树不为空，因此我们创建一个新节点，并用红色添加下一个整数，
Now, the tree is not empty so we create a new node and add the next integer with color red,
节点不违反二叉查找树和 RB 树属性，因此我们继续添加另一个节点。
The nodes do not violate the binary search tree and RB tree properties, hence we move ahead to add another node.
树不为空；我们用下一个整数创建一个新的红色节点。但新节点的父节点不是黑色节点，
The tree is not empty; we create a new red node with the next integer to it. But the parent of the new node is not a black colored node,
现在树违反了二叉搜索树和 RB 树的属性；因为父节点的兄弟节点是 NULL，我们应用了合适的旋转并重新给节点着色。
The tree right now violates both the binary search tree and RB tree properties; since parent’s sibling is NULL, we apply a suitable rotation and recolor the nodes.
现在 RB 树属性已恢复，我们向树中添加另一个节点 −
Now that the RB Tree property is restored, we add another node to the tree −
树再次违背 RB 树的平衡属性，因此我们检查父节点的兄弟节点颜色，在本例中为红色，因此我们只需重新给父节点和兄弟节点着色。
The tree once again violates the RB Tree balance property, so we check for the parent’s sibling node color, red in this case, so we just recolor the parent and the sibling.
接下来，我们插入元素 5，这使树再次违反 RB 树的平衡属性。
We next insert the element 5, which makes the tree violate the RB Tree balance property once again.
并且由于兄弟节点是 NULL，我们应用了合适的旋转并重新给颜色。
And since the sibling is NULL, we apply suitable rotation and recolor.
现在，我们插入元素 6，但 RB 树属性被违反，需要应用插入案例之一 −
Now, we insert element 6, but the RB Tree property is violated and one of the insertion cases need to be applied −
父节点的兄弟节点是红色的，因此我们重新给父节点、父节点的兄弟节点和祖父节点着色，因为祖父节点不是根节点。
The parent’s sibling is red, so we recolor the parent, parent’s sibling and the grandparent nodes since the grandparent is not the root node.
现在，我们添加最后一个元素 7，但这个新节点的父节点是红色的。
Now, we add the last element, 7, but the parent node of this new node is red.
因为父节点的兄弟节点是 NULL，我们应用合适的旋转（RR 旋转）
Since the parent’s sibling is NULL, we apply suitable rotations (RR rotation)
最终的 RB 树已完成。
The final RB Tree is achieved.
Deletion operation
红黑树上的删除操作必须以一种方式执行，这种方式必须恢复二叉搜索树和红黑树的所有属性。按照以下步骤在红黑树上执行删除操作 −
The deletion operation on red black tree must be performed in such a way that it must restore all the properties of a binary search tree and a red black tree. Follow the steps below to perform the deletion operation on the red black tree −
首先，我们基于二叉搜索树属性执行删除。
Firstly, we perform deletion based on the binary search tree properties.
Case 1 - 如果要删除的节点或节点的父节点为红色，则直接删除它。
Case 1 − If either the node to be deleted or the node’s parent is red, just delete it.
Case 2 - 如果节点是双黑色，则只需删除双黑色（双黑色发生在待删除节点为黑色叶节点时，因为它添加了也被视为黑色节点的 NULL 节点）
Case 2 − If the node is a double black, just remove the double black (double black occurs when the node to be deleted is a black colored leaf node, as it adds up the NULL nodes which are considered black colored nodes too)
Case 3 - 如果双黑节点的兄弟节点也是黑色节点并且其子节点也是黑色，请按照以下步骤操作 −
Case 3 − If the double black’s sibling node is also a black node and its child nodes are also black in color, follow the steps below −
-
Remove double black
-
Recolor its parent to black (if the parent is a red node, it becomes black; if the parent is already a black node, it becomes double black)
-
Recolor the parent’s sibling with red
-
If double black node still exists, we apply other cases.
Case 4 − 如果双黑节点的兄弟节点为红色，则执行以下操作 −
Case 4 − If the double black node’s sibling is red, we perform the following steps −
-
Swap the colors of the parent node and the parent’s sibling node.
-
Rotate parent node in the double black’s direction
-
Reapply other cases that are suitable.
Case 5 − 如果双黑节点的兄弟节点是黑节点，但兄弟节点的一个最近的子节点为红色，则按照以下步骤进行 −
Case 5 − If the double black’s sibling is a black node but the sibling’s child node that is closest to the double black is red, follows the steps below −
-
Swap the colors of double black’s sibling and the sibling’s child in question
-
Rotate the sibling node is the opposite direction of double black (i.e. if the double black is a right child apply left rotations and vice versa)
-
Apply case 6.
Case 6 − 如果双黑节点的兄弟节点是黑节点，但兄弟节点的一个更远的子节点为红色，则按照以下步骤进行 −
Case 6 − If the double black’s sibling is a black node but the sibling’s child node that is farther to the double black is red, follows the steps below −
-
Swap the colors of double black’s parent and sibling nodes
-
Rotate the parent in double black’s direction (i.e. if the double black is a right child apply right rotations and vice versa)
-
Remove double black
-
Change the color of red child node to black.
Example
考虑以上构建的红黑树，让我们从树中删除一些元素。
Considering the same constructed Red-Black Tree above, let us delete few elements from the tree.
从树中删除元素 4、5、3。
Delete elements 4, 5, 3 from the tree.
要删除元素 4，让我们首先执行二元查找删除。
To delete the element 4, let us perform the binary search deletion first.
执行二元查找删除后，红黑树属性不受干扰，因此树保持原样。
After performing the binary search deletion, the RB Tree property is not disturbed, therefore the tree is left as it is.
然后，我们使用二元查找删除来删除元素 5
Then, we delete the element 5 using the binary search deletion
但是在执行二元查找删除后，红黑属性被破坏，即树中的所有路径未保存相同数量的黑节点；因此，我们交换颜色来平衡树。
But the RB property is violated after performing the binary search deletion, i.e., all the paths in the tree do not hold same number of black nodes; so we swap the colors to balance the tree.
然后，我们从获得的树中删除节点 3 −
Then, we delete the node 3 from the tree obtained −
应用二进制查找删除，我们正常删除节点 3，因为它是一个叶节点。由于 3 是一个黑色节点，我们得到了一个双重节点。
Applying binary search deletion, we delete node 3 normally as it is a leaf node. And we get a double node as 3 is a black colored node.
我们应用情况 3 删除，因为双重黑色的兄弟节点是黑色，其子节点也是黑色。在这里，我们删除双重黑色，为双重黑色的父级和兄弟节点重新着色。
We apply case 3 deletion as double black’s sibling node is black and its child nodes are also black. Here, we remove the double black, recolor the double black’s parent and sibling.
所有所需的节点都被删除，并且 RB 树属性得到了保持。
All the desired nodes are deleted and the RB Tree property is maintained.
Search operation
红黑树中的搜索操作遵循与二叉查找树相同的算法。遍历树，并比较每个节点与要搜索的关键元素；如果找到，则返回成功的搜索。否则，返回不成功的搜索。
The search operation in red-black tree follows the same algorithm as that of a binary search tree. The tree is traversed and each node is compared with the key element to be searched; if found it returns a successful search. Otherwise, it returns an unsuccessful search.