7.16 AVL Trees

AVL trees were the first self-balancing binary search trees. Introduced in 1962 by entity["people","Georgy Adelson-Velsky","AVL tree co-inventor"] and entity["people","Evgenii Landis","AVL tree co-inventor"], they established many of the balancing techniques that later tree structures would adopt.

The defining characteristic of an AVL tree is strict balance. Every node tracks the relative heights of its left and right subtrees. Whenever an insertion or deletion causes that difference to become too large, rotations restore balance immediately.

This strictness produces very shallow trees and excellent search performance. The trade-off is additional bookkeeping during updates.

Compared with red-black trees, AVL trees usually perform more rotations but often achieve slightly faster lookups because their height is smaller.

Problem

Consider inserting values into a binary search tree.

A naïve BST becomes:

10
  \\n   20
     \\n      30
        \\n         40
           \\n            50

Height:

Searching for:

requires traversing every node.

To maintain logarithmic performance, we need to detect imbalance and repair it before the tree becomes excessively tall.

Understanding AVL Balance

An AVL tree associates a height with every node.

Example:

        40
       /  \\n     20    60
    / \    / \\n  10 30 50 70

Node heights:

The AVL rule states:

|height(left) - height(right)| ≤ 1

for every node.

This difference is called the balance factor.

Balance Factor

The balance factor of a node is:

height(left) - height(right)

Examples:

Balance = 0

Perfectly balanced.

Balance = 1

Left subtree is one level taller.

Balance = -1

Right subtree is one level taller.

These values are valid.

However:

Balance = 2

or:

Balance = -2

indicates imbalance.

The tree must be repaired.

Example of Imbalance

Insert:

10
20
30

Result:

10
  \\n   20
     \\n      30

Heights:

30 = 1
20 = 2
10 = 3

Balance factors:

30 = 0
20 = -1
10 = -2

Node 10 violates the AVL rule.

A rotation is required.

AVL Node Structure

A typical node stores:

type Node struct {
	Key    int
	Height int

	Left  *Node
	Right *Node
}

The stored height allows balance factors to be computed efficiently.

Without this metadata, height calculations would require repeated subtree traversals.

Height Calculation

Helper function:

func Height(n *Node) int {
	if n == nil {
		return 0
	}

	return n.Height
}

Balance factor:

func Balance(n *Node) int {
	if n == nil {
		return 0
	}

	return Height(n.Left) -
		Height(n.Right)
}

These small functions appear throughout AVL implementations.

Updating Heights

Whenever a subtree changes:

func UpdateHeight(n *Node) {
	left := Height(n.Left)
	right := Height(n.Right)

	if left > right {
		n.Height = left + 1
	} else {
		n.Height = right + 1
	}
}

Every rotation must update heights before returning.

Incorrect height updates are one of the most common AVL bugs.

The Four AVL Cases

Every AVL imbalance falls into one of four patterns.

Left-Left (LL)

Repair:

Right rotation

Result:

      y
     / \\n    x   z

LL Rotation Example

Before:

After:

    20
   /  \\n 10    30

A single right rotation restores balance.

Right-Right (RR)

Mirror image of LL.

  z
   \\n    y
     \\n      x

Repair:

Left rotation

Example:

10
  \\n   20
     \\n      30

After:

    20
   /  \\n 10    30

Left-Right (LR)

Structure:

A single rotation is insufficient.

Step 1:

Rotate left at x

Step 2:

Rotate right at z

Result:

      y
     / \\n    x   z

LR Example

Before:

      30
     /
   10
     \\n      20

Rotate left:

Rotate right:

      20
     /  \\n   10    30

Balance restored.

Right-Left (RL)

Mirror image of LR.

    z
     \\n      x
     /
    y

Step 1:

Rotate right at x

Step 2:

Rotate left at z

Result:

      y
     / \\n    z   x

These four cases cover every AVL imbalance.

Insertion

Insertion begins as an ordinary BST insertion.

func Insert(
	root *Node,
	key int,
) *Node

After insertion:

Update heights.
Compute balance factor.
Apply the appropriate rotation if necessary.

The search path from the insertion point back to the root is the only region that can become imbalanced.

This locality keeps insertion efficient.

Simplified Insertion Flow

Insert node

Update height

Compute balance

If LL:
    rotate right

If RR:
    rotate left

If LR:
    rotate left
    rotate right

If RL:
    rotate right
    rotate left

Most AVL insertion code follows exactly this structure.

Example Walkthrough

Insert:

30
20
10

Tree:

Balance:

30 = 2

Violation detected.

Apply LL repair.

      20
     /  \\n   10    30

The height drops immediately.

Deletion

Deletion is more complicated than insertion.

Removing a node can decrease subtree heights, causing imbalance to propagate upward.

Unlike insertion, multiple rotations may be required while walking back toward the root.

The same four cases still apply:

LL
RR
LR
RL

The difference is that deletion may trigger balancing at several levels.

Why AVL Trees Search Quickly

Because AVL trees enforce strict balance, their height remains very close to optimal.

For:

1,000,000 nodes

Typical AVL height is around:

levels.

This is often slightly better than red-black trees.

Search operations therefore perform fewer comparisons on average.

AVL Trees Versus Red-Black Trees

AVL trees maintain stricter balance.

Red-black trees permit more variation.

Consequences:

Feature	AVL	Red-Black
Search speed	Faster	Slightly slower
Insert speed	Slightly slower	Faster
Delete speed	Slightly slower	Faster
Height	Smaller	Larger
Rotations	More frequent	Less frequent

The difference is usually modest, but it influences system design.

AVL Trees Versus Treaps

Treaps rely on random priorities.

AVL trees rely on deterministic height constraints.

Feature	AVL	Treap
Balance	Deterministic	Randomized
Height guarantee	Worst-case O(log n)	Expected O(log n)
Rotations	Structured	Priority-driven
Implementation complexity	Moderate	Low
Search performance	Excellent	Very good

AVL trees provide stronger guarantees.

Treaps provide simpler code.

Real-World Usage

AVL trees are particularly attractive when:

Searches dominate updates
Predictable lookup latency matters
Data remains mostly static
Ordered access is required

Examples include:

Read-heavy indexes
Routing tables
Symbol tables
Configuration stores
Memory-resident catalogs

In highly write-intensive systems, red-black trees are often preferred.

Complexity Analysis

AVL height remains:

O(log n)

Therefore:

Operation	Complexity
Search	O(log n)
Insert	O(log n)
Delete	O(log n)
Minimum	O(log n)
Maximum	O(log n)
Lower bound	O(log n)
Upper bound	O(log n)

Space complexity:

O(n)

The height field adds only constant overhead per node.

Common Mistakes

A common error is updating heights before rotations but not after rotations. Every node participating in a rotation must have its height recomputed.

Another mistake is confusing balance factors. The convention:

height(left) - height(right)

must be applied consistently.

A third mistake is performing the wrong rotation sequence. LR and RL cases require two rotations, not one.

Finally, many implementations recalculate subtree heights recursively. Storing heights directly in each node is essential for maintaining logarithmic update costs.

Takeaway

AVL trees maintain logarithmic height through strict balance-factor constraints. By tracking subtree heights and applying one of four rotation patterns whenever imbalance appears, they keep search paths short and predictable. Their stronger balancing rules generally produce faster lookups than red-black trees at the cost of additional maintenance during updates. AVL trees illustrate a central theme in data structure design: paying a small cost during modification can significantly improve future queries.