AVL Delete with Rebalancing
Delete like a BST, then rebalance every ancestor. Unlike insert, several rotations may be needed.
AVL Tree: Delete a leaf and rotate above it
Found 90 as the right child of 75. It is a leaf, so it is simply unlinked.
Cost
- Best
- O(log n)
- Average
- O(log n)
- Worst
- O(log n)
- Space
- O(1)
Before this
Taught by the same lesson
AVL Tree covers these too, in the same run.