AVL Tree

A binary search tree that rotates to keep the two subtrees of every node within one level of each other. Feed a plain BST ascending keys and it degenerates into a linked list; an AVL tree performs a rotation and stays logarithmic. The four rebalancing cases — LL, RR, LR, RL — are all shown.

Best

O(log n)

Average

O(log n)

Worst

O(log n)

Space

O(n)