AlgoScope

AVL Tree

A search tree that rotates itself back into balance whenever two sides differ in height by two.

Data structures, data structure, advanced
Node 30 has balance 2. It needs a rotation.102030current
Node 30 has balance 2. It needs a rotation.102030current

AVL Tree: Left-left needs a right rotation

Decision, step 10 of 12

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)

Leads to

Topics that need this one first.

Taught by the same lesson

AVL Tree covers these too, in the same run.