Self-balancing trees creation
Jump to navigation
Jump to search
Problem Description
Self-Balancing Binary Search Trees are height-balanced binary search trees that automatically keeps height as small as possible when insertion and deletion operations are performed on tree. The height is typically maintained in order of Log n so that all operations take O(Log n) time on average.
Bounds Chart
File:Self-balancing trees creationBoundsChart.png
Step Chart
File:Self-balancing trees creationStepChart.png
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | ||
| nlogn | [ AVL Tree (1962)]
Guibas, Sedgewick Red-Black Tree (1972) [ 2-3 Tree (1970)] [ Tarjan Splay Tree (1985)] [ Bayer, McCreight B-Tree (1970)] |
|
| Linear | ||
| logn |