Red-Black Tree: Insertion and Deletion
A Red-Black Tree is a type of balanced binary search tree that maintains five properties:
- Every node is either red or black.
- The root is black.
- Every leaf has two black sentinel children. If a node has only one child (left or right), the other child is a black sentinel.
- Every path from a node to its descendant leaves contains the same number of black nodes.
- No two adjacent nodes can be red. In other words, a red node cannot have a red parent or red children.
Red-Black Tree Insertion
Insertion follows these rules:
- The newly inserted node is initially colored red.
- Case 1: If the parent of the inserted node is black, no further action is needed.
- Case 2: If the parent of the inserted node is red and the uncle (parent's sibling) is also red, we recolor the parent, uncle, and grandparent. Then, we recursively check the grandparent node.
- Case 3: If the parent of the inserted node is red and the uncle is black, we perform a rotation and recoloring to balance the tree. This involves adding two sentinel nodes and rearranging the nodes in a specific order. Arrange the grandparent, parent, uncle, sibling, self, and two sentinel sons, a total of seven individuals(subtrees), in a sorted rotation to form a black-red-black three-level tree.
Explanation and Proof:
The Red-Black Tree maintains its balance by ensuring the five properties mentioned earlier. The subsequent operations aim to preserve these properties after inserting a new node.
Properties 1 and 2: These properties are fundamental requirements for a Red-Black Tree.
Property 3: This property allows regular node insertion and deletion operations to be transformed into subtree replacement operations.
Property 4: If only black nodes are present, the tree becomes a perfectly balanced tree.
Property 5: Since red nodes cannot be adjacent, the maximum length of a path is at most twice the length of the shortest path.
Any tree that satisfies both properties 4 and 5 can be considered "reasonably" balanced. The relationship between the tree height and the number of nodes is O(log N).
The insertion algorithm ensures that after replacing a Red-Black subtree with the next level's two subtrees of equal black height, all the subtrees remain Red-Black Trees. The time complexity of the insertion operation, except for Case 2, is constant.
- Case 1: If the subtree to be replaced has a black parent, we simply replace it. The black height of all subtrees remains unchanged, making it a valid operation.
- Case 2: If the subtree to be replaced has a red parent and red uncle, inserting the new node would result in consecutive red nodes. To resolve this, we change the colors of the parent, uncle, and grandparent. The grandparent becomes red. This transformation converts the subtree rooted at the grandparent into another valid insertion operation.
- Case 3: If the subtree to be replaced has a red parent and black uncle, inserting the new node would result in consecutive red nodes, but we cannot use the same method as in Case 2. However, in this case, the uncle, sibling, left child, and right child are all Red-Black Trees with equal black heights. Additionally, regardless of the rotation and rearrangement, the uncle, sibling, left child, and right child will always be the four bottommost leaf subtrees. Since the subtree rooted at the grandparent has one more black node than the uncle's subtree, we can simply change the color of the root to black, the second-level nodes to red, and transform it into a new Red-Black Tree while maintaining the overall tree's validity.
These three cases cover all possibilities. Except for Case 2, which may require O(log N) calculations, the other cases have constant time complexity.
Red-Black Tree Deletion
The deletion method in a Red-Black Tree involves the following steps:
- In an ordered binary tree, we can replace the node to be deleted with either the first element of its right subtree or the last element of its left subtree. This transformation converts the deletion operation into a subtree replacement operation using a Red-Black Tree.
- If the new Red-Black Tree has the same black height as the subtree being replaced (only possible if the root of the subtree is red), we can directly replace it.
- If the new Red-Black Tree has a black height one less than the subtree being replaced, we can enumerate four combinations of the parent, sibling, sibling's left child, and sibling's right child binary trees (a total of four cases). Then, we attach the five original leaf subtrees to the binary tree in a specific way, while keeping the color of the overall subtree unchanged. By considering all possible colors for the non-leaf nodes, we ensure that the entire subtree remains a valid Red-Black Tree, with the black height as close as possible to the original height. If the black height can only be reduced by one (when the sibling, sibling's left child, and sibling's right child are all black), the problem is transformed into a subtree replacement operation using a new Red-Black Tree rooted at the parent.
- Special attention should be given to boundary cases, such as replacing the entire subtree with a new Red-Black Tree. However, since Red-Black Trees are balanced trees, such cases are rare.
Because Red-Black Trees are balanced trees, this method is complete. Except for cases where the sibling, sibling's left child, and sibling's right child are all black, which may require O(log N) calculations, most other cases have constant time complexity.