Properties and Balancing Operations of Red-Black Trees

A red-black tree is a self-balancing binary search tree that maintains balance through specific rules and rotation operations, ensuring worst-case time complexity of O(log n) for search, insertion, and deletion operations. Below, I will explain in detail the properties and balancing operations of red-black trees.

1. Definition and Properties of Red-Black Trees

A red-black tree is a binary search tree where each node has a color attribute (red or black) and must satisfy the following five properties:

• Property 1: Each node is either red or black.
• Property 2: The root node is black.
• Property 3: All leaf nodes (NIL nodes, i.e., empty nodes) are black.
• Property 4: The children of a red node must be black (i.e., no two consecutive red nodes are allowed).
• Property 5: For any node, the number of black nodes on all paths from that node to its descendant leaf nodes is the same (known as consistent "black height").

These properties ensure the key characteristic of red-black trees: the length of the path from the root to the farthest leaf node will not exceed twice the length of the shortest path, thereby achieving approximate balance.

2. Basic Structure of Red-Black Trees

• Each node contains: key value, color, left child, right child, parent node.
• Leaf nodes are represented as NIL nodes (considered black empty nodes).
• Example: A simple red-black tree may have a black root node with a red left child, but it must satisfy Properties 4 and 5.

3. Balancing Operations: Rotation

When insertion or deletion of a node violates the red-black tree properties, rotations are used to adjust the tree. There are two types of rotations:

• Left Rotation: With node x as the pivot, promote x's right child y as the new parent node, making x the left child of y, while adjusting relevant child nodes.
  • Steps:
    1. Set y's left child as x's right child.
    2. If y's left child is not NIL, set its parent pointer to x.
    3. Set y's parent as x's parent and update the parent's child pointer to y.
    4. Set x as y's left child, making y the parent of x.
• Right Rotation: Symmetric to left rotation, with node y as the pivot, promote y's left child x as the parent node, making y the right child of x.

Rotation operations do not change the ordering properties of the binary search tree but alter the height structure, preparing for subsequent color adjustments.

4. Insertion Operation and Balancing Adjustment

When inserting a new node, it is first inserted like in a standard binary search tree and initialized as red (to avoid violating Property 5). Then, a "fix-up" process is used to restore the properties:

• Step 1: If the inserted node is the root, simply color it black (satisfying Property 2).
• Step 2: If the parent node is black, no adjustment is needed (Property 4 is not violated).
• Step 3: If the parent node is red (violating Property 4), handle it based on the following cases:
  • Case 1: The uncle node (the sibling of the parent) is red.
    • Operation: Recolor the parent and uncle nodes to black, recolor the grandparent to red, then recursively process the grandparent as the current node.
  • Case 2: The uncle node is black, and the current node is the right child of its parent (forming a triangular structure).
    • Operation: Perform a left rotation with the parent as the pivot, converting it to Case 3.
  • Case 3: The uncle node is black, and the current node is the left child of its parent (forming a linear structure).
    • Operation: Recolor the parent to black, recolor the grandparent to red, then perform a right rotation with the grandparent as the pivot.

Through these three cases, the properties of the red-black tree are restored. The time complexity of insertion is O(log n).

5. Deletion Operation and Balancing Adjustment

The deletion operation is more complex. First, perform a standard binary search tree deletion:

• If the node to be deleted has two non-NIL children, replace its value with the successor node's value, then delete the successor node.
• The node actually deleted has at most one non-NIL child. Denote the deleted node as y and its child as x (x may be NIL).

After deletion, if y is black, the black height (Property 5) may be violated, requiring adjustment via a "fix-up" process:

• Step 1: If x is red, simply recolor it to black to restore balance.
• Step 2: If x is black, handle it based on the following cases (let w be x's sibling node):
  • Case 1: w is red.
    • Operation: Recolor w to black, recolor the parent to red, perform a left rotation with the parent as the pivot, then convert to Case 2, 3, or 4.
  • Case 2: w is black, and both of w's children are black.
    • Operation: Recolor w to red, treat x's parent as the new current node and recursively process.
  • Case 3: w is black, and w's left child is red while its right child is black.
    • Operation: Recolor w's left child to black, recolor w to red, perform a right rotation with w as the pivot, converting to Case 4.
  • Case 4: w is black, and w's right child is red.
    • Operation: Set w's color to the parent's color, recolor the parent to black, recolor w's right child to black, perform a left rotation with the parent as the pivot, and end the adjustment.

Deletion fix-up ensures property restoration through rotations and recoloring, with a time complexity of O(log n).

6. Applications of Red-Black Trees

Red-black trees are widely used in scenarios requiring efficient dynamic set operations, such as:

• Standard libraries of programming languages (e.g., C++'s std::map, Java's TreeMap).
• Database index structures.
• Kernel schedulers for managing process queues.

Summary: Red-black trees efficiently maintain balance during insertion and deletion through color constraints and rotation operations, balancing performance and implementation complexity. Understanding their properties and adjustment logic is key to mastering advanced data structures.