Definition
A Red Black Tree is a self-balancing binary search tree where each node is designated as either red or black.
Properties
- Every node is either red or black
- The root is always black
- All leaves (NIL nodes) are black
- If a node is red, its children must be black (i.e no two consecutive nodes can be red)
- Every path from root to leaves must have the same number of black nodes (Black Height Property)
Visual Representation
Example of a valid Red-Black Tree
Basic Operations
Insertion
When inserting a node:
- Insert like a regular BST
- Color the new node red
- Recolor and rotate as needed to rebalance
Deletion
When deleting a node:
- Perform a standard BST deletion
- Perfom color repairs
- Rebalance the tree based on new colors
A more in-depth tutorial of performing operations on a Red-Black Tree can be found here.
Time Complexities
| Operation | Average Case | Worst Case |
|---|---|---|
| Access | O(log n) | O(log n) |
| Insert | O(log n) | O(log n) |
| Delete | O(log n) | O(log n) |