AVL Balanced Trees

DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).

AVL Balanced Trees: keeping search fast even in the worst case

A plain BST can degrade into a slow, lopsided line. AVL trees refuse to let that happen.

If you insert sorted data (1,2,3,4,5...) into a plain BST, it degenerates into essentially a linked list — O(n) search instead of the O(log n) you wanted. An AVL tree automatically rebalances itself after every insertion/deletion to prevent this.

Balance factor = height(left subtree) − height(right subtree) A node is "balanced" only if its balance factor is -1, 0, or +1. If it goes outside this range after an insertion, a ROTATION is triggered to fix it.

🔄 The Four Rotation Cases

LLLeft-Left heavy — fix with a single right rotation.

RRRight-Right heavy — fix with a single left rotation.

LRLeft-Right heavy — fix with a left rotation, then a right rotation.

RLRight-Left heavy — fix with a right rotation, then a left rotation.

💡 The guaranteed numerical: "Insert this sequence of values into an AVL tree, showing every rotation performed" — practice a full sequence of 6-8 insertions until you can identify LL/RR/LR/RL cases on sight and apply the correct rotation immediately.

A full insertion sequence

Insert 10, 20, 30, 40, 50, 25 into an empty AVL tree. This sequence is chosen because it triggers two different rotation cases in six steps.

insert 10 tree: 10 balanced insert 20 tree: 10(–, 20) balanced (bf = −1) insert 30 node 10 now has bf = −2, and 30 went RIGHT of 20 → RR case → single LEFT rotation at 10 tree: 20(10, 30) root is now 20 insert 40 tree: 20(10, 30(–, 40)) balanced insert 50 node 30 has bf = −2, 50 went RIGHT of 40 → RR case → single LEFT rotation at 30 tree: 20(10, 40(30, 50)) insert 25 node 20 has bf = −2, but 25 went LEFT of 40 → RL case → RIGHT rotation at 40, then LEFT at 20 tree: 30(20(10, 25), 40(–, 50)) height 3

Read the case from two pieces of information: which side is heavy (the sign of the balance factor) and which side of the child the new key went. Heavy-right plus inserted-right is RR; heavy-right plus inserted-left is RL. Getting the second half wrong is what turns a single rotation into the wrong answer.

💡 The rotation always happens at the lowest unbalanced node, found by walking back up from the insertion point. Higher ancestors usually rebalance automatically once that one is fixed, which is why a single rotation (or double) is enough per insertion.

Why the balance factor limit is ±1 and not 0

Demanding a balance factor of exactly 0 would mean a perfectly balanced tree — which only exists when the node count is exactly 2ᵏ−1. Any other count is impossible to balance perfectly, so the requirement would be unsatisfiable.

Allowing ±1 keeps the height within about 1.44·log₂n — close enough to log n to preserve the guarantee, while loose enough that most insertions need no rotation at all. It is a deliberate compromise between how balanced and how much work to stay that way.

💡 That trade-off is why other balanced trees exist. Red-black trees allow a looser bound (up to 2·log n), so they rotate less on insertion and are preferred where writes dominate; AVL trees stay tighter and search slightly faster, which suits read-heavy use.

What deletion costs

Insertion needs at most one rotation, single or double — fixing the lowest unbalanced node restores every ancestor. Deletion has no such guarantee: rebalancing one node can unbalance its parent, so rotations may cascade all the way to the root, up to O(log n) of them.

💡 That asymmetry is a favourite short question: "how many rotations can a single AVL insertion require?" — one. "And a deletion?" — up to the height of the tree.

Syllabus points

Balance factor
Rotations: LL, RR, LR, RL (numerical)

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.