AVL Insert with Rebalancing
Insert as a BST, walk back up updating heights, and rotate the first unbalanced node.
AVL Tree: A longer mixed sequence
At 50: left height 1, right height 0, balance 1. Within one, so it stays.
Cost
- Best
- O(log n)
- Average
- O(log n)
- Worst
- O(log n)
- Space
- O(1)
Leads to
Topics that need this one first.
Taught by the same lesson
AVL Tree covers these too, in the same run.