Red-Black Trees
A Self-Balancing Binary Search Tree
Key Properties
- Every node is either red or black.
- The root is always black.
- Red nodes cannot have red children (no two consecutive red nodes).
- Every path from a node to its descendant NULL nodes has the same number of black nodes.
Advantages of Red-Black Trees
- Ensures O(log n) time complexity for insertions, deletions, and lookups.
- Maintains balance automatically, preventing degeneration into linked lists.
- Widely used in computational applications, including Linux kernel trees and associative containers in C++ STL.
Red-Black Tree Structure
