AVL Tree
A search tree that rotates itself back into balance whenever two sides differ in height by two.
AVL Tree: Left-left needs a right rotation
At 30: left height 2, right height 0, balance 2. Too heavy on the left, and the new value went left of the left child. One right rotation.
Cost
- Search
- O(log n)
- Insert
- O(log n)
- Delete
- O(log n)
- Space
- O(n)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
AVL Tree covers these too, in the same run.