After studying two or three trees, you know how to understand red black trees, but if you look directly at the properties of red black trees in “Introduction to Algorithms”, you can’t see why. Let’s also look at a binary search tree that satisfies the red-black property:
1. Each node is either red or black;
2. The root node is black.
3. Each leaf node (NIL) is black;
4. If a node is red, both of its children are black;
5. For each node, a simple path from that node to all of its descendant leaf nodes contains the same number of black nodes.
If the first four are understandable, what about the fifth property? In this case, we’re going to use two or three trees to understand basic red-black trees, and of course I’m going to introduce two-three-four trees and red-black trees based on two-three-four trees in the next few articles.
Regardless of the above binary search tree meets the red-black nature, we know that 2-3 trees are not binary trees, we convert it into a binary tree, 2-node is very good, 3-node to binary, but there are two kinds, as shown below:
Red-black refers to the color of the link to the node being pointed to. For a 2-3 tree, since there are many different representations of the 3-node, we only consider the left-leaning case.
Left-leaning red-black tree is equivalent to 2-3 tree
A red-black tree is defined as a binary search tree that contains red-black links and satisfies the following criteria:
1. Red links are left links;
2. No node is connected to two red links;
3. The tree is perfectly black balanced, that is, there are the same number of black links on the path from any empty link to the root node (equivalent to a 2-3 tree, any node is the same height from its leaf node).
Since there is no permanent 4-node in 2-3 trees, 4-nodes will eventually be decomposed (in 2-3-4 trees, 4-nodes only exist in leaf nodes, non-leaf nodes are the same as 2-3 trees for better insertion and deletion), so no node in 2-3 trees can be connected to two red links at the same time. For the third clause, the 2-3 tree itself is absolutely balanced. Turning the 3-node into a binary only increases the left-red link, while the other black links remain black and balanced.
Look for the element
A lookup hit is the same as a binary search tree, starting at the root node, and returning if the lookup is hit. Otherwise, a left recursive search is performed for those smaller than it, and a right recursive search is performed for those larger than it until the lookup is empty.
Before we write about insert elements and delete elements, let’s talk about rotation and color conversion.
rotating
There may be a tilt to the right or two consecutive red links during an insert or delete operation, both of which should be adjusted to the left during an upward transformation.
Suppose there is a red right link that needs to be converted to the left, as shown below:
This operation is called left rotation, and the right link becomes the left link, meaning that the node pointed to by the red link turns red, and the root node defaults to black.
The same is true for a right rotation, but in a left-leaning red-black tree, a right rotation occurs only if there are two consecutive red left links, as shown below:
Code: Left rotation and right rotation
Color conversion
Color transitions are used on temporary 4-nodes, either down or up.
Code: color conversion
Insert elements
If the search is not hit, an element is inserted into this node (NIL), that is, a red node is inserted under the red-black tree. By default, the inserted element is a red node.
If the red-black tree is currently an empty tree, you can store an element directly as a node, which then turns black. If it is not an empty tree, there are two ways to insert elements: to the 2-node and to the 3-node.
There are two cases of inserting a new element into a 2-node
Inserting a new element into the 2-node is easy. If the new element is smaller than the parent node, just insert the red node. If the new element is larger than the element of the parent node, a red right link is generated. After insertion, the upward transformation is carried out. In the upward transformation process (repairing the properties of red-black tree), the right link needs to be rotated left to change the right link to the left, which satisfies the properties of left-leaning red-black tree.
There are three cases of inserting new elements into the 3-node
1. The new element is less than 3- the node minimum
2. The new element is between the minimum and maximum value of the 3-node
3. New element is greater than 3- node maximum value
The insertion only goes up, in order to satisfy the red-black properties.
Animation: Insert node
Algorithm animation address: STATION B
Code: Insert elements
Remove elements
There are both downward and upward transformations for deleting elements: downward transformations allow a node under the tree to be deleted that is pointed to by a red link without affecting the black balance; The upscaling is to fix left-leaning red black trees based on 2-3 trees.
Code: Transform up (fix adjustments)
There are four principles for deleting elements:
1. The current node of the deleted element cannot be a 2-node.
2. The downward transformation is not 2-node;
3. Delete the node from the bottom of the tree.
4. Shift up to eliminate right-leaning and 4-node.
Deleting elements refers to the idea of deleting elements in binary search tree, which can be divided into three cases: deleting the smallest element, deleting the largest element and deleting any element. Deleting the smallest element recurses to its left child until the left child is empty. Removing the largest element is the opposite; If any element is to be deleted, a matching search is required. If the element is found, the minimum value of the right subtree is used to replace the element to be deleted, and then the minimum element of the right subtree is deleted.
Red-black tree deletes elements in the same way, but more down and up transformation process. Since it’s a left-leaning red-black tree, removing the smallest element is the most appropriate.
Delete the smallest element
The red-black tree in “Algorithm 4” introduces the section on deleting the minimum key. Although it does not go into detail, it gives three cases of transformation down the left link:
1. If the left child of the current node (parent node) is not a 2-node, complete.
2. If the left child of the current node (parent node) is a 2-node and the left child’s sibling is not a 2-node, the left child borrows a key from its sibling.
3. If the left child of the current node (parent node location) and the brothers of the left child node are 2-nodes, combine the left child, the current node, and the brothers of the left child node into a temporary 4-node, so that the current node becomes 2-node or 4-node becomes 3-node.
Code: moveRedLeft
The idea of removing the largest node is the same, but this is a left-leaning red-black tree, so it is not very helpful to remove the largest node, even if the left is adjusted to the right when switching down, and the right is adjusted to the left when switching up balance.
Animation: Remove the smallest element
Algorithm animation address: STATION B
Code: Removes the smallest element
Delete any element
After learning how to delete the smallest node, it is easy to delete any node. If we want to delete a node, we first conduct a matching search and replace the element to be deleted with the minimum value of the right subtree. The color of the link pointing to the node to be deleted cannot be changed. Then delete the smallest element of the right subtree.
During a hit lookup, you need to translate down either the left link or the right link. The previous deletion of the smallest element is translated down the left link.
Conversions down the right link also fall into three categories:
1. If the right child of the current node (parent node) is not a 2-node, change the left-leaning to right-leaning;
2. If the right child of the current node (parent node) is a 2-node and the right child’s sibling is not a 2-node, then the right child borrows a key from its sibling.
3. If the siblings of the right child and right child of the current node (parent node location) are 2-nodes, combine the siblings of the right child, current node, and right child into a temporary 4-node, so that the current node becomes 2-node or 4-node becomes 3-node.
Code: moveRedRight
Code: Delete any element
Animation: Remove any element
Algorithm animation address: STATION B
See redBlacktree.java in algorithm 4
Click on the source
If you like this article, please pay attention to the public account “Algorithmic Strategy” and watch more exciting content
