How to Use
- Insert: Enter a value and click "Insert"
- Delete: Enter a value and click "Delete"
- Search: Enter a value and click "Search"
- Random Red-Black Tree: Click to generate a random tree
- Reset: Click to clear the tree
Red-Black Tree Concept
Red-Black Tree is a self-balancing binary search tree where each node has a color (red or black) and follows specific rules to maintain balance.
Key Properties:
- Every node is either red or black
- Root is always black
- Red nodes have black children
- All paths from root to leaves have same black height
Red-Black Tree Setup
Red-Black Tree Operations
Tree Visualization
(Zoom out if tree nodes fall out of screen)
Operation Steps
Purpose & Applications
- Java TreeMap and TreeSet
- C++ std::map and std::set
- Linux kernel scheduler
- Database indexing
Time & Space Complexity
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Search | O(log n) | O(n) |
| Get Height | O(n) | O(1) |
Strengths & Limitations
Strengths:
- Guaranteed O(log n) operations
- Fewer rotations than AVL trees
Limitations:
- More complex implementation
- Slightly less balanced than AVL