What is a Red-Black Tree?
A Red-Black Tree is a type of self-balancing binary search tree where each node has an extra bit to store its color (red or black). This data structure ensures that the tree remains approximately balanced during insertions and deletions, guaranteeing O(log n) time complexity for basic operations.
Red-Black Tree Properties
Every Red-Black Tree must satisfy these fundamental properties:
- Every node is either red or black
- The root node is always black
- All leaf nodes (NIL nodes) are black
- Red nodes cannot have red children (no two red nodes can be adjacent)
- Every path from a node to its descendant NIL nodes contains the same number of black nodes
Key Operations
Basic Operations
- Search: Find a specific value in O(log n) time
- Insert: Add a new node while maintaining tree properties
- Delete: Remove a node and rebalance the tree
- Traversal: Visit all nodes in sorted order
Balancing Operations
When the Red-Black properties are violated during insertion or deletion, the tree uses these operations to restore balance:
- Rotation: Left and right rotations to restructure subtrees
- Recoloring: Change node colors to satisfy properties
Visual Representation
Example of a Red-Black Tree with red and black nodes
Advantages & Applications
Performance
Guaranteed O(log n) for search, insert, and delete operations
Balance
Self-balancing property prevents degeneration into a linear structure
Real-world Use
Used in Java's TreeMap, Linux kernel's CFS scheduler, and many databases