AVL Trees and Balanced BSTs: short notes (Data Structures)

Introduction

Related material. The GATE 2027 CS syllabus names binary search trees but not AVL trees. AVL trees are included because they are the standard way to keep a binary search tree balanced.

Search, insertion and deletion in a binary search tree take time proportional to the tree's height $h$ . Inserting keys in sorted order builds a path of height $n - 1$ , so an unbalanced BST can degrade to $\Theta(n)$ per operation. A balanced BST adds a structural rule and repairs any violation after each update, keeping $h = O(\lg n)$ for every insertion order.

The AVL tree (Adelson-Velsky and Landis, 1962) was the first such scheme. Its rule is simple to state and to check, and its repair operations, rotations, are the same ones used by other balanced trees. This note covers the balance condition, the four rotation cases for insertion, deletion, the height bound through minimum-node (Fibonacci) trees, and a brief comparison with other balanced structures.

Conventions: heights follow Trees and Binary Trees: an empty tree has height $-1$ , a single node height 0. Keys are distinct. The rotation code uses the pointer fields left and right; the balance factor is $h_L - h_R$ .

Prerequisites

Binary Search Trees: search, insertion, deletion, inorder order.
Trees and Binary Trees: height, node counts.

Core concepts

The AVL condition

For every node $x$ , define the balance factor

\text{bf}(x) = h(\text{left subtree of } x) - h(\text{right subtree of } x).

A BST is an AVL tree if $\text{bf}(x) \in \{-1, 0, +1\}$ for every node. Each node stores its height (or its balance factor), updated on the way back up from an insertion or deletion.

Checking only the root is not enough: a tree whose root has two subtrees of equal height can still contain an unbalanced node deeper down.

Rotations

A rotation rearranges three links around an edge while preserving inorder order (so the tree is still a BST), and changes the heights of the subtrees involved.

Text

   right rotation at y              left rotation at x
        y                 x            x                  y
       / \               / \          / \                / \
      x   C     ==>     A   y        A   y      ==>     x   C
     / \                   / \          / \            / \
    A   B                 B   C        B   C          A   B

Inorder in both shapes is $A, x, B, y, C$ : the subtree $B$ changes parent, nothing else moves. A rotation uses $\Theta(1)$ time and $O(1)$ workspace.

C

struct avl { int key, h; struct avl *left, *right; };
static int ht(const struct avl *t) { return t ? t->h : -1; }
static void fix(struct avl *t) { int a = ht(t->left), b = ht(t->right); t->h = 1 + (a > b ? a : b); }

struct avl *rot_right(struct avl *y) {
    struct avl *x = y->left;
    y->left = x->right;        /* B moves from x to y */
    x->right = y;
    fix(y); fix(x);            /* y is now below x: update y first */
    return x;                  /* new root of this subtree */
}
/* rot_left is the mirror image */

How it works: insertion

Insert as in an ordinary BST, then walk back up the path to the root, updating heights. The first node $z$ found with $|\text{bf}(z)| = 2$ is repaired by one of four cases, named by the path from $z$ to the newly inserted key:

Case	New key is in	Repair
LL	left subtree of $z$ 's left child	single right rotation at $z$
RR	right subtree of $z$ 's right child	single left rotation at $z$
LR	right subtree of $z$ 's left child	left rotation at the left child, then right rotation at $z$
RL	left subtree of $z$ 's right child	right rotation at the right child, then left rotation at $z$

AVL rotations: LL, RR, LR and RL — Figure 1. The four insertion cases on three keys 10, 20, 30, each inserted in an order that unbalances the first node, and the balanced result 20 with children 10 and 30 in every case. LL and RR need one rotation; LR and RL need two.

At most one repair per insertion. After the repair, the subtree rooted where $z$ was has the same height it had before the insertion, so no ancestor's balance factor changes and the walk can stop. An insertion therefore needs at most one single or one double rotation, plus $O(\lg n)$ height updates.

In terms of balance factors: at $z$ with $\text{bf}(z) = +2$ , the case is LL if $\text{bf}(\text{left}) = +1$ and LR if $\text{bf}(\text{left}) = -1$ ; symmetrically for $-2$ .

Deletion

Delete as in an ordinary BST (a node with two children is replaced by its inorder successor or predecessor), then walk up to the root, rebalancing every node with $|\text{bf}| = 2$ . Deletion uses the same four rotations, with one extra situation: if the taller child of $z$ has balance factor 0, use the single rotation (LL or RR). Unlike insertion, a rotation after deletion can reduce the subtree's height, so imbalance can propagate upward; a deletion may need rotations at up to $O(\lg n)$ levels. The total cost is still $O(\lg n)$ .

The height bound

Let $N(h)$ be the minimum number of nodes in an AVL tree of height $h$ . The sparsest such tree has a root, one subtree of height $h - 1$ and one of height $h - 2$ , each as sparse as possible:

N(h) = 1 + N(h-1) + N(h-2), \qquad N(0) = 1,\; N(1) = 2 .

$h$	0	1	2	3	4	5	6
$N(h)$	1	2	4	7	12	20	33

These extremal trees are the Fibonacci trees, and $N(h) = F_{h+3} - 1$ , where $F_0 = 0, F_1 = 1$ . Since $F_k$ grows like $\varphi^k$ with the golden ratio $\varphi=(1+\sqrt{5})/2\approx1.618$ , an AVL tree with $n$ nodes has height

h < 1.4405 \lg (n + 2),

so every operation is $O(\lg n)$ . The maximum number of nodes at height $h$ is $2^{h+1} - 1$ (a perfect tree), as for any binary tree.

Using the table. The maximum height of an AVL tree with $n$ nodes is the largest $h$ with $N(h) \le n$ . With 20 nodes the maximum height is 5; with 12 nodes it is 4; with 7 nodes it is 3.

Worked examples

Each tree below is the result of inserting or deleting the given keys, preserving the AVL condition and BST order after every operation.

Example 1. Insert 10, 20, 30, 40, 50, 25 into an empty AVL tree.

10, 20, 30: node 10 has bf $-2$ , case RR: left rotation at 10. Tree: 20 (10, 30).
40, 50: node 30 has bf $-2$ , case RR: left rotation at 30. Tree: 20 (10, 40 (30, 50)).
25 goes left of 30. Node 20 has bf $0 - 2 = -2$ , its right child 40 has bf $+1$ : case RL. Right rotation at 40, then left rotation at 20.

Final tree, preorder 30 20 10 25 40 50: root 30, left child 20 (children 10 and 25), right child 40 (right child 50). Height 2.

Example 2. Inserting 1, 2, ..., 7 in increasing order performs four single left rotations and ends with the perfect tree of height 2, preorder 4 2 1 3 6 5 7. The same insertions into an ordinary BST give a path of height 6.

Example 3. Insert 50, 20, 60, 10, 30, 40. Adding 40 (right of 30) makes 50 have bf $+2$ with left child 20 at bf $-1$ : case LR. Result, preorder 30 20 10 50 40 60.

Example 4. Minimum nodes for height 4: $N(4) = 1 + N(3) + N(2) = 1 + 7 + 4 = 12$ .

Other balanced search trees (orientation only)

Structure	Balance rule	Height bound
AVL	$\lvert \text{bf} \rvert \le 1$ at every node	about $1.44 \lg n$
Red-black tree	colouring rules; every root-to-leaf path has the same number of black nodes	at most $2 \lg (n+1)$
B-tree, B+ tree	all leaves at the same depth; nodes hold many keys	$O(\log_m n)$ for order $m$

AVL trees are more rigidly balanced (faster searches); red-black trees need fewer rotations on updates. B-trees suit disks and are covered with databases (B-trees and B+ trees).

Important properties and observations

Balance factor in $\{-1, 0, +1\}$ at every node; heights are stored and updated bottom-up.
Rotations preserve inorder order and take $O(1)$ .
Insertion: at most one single or double rotation. Deletion: possibly one per level.
Minimum nodes $N(h) = N(h-1) + N(h-2) + 1$ ; maximum height for $n$ nodes from that table.
Search, insert and delete are $O(\lg n)$ in the worst case. In the unit-cost pointer/key model, successful search has best $\Theta(1)$ (root), and average $\Theta(\lg(n+1))$ for a uniformly chosen stored key. For $n\ge1$ , inserting a new distinct key and deleting by key using the stated successor/predecessor procedure each take $\Theta(\lg(n+1))$ time in the best, average and worst cases; the average bound holds under any distribution over these operations. Even the shortest root-to-leaf path in an AVL tree has length $\Omega(\lg(n+1))$ : height drops by at most two per edge. Insertion reaches a missing child; deletion searches to a node with at most one child, directly or through its successor/predecessor. Empty-tree operations take $\Theta(1)$ . Iterative parent-pointer updates use $O(1)$ workspace; recursive or stored-path versions use $O(\lg(n+1))$ stack space.

GATE examination perspective

Insert a sequence into an empty AVL tree and give the final tree, its root, its height or a traversal.
Identify the rotation needed (LL, RR, LR, RL) after a given insertion.
Minimum number of nodes in an AVL tree of height $h$ , or the maximum height with $n$ nodes; check the height convention in the question (some count the single node as height 1, which shifts the table by one).
Worst-case complexity of search, insertion and deletion compared with an unbalanced BST.

Summary

Binary Search Trees: prerequisite.
Trees and Binary Trees: prerequisite.
Binary Tree Traversals: related. Preorder answers to insertion questions.
Binary Heaps: related. Balanced shape does not imply BST key order.
B-trees and B+ Trees: related.

AVL Trees and Balanced BSTs

Introduction

Prerequisites

Core concepts

The AVL condition

Rotations

How it works: insertion

Deletion

The height bound

Worked examples

Other balanced search trees (orientation only)

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

The AVL condition

Rotations

How it works: insertion

Deletion

The height bound

Worked examples

Other balanced search trees (orientation only)

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps