AlgoScope

Right Rotation

The left child comes up and the old node drops to its right.

Tree algorithms, algorithm, intermediate
After the rotation 20 heads the subtree and it is balanced.102030current
After the rotation 20 heads the subtree and it is balanced.102030current

AVL Tree: Left-left needs a right rotation

Step, step 11 of 12

20 is now the root of this subtree, with 30 beneath it. Heights differ by at most one again, and nothing above needs checking: the subtree is exactly as tall as before the insert.

Cost

Best
O(1)
Average
O(1)
Worst
O(1)
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.