What is an AVL Tree?

Every node in an AVL Tree tracks its own height: the number of edges on the longest path down to a leaf. A leaf has height 1, and an empty subtree counts as height 0. From the height of a node's two children, you can compute its balance factor: height(left) - height(right).

A node is balanced when its balance factor is -1, 0, or 1. The AVL Tree's rule is simple: every single node must stay balanced, all the time. Whenever an insert or delete pushes a node's balance factor to 2 or -2, the tree performs a rotation: a local rearrangement of a few pointers that restores balance in constant time without breaking the search-tree ordering.

There are four rotation cases (left-left, right-right, left-right, right-left), but they all boil down to two building blocks: a single left rotation and a single right rotation. You will build both from scratch in the next few lessons.