Red Black Tree

Introduction

Red Black Tree: a type of self-balancing binary search tree (BST). Ensures O(log n) height. Maintains balance via color properties and rotations. Used widely in associative containers, memory management, databases. Invented by Rudolf Bayer (1972), refined by Guibas and Sedgewick (1978). Guarantees worst-case performance for search, insertion, deletion.

"Red-black trees provide a way to maintain balance in a binary search tree while allowing for efficient insertion and deletion operations." -- Robert Sedgewick

Definition and Properties

Definition

Binary search tree with an extra bit of storage per node: color (red or black). Balances itself by enforcing color and structural constraints.

Properties

• Each node is red or black.
• Root is always black.
• All leaves (NIL) are black.
• If a node is red, both children are black (no two reds in a row).
• Every path from a node to descendant leaves has the same number of black nodes (black-height).

Implications

These properties guarantee the tree height is at most 2 * log2(n+1). Enables balanced search tree operations.

Structure and Node Attributes

Node Components

Key: value stored. Color: red or black. Left and right child pointers. Parent pointer (optional but common).

Leaf Representation

Leaves represented by sentinel NIL nodes colored black. Simplifies boundary cases in algorithms.

Black-Height Concept

Number of black nodes on path to NIL leaves. Same black-height across paths from any node ensures balanced structure.

Insertion Algorithm

Step 1: Standard BST Insert

Insert new node as in binary search tree. New node colored red.

Step 2: Fix Violations

Violations of red-black properties corrected by recoloring and rotations. Fix proceeds bottom-up.

Cases in Fix-up

• Case 1: Uncle red - recolor parent, uncle to black, grandparent to red; recurse at grandparent.
• Case 2: Uncle black, new node inside subtree - rotate parent.
• Case 3: Uncle black, new node outside subtree - rotate grandparent.

INSERT(node): 1. BST-Insert(node, red) 2. While parent(node) is red: a. Identify uncle(node) b. If uncle red: Recolor parent and uncle to black Recolor grandparent to red node = grandparent c. Else: If node is inside subtree: Rotate parent Rotate grandparent Recolor nodes appropriately 3. Root color = black

Deletion Algorithm

Step 1: Standard BST Delete

Delete node using binary search tree rules (replace with successor if two children).

Step 2: Fix Violations

Fix double black or color violations using recoloring and rotations.

Cases in Fix-up

• Case 1: Sibling red - rotate and recolor.
• Case 2: Sibling black with black children - recolor sibling red, move up tree.
• Case 3: Sibling black with at least one red child - rotate and recolor accordingly.

DELETE(node): 1. BST-Delete(node) 2. If deleted node or replacement black: Fix-Double-Black(node) FIX-DOUBLE-BLACK(node): While node != root and node black: a. Identify sibling b. If sibling red: Rotate and recolor c. If sibling black with black children: Recolor sibling red node = parent(node) d. Else: Rotate and recolor node = root node.color = black

Tree Rotations

Purpose

Adjust tree structure to maintain red-black properties without violating BST order.

Types

• Left Rotation: pivots around a node to the left child becoming parent
• Right Rotation: pivots around a node to the right child becoming parent

Effect on Subtrees

Rotations preserve in-order traversal sequence, thus preserving BST property.

Time and Space Complexity

Time Complexity

• Search: O(log n) worst-case
• Insertion: O(log n) worst-case including fixup
• Deletion: O(log n) worst-case including fixup

Space Complexity

O(n) for storing n nodes. Additional constant space for color bit and pointers.

Height Bound

Height ≤ 2 * log2(n+1). Ensures balanced tree.

Applications and Use Cases

Associative Containers

Used in implementations of maps, sets in STL (C++), TreeMap (Java).

Memory Management

Kernel allocators use red-black trees to manage free blocks.

Databases and File Systems

Indexing structures requiring balanced search trees.

Other Uses

Priority queues, dynamic order statistics.

Advantages and Limitations

Advantages

• Guaranteed logarithmic height
• Efficient insertions and deletions
• Simple to implement compared to AVL trees
• Good worst-case performance

Limitations

• Balancing less strict than AVL, so searches may be slower
• More complex fixup code than simple BST
• Rotations and recoloring add overhead

Comparison with Other Trees

AVL Tree

AVL more strictly balanced; faster searches, slower insert/delete.

Splay Tree

Splay trees have amortized O(log n) but no guaranteed worst-case; simpler code.

B-Trees

B-Trees optimized for disk storage, multi-way nodes; different use cases.

Summary Table

Implementation Details

Data Structures

Struct or class for node: includes key, color, pointers. NIL sentinel nodes for leaves.

Algorithm Flow

Insertion and deletion use helper functions for rotations and fixup. Recursive or iterative approaches.

Common Pitfalls

• Incorrect recoloring order causing infinite loops.
• Failure to update parent pointers during rotations.
• Mismanagement of NIL sentinel nodes.

Optimizations and Variants

Left-Leaning Red Black Tree (LLRB)

Simplifies red-black tree by enforcing left-leaning red links. Easier to implement.

Augmented Red Black Trees

Store extra info per node (size, intervals) for advanced queries.

Memory Optimizations

Pack color bit with pointer using bit manipulation. Reduce memory overhead.

Parallel and Concurrent Variants

Lock-free or fine-grained locking implementations for multi-threaded environments.

References

• R. Bayer, "Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms," Acta Informatica, vol. 1, 1972, pp. 290–306.
• L. J. Guibas and R. Sedgewick, "A Dichromatic Framework for Balanced Trees," Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978, pp. 8–21.
• R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms," Addison-Wesley, 1992, ch. on red-black trees.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to Algorithms," 3rd ed., MIT Press, 2009, pp. 317–321.
• M. D. McIlroy, "Balanced Search Trees Made Simple," Software: Practice and Experience, vol. 25, no. 8, 1995, pp. 871–883.