Red-Black Tree: Principles and Implementation

Red-Black Tree: Principles and Implementation

A Red-Black Tree is a self-balancing binary search tree. It adds a color storage bit (red or black) to each node and ensures that no path from the root to any leaf is twice as long as any other path by constraining the colors of nodes along every such path, thereby achieving approximate balance.

I. Basic Properties of Red-Black Trees
A Red-Black Tree must satisfy the following five properties:

  1. Every node is either red or black.
  2. The root node is black.
  3. Every leaf node (NIL node, empty node) is black.
  4. If a node is red, then both its children are black (i.e., no two adjacent red nodes are allowed).
  5. For any node, all paths from it to descendant leaves contain the same number of black nodes (equal black height).

II. Basic Operations of Red-Black Trees

1. Node Structure
Each node contains: key value (key), color (color), left child (left), right child (right), and parent node (parent).

2. Rotation Operations
Rotation is a fundamental operation for maintaining balance:

  • Left Rotation: Using a node as the pivot, its right child becomes the new parent node.
  • Right Rotation: Using a node as the pivot, its left child becomes the new parent node.

III. Detailed Insertion Operation

Step 1: Standard Binary Search Tree Insertion
First, insert the new node according to the rules of a binary search tree. The newly inserted node is initially colored red (this does not violate the black height property but may violate the rule that no two adjacent nodes are red).

Step 2: Color Adjustment and Rotation
After insertion, check for any violations of the Red-Black Tree properties, primarily addressing the following cases:

Case 1: The Inserted Node Is the Root Node
Simply change its color to black.

Case 2: The Parent Node Is Black
No properties are violated, so no adjustment is needed.

Case 3: The Parent Node Is Red (Requires Adjustment)
This case requires further subcase handling:

Case 3.1: The Uncle Node Is Red

  • Change the parent and uncle nodes to black.
  • Change the grandparent node to red.
  • Treat the grandparent node as the new current node and continue adjustments.

Case 3.2: The Uncle Node Is Black, and the Current Node Is the Right Child of Its Parent

  • Perform a left rotation with the parent node as the pivot.
  • Treat the original parent node as the new current node and proceed to Case 3.3.

Case 3.3: The Uncle Node Is Black, and the Current Node Is the Left Child of Its Parent

  • Change the parent node to black.
  • Change the grandparent node to red.
  • Perform a right rotation with the grandparent node as the pivot.

IV. Detailed Deletion Operation

Step 1: Standard Binary Search Tree Deletion
First, perform the standard binary search tree deletion. If the deleted node is red, no adjustment is usually needed; if it is black, rebalancing is required.

Step 2: Post-Deletion Balance Adjustment
Primarily address the following cases:

Case 1: The Sibling Node Is Red

  • Change the sibling node to black.
  • Change the parent node to red.
  • Perform a left/right rotation on the parent node.
  • Re-determine the sibling node and continue processing.

Case 2: The Sibling Node Is Black, and Both Children of the Sibling Node Are Black

  • Change the sibling node to red.
  • Treat the parent node as the new current node and continue adjustments.

Case 3: The Sibling Node Is Black, and the Sibling's Near Nephew Node Is Red, While the Far Nephew Node Is Black

  • Change the sibling node to red.
  • Change the near nephew node to black.
  • Perform a right/left rotation on the sibling node.
  • Re-determine the sibling node and proceed to Case 4.

Case 4: The Sibling Node Is Black, and the Sibling's Far Nephew Node Is Red

  • Set the sibling node's color to the parent node's color.
  • Change the parent node and the far nephew node to black.
  • Perform a left/right rotation on the parent node.
  • Adjustment is complete.

V. Time Complexity of Red-Black Trees

  • Search, Insertion, Deletion: O(log n)
  • Rotation Operations: At most 2 rotations per insertion, at most 3 rotations per deletion.

VI. Application Scenarios of Red-Black Trees

  1. C++ STL: map, multimap, set, multiset
  2. Java: TreeMap, TreeSet
  3. Linux Kernel: Process Scheduling
  4. File System Directory Structures
  5. Database Index Structures

Red-Black Trees achieve relatively good balance performance through simple rules and operations, making them more efficient in practical applications compared to other balanced trees like AVL trees.