AVL Trees - Learning Module

Loading content...

0/276

What is an AVL Tree

The Quest for Balance

In 1962, two Soviet mathematicians—Georgy Adelson-Velsky and Evgenii Landis—published a groundbreaking paper that would forever change how we think about binary search trees. They had solved a problem that had haunted computer scientists since the invention of BSTs: the dreaded degenerate tree.

Their solution, named after their initials (AVL), was the world's first self-balancing binary search tree. It introduced a deceptively simple invariant: at every node, the heights of the left and right subtrees can differ by at most one. This single constraint, combined with an elegant mechanism for restoration, guarantees that an AVL tree with n elements never exceeds a height of approximately 1.44 log₂(n)—ensuring O(log n) operations no matter what order elements are inserted.

What You Will Learn

By the end of this page, you will:

• Understand the precise definition of an AVL tree and what distinguishes it from a regular BST • Know the historical significance of AVL trees in computer science • Grasp the height-balance invariant and why it guarantees logarithmic operations • Recognize AVL trees visually and understand their structural properties • Appreciate why the 'balance factor ∈ {-1, 0, +1}' constraint is both necessary and sufficient for efficient operations

The Problem AVL Trees Solve

Before diving into AVL trees, let's crystallize the problem they were designed to solve. Recall from our study of Binary Search Trees that:

The BST property guarantees that search, insertion, and deletion all take O(h) time, where h is the height of the tree.

In an ideal world—a perfectly balanced tree—this height is O(log n). But in the worst case—a completely degenerate tree—the height degrades to O(n), reducing our elegant search tree to a glorified linked list.

BST Performance: Best vs. Worst Case
Scenario	Tree Height	Search Time	Insert Time	Delete Time
Perfectly Balanced	O(log n)	O(log n)	O(log n)	O(log n)
Randomly Built	O(log n) expected	O(log n) expected	O(log n) expected	O(log n) expected
Sorted Insertion	O(n)	O(n)	O(n)	O(n)
Reverse-Sorted	O(n)	O(n)	O(n)	O(n)

The fundamental insight: We cannot control the order in which data arrives. Users might register in alphabetical order. Transactions might have incrementing IDs. Sensor readings might arrive in timestamp order. Any assumption about 'random' insertion is dangerous in production systems.

What we need is a tree that automatically maintains balance, adjusting its structure after each modification to ensure the height never exceeds O(log n). This is precisely what AVL trees provide.

The Cost of Worst-Case Degradation

Consider a database index built on a standard BST. If 1 million records are inserted in sorted order:

• Standard BST: Height = 1,000,000 → Each search takes ~1 million comparisons • AVL Tree: Height ≈ 29 → Each search takes ~29 comparisons

That's a 34,000× difference in performance. At 1μs per comparison, a search in the degenerate BST takes 1 second; in the AVL tree, it takes 29 microseconds.

Formal Definition of an AVL Tree

An AVL tree is a binary search tree that satisfies an additional structural constraint called the AVL property or height-balance property. Let's build this definition precisely.

Definition: Height of a Node

The height of a node in a binary tree is the length of the longest path from that node to a leaf. By convention:

• A null pointer (empty subtree) has height -1 • A leaf node has height 0 • An internal node has height = 1 + max(height of left child, height of right child)

Definition: Balance Factor

For any node v in a binary tree, the balance factor is defined as:

balanceFactor(v) = height(v.left) - height(v.right)

The balance factor tells us how 'lopsided' a node is:

Negative balance factor: The right subtree is taller
Zero balance factor: Both subtrees have equal height
Positive balance factor: The left subtree is taller

The AVL Property (Height-Balance Invariant)

A binary search tree is an AVL tree if and only if:

For every node v in the tree: balanceFactor(v) ∈ {-1, 0, +1}

In words: at every node, the heights of the left and right subtrees differ by at most 1. This invariant must hold at ALL nodes, not just the root.

Why 'at most one' and not 'exactly equal'?

You might wonder why we allow a height difference of 1 rather than requiring perfect balance. The answer is both practical and mathematical:

Perfect balance isn't always possible. A tree with 6 nodes cannot have equal-height subtrees at every node. Attempting perfect balance would require padding with dummy nodes.
Balance factor of ±1 is sufficient. As we'll prove later, allowing a height difference of 1 still guarantees that the tree height is O(log n). Specifically, an AVL tree of height h contains at least F(h+3) - 1 nodes, where F(i) is the i-th Fibonacci number.
It minimizes rebalancing overhead. Stricter invariants would require more frequent rotations, increasing constant factors.

Valid AVL Trees

•Every node has balance factor in {-1, 0, +1}
•The BST property holds at all nodes
•May be 'heavy' on either side at different nodes
•Includes perfectly balanced trees as a subset

Invalid AVL Trees

•Any node with |balance factor| ≥ 2
•Even if just ONE node violates the invariant
•Degenerate (linear) trees
•Trees violating the BST property

Visualizing AVL Trees

Let's develop visual intuition for what makes an AVL tree. Understanding this 'shape' helps you recognize balanced and unbalanced configurations instantly.

Converting Mermaid diagram...

In the tree above, every node's balance factor is annotated as 'bf'. Notice:

Node 50 (root): Left subtree has height 2, right subtree has height 2 → bf = 0
Node 25: Both subtrees have height 1 → bf = 0
Node 75: Left subtree has height 1, right subtree is null (height -1) → bf = 1 - (-1) = +2... Wait!

Actually, let me correct this visualization. Node 75 having only a left child of height 0 with no right child would give bf = 0 - (-1) = +1, which IS valid. The key is that 75's left subtree (rooted at 60) has height 0, and its right subtree is null (height -1), giving bf = 0 - (-1) = +1. This is still valid!

Visual Heuristic for AVL Trees

When looking at a tree, check each node mentally:

Look at the maximum depth reachable going left vs. going right
If the difference at any node exceeds 1, it's NOT an AVL tree
Remember: null children have height -1, so a node with one child has bf ∈ {-1, +1}

Example of an INVALID AVL Tree:

Converting Mermaid diagram...

Here, the root node 50 has a left subtree of height 3 and a right subtree of height 1. The balance factor is +2, which violates the AVL property. This tree would need rebalancing to become a valid AVL tree.

The Height Guarantee: Why AVL Trees Are Efficient

The most important property of AVL trees is the guaranteed height bound. This is what transforms BST operations from potentially O(n) to always O(log n).

Theorem: AVL Height Bound

For an AVL tree with n nodes:

height ≤ 1.44 × log₂(n + 2) - 0.328

Simplified: height = O(log n)

This means an AVL tree is never more than about 44% taller than a perfectly balanced tree.

Proof Sketch (via Fibonacci numbers):

To prove this, we ask: What is the minimum number of nodes in an AVL tree of height h? If we can show this minimum grows exponentially with h, then h must be logarithmic in n.

Let N(h) be the minimum nodes in an AVL tree of height h.

Base cases:

N(-1) = 0 (empty tree)
N(0) = 1 (single node)
N(1) = 2 (root with one child)

Recurrence: To build a minimal AVL tree of height h:

We need a root
One subtree must have height h-1 (to achieve overall height h)
The other subtree can have height h-2 (minimum allowed by AVL property)
Both subtrees must be minimal AVL trees themselves

Thus: N(h) = 1 + N(h-1) + N(h-2)

This is exactly the Fibonacci recurrence! In fact, N(h) = F(h+3) - 1, where F(i) is the i-th Fibonacci number.

Minimum Nodes in AVL Trees of Given Heights
Height	N(h) = Min Nodes	Fibonacci Relation
0	1	F(3) - 1 = 2 - 1 = 1
1	2	F(4) - 1 = 3 - 1 = 2
2	4	F(5) - 1 = 5 - 1 = 4
3	7	F(6) - 1 = 8 - 1 = 7
4	12	F(7) - 1 = 13 - 1 = 12
5	20	F(8) - 1 = 21 - 1 = 20
10	143	F(13) - 1 = 144 - 1 = 143
20	17,710	F(23) - 1 = 17,711 - 1

Since Fibonacci numbers grow as F(n) ≈ φⁿ/√5 where φ ≈ 1.618 (the golden ratio), we have:

n ≥ N(h) ≈ φʰ⁺³/√5

Solving for h:

h ≤ logᵩ(n√5) - 3 ≈ 1.44 log₂(n) - 1.33

The takeaway: No matter how adversarially data is inserted, an AVL tree of n nodes has height at most ~1.44 log₂(n). This is the worst case, not the average case. Most AVL trees are even shorter.

Comparison with Perfect Balance

A perfectly balanced tree has height exactly ⌊log₂(n)⌋. An AVL tree has height at most 1.44 × log₂(n). The ratio 1.44 comes from the golden ratio: logᵩ(2) ≈ 1.44.

In practice, this ~44% overhead in height translates to only a few extra levels even for very large trees. For 1 billion nodes: perfect balance = 30 levels, worst AVL = 43 levels. That's 13 extra comparisons per search—a tiny price for guaranteed performance.

AVL Trees in Context: Why They Matter

AVL trees occupy a unique position in the landscape of data structures. Understanding their role helps you know when to use them and when alternatives might be better.

Historical Significance

•First self-balancing BST (1962) — Adelson-Velsky and Landis invented AVL trees before Red-Black trees (1972), B-trees (1970), or any other balanced tree variant. They proved that efficient, worst-case O(log n) search trees were possible.
•Elegant mathematical foundation — The connection between minimal AVL trees and Fibonacci numbers is one of the most beautiful results in data structures. It demonstrates deep connections between combinatorics and computer science.
•Practical in-memory data structure — AVL trees are still used today in memory-intensive applications where lookup performance is critical. The Linux kernel uses AVL trees for certain memory management tasks.
•Teaching tool — AVL trees are often taught as the canonical example of a self-balancing tree because their invariant is simple to state and their rebalancing mechanism (rotations) is intuitive to visualize.

AVL Trees vs. Standard BSTs
Property	Standard BST	AVL Tree
Worst-case height	O(n)	O(log n)
Search (worst)	O(n)	O(log n)
Insert (worst)	O(n)	O(log n)
Delete (worst)	O(n)	O(log n)
Space overhead	None	O(n) for height/balance info
Implementation complexity	Simple	Moderate (rotations required)
Insertion/deletion cost	Just BST operations	BST + potential rotations

When to Use AVL Trees:

Lookup-heavy workloads: AVL trees maintain stricter balance than Red-Black trees, resulting in shallower trees and faster lookups. If you search far more often than you insert/delete, AVL is excellent.
Real-time systems: The O(log n) guarantee matters when worst-case latency is unacceptable. Games, trading systems, and control systems benefit from predictable performance.
Database indices (in-memory): When data lives entirely in RAM and rapid key lookup is essential.
Ordered data structures: When you need not just lookup buy also predecessor/successor, range queries, and ordered iteration—all of which are O(log n) in AVL trees.

AVL vs. Red-Black Trees

You might have heard of Red-Black trees (used in Java's TreeMap, C++'s std::map). The key tradeoff:

• AVL trees: Stricter balance → fewer levels → faster lookups • Red-Black trees: Looser balance → fewer rotations on insert/delete → faster modifications

In practice, the differences are small. Both are O(log n) for all operations. Choose AVL for read-heavy workloads; Red-Black for write-heavy.

The Structure of an AVL Node

To implement an AVL tree, each node must store additional information beyond the standard BST fields. Let's examine the complete node structure.

avl_node.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class AVLNode:
    """
    A node in an AVL tree. Each node stores:
    - key: The value used for BST ordering
    - left, right: Pointers to child nodes
    - height: Height of the subtree rooted at this node
    
    Note: We store height rather than balance factor because:
    1. Height is needed to compute balance factor anyway
    2. Height updates are straightforward during rotations
    3. Balance factor can be derived: bf = left.height - right.height
    """
    
    def __init__(self, key):
        self.key = key
        self.left = None   # Left child
        self.right = None  # Right child
        self.height = 0    # Height of this node (leaf = 0)
    
    def get_height(node):
        """Return height of a node, handling None as -1."""
        if node is None:
            return -1
        return node.height
    
    def update_height(self):
        """Recalculate height based on children's heights."""
        left_height = AVLNode.get_height(self.left)
        right_height = AVLNode.get_height(self.right)
        self.height = 1 + max(left_height, right_height)
    
    def balance_factor(self):
        """Calculate balance factor: left height - right height."""
        left_height = AVLNode.get_height(self.left)
        right_height = AVLNode.get_height(self.right)
        return left_height - right_height

Key Design Decisions:

Store height, not balance factor: While you could store balance factor directly (it's just -1, 0, or +1), storing height is more robust. Heights are needed for rotation calculations, and deriving balance factor from heights is trivial.
Null convention: Null children have height -1. This ensures that:
- A leaf (no children) has height 0 = max(-1, -1) + 1
- Single-child nodes have correct balance factors
Update height after changes: Any operation that modifies the tree structure (insertion, deletion, rotation) must update affected nodes' heights.

Space Overhead

Each AVL node requires one extra integer (the height field) compared to a standard BST node. For 1 million nodes with 32-bit integers, this is just 4 MB of extra space—negligible for the guaranteed O(log n) performance it enables.

Summary: Understanding AVL Trees

Let's consolidate what we've learned about AVL trees before moving on to the mechanics of how they maintain balance.

Key Takeaways

•AVL trees are self-balancing BSTs — They automatically maintain balance after insertions and deletions, eliminating the O(n) worst case of standard BSTs.
•The AVL property is simple: |balance factor| ≤ 1 at every node — The balance factor is the difference between left and right subtree heights.
•Height is guaranteed to be O(log n) — Specifically, height ≤ 1.44 log₂(n), ensuring all operations are logarithmic.
•The height bound derives from Fibonacci numbers — Minimal AVL trees follow the Fibonacci recurrence, connecting this data structure to beautiful mathematics.
•AVL nodes store height information — This O(n) space overhead enables O(1) balance factor computation and efficient rebalancing.
•AVL trees excel at lookup-heavy workloads — Their stricter balance (compared to Red-Black trees) makes them faster for searches.

What's Next:

We've defined what an AVL tree IS—but how does it STAY balanced? When we insert or delete a node, the balance factors change. If any node's balance factor becomes ±2, the AVL property is violated.

In the next section, we'll deep-dive into the balance factor concept, examining exactly how insertions and deletions affect balance factors throughout the tree. Then we'll learn about rotations—the elegant mechanism AVL trees use to restore balance in O(1) time.

Page Complete

You now understand what an AVL tree is: a binary search tree where every node has a balance factor of -1, 0, or +1. This simple invariant guarantees O(log n) height, transforming BST operations from potentially linear to always logarithmic. Next, we'll explore the balance factor in depth and prepare for understanding rotations.

What is an AVL Tree

The Quest for Balance

What You Will Learn

By the end of this page, you will:

The Problem AVL Trees Solve

Before diving into AVL trees, let's crystallize the problem they were designed to solve. Recall from our study of Binary Search Trees that:

The BST property guarantees that search, insertion, and deletion all take O(h) time, where h is the height of the tree.

BST Performance: Best vs. Worst Case
Scenario	Tree Height	Search Time	Insert Time	Delete Time
Perfectly Balanced	O(log n)	O(log n)	O(log n)	O(log n)
Randomly Built	O(log n) expected	O(log n) expected	O(log n) expected	O(log n) expected
Sorted Insertion	O(n)	O(n)	O(n)	O(n)
Reverse-Sorted	O(n)	O(n)	O(n)	O(n)

The Cost of Worst-Case Degradation

Consider a database index built on a standard BST. If 1 million records are inserted in sorted order:

• Standard BST: Height = 1,000,000 → Each search takes ~1 million comparisons • AVL Tree: Height ≈ 29 → Each search takes ~29 comparisons

That's a 34,000× difference in performance. At 1μs per comparison, a search in the degenerate BST takes 1 second; in the AVL tree, it takes 29 microseconds.

Formal Definition of an AVL Tree

An AVL tree is a binary search tree that satisfies an additional structural constraint called the AVL property or height-balance property. Let's build this definition precisely.

Definition: Height of a Node

The height of a node in a binary tree is the length of the longest path from that node to a leaf. By convention:

• A null pointer (empty subtree) has height -1 • A leaf node has height 0 • An internal node has height = 1 + max(height of left child, height of right child)

Definition: Balance Factor

For any node v in a binary tree, the balance factor is defined as:

balanceFactor(v) = height(v.left) - height(v.right)

The balance factor tells us how 'lopsided' a node is:

Negative balance factor: The right subtree is taller
Zero balance factor: Both subtrees have equal height
Positive balance factor: The left subtree is taller

The AVL Property (Height-Balance Invariant)

A binary search tree is an AVL tree if and only if:

For every node v in the tree: balanceFactor(v) ∈ {-1, 0, +1}

In words: at every node, the heights of the left and right subtrees differ by at most 1. This invariant must hold at ALL nodes, not just the root.

Why 'at most one' and not 'exactly equal'?

You might wonder why we allow a height difference of 1 rather than requiring perfect balance. The answer is both practical and mathematical:

Perfect balance isn't always possible. A tree with 6 nodes cannot have equal-height subtrees at every node. Attempting perfect balance would require padding with dummy nodes.
Balance factor of ±1 is sufficient. As we'll prove later, allowing a height difference of 1 still guarantees that the tree height is O(log n). Specifically, an AVL tree of height h contains at least F(h+3) - 1 nodes, where F(i) is the i-th Fibonacci number.
It minimizes rebalancing overhead. Stricter invariants would require more frequent rotations, increasing constant factors.

Valid AVL Trees

•Every node has balance factor in {-1, 0, +1}
•The BST property holds at all nodes
•May be 'heavy' on either side at different nodes
•Includes perfectly balanced trees as a subset

Invalid AVL Trees

•Any node with |balance factor| ≥ 2
•Even if just ONE node violates the invariant
•Degenerate (linear) trees
•Trees violating the BST property

Visualizing AVL Trees

Let's develop visual intuition for what makes an AVL tree. Understanding this 'shape' helps you recognize balanced and unbalanced configurations instantly.

Converting Mermaid diagram...

In the tree above, every node's balance factor is annotated as 'bf'. Notice:

Node 50 (root): Left subtree has height 2, right subtree has height 2 → bf = 0
Node 25: Both subtrees have height 1 → bf = 0
Node 75: Left subtree has height 1, right subtree is null (height -1) → bf = 1 - (-1) = +2... Wait!

Visual Heuristic for AVL Trees

When looking at a tree, check each node mentally:

Look at the maximum depth reachable going left vs. going right
If the difference at any node exceeds 1, it's NOT an AVL tree
Remember: null children have height -1, so a node with one child has bf ∈ {-1, +1}

Example of an INVALID AVL Tree:

Converting Mermaid diagram...

The Height Guarantee: Why AVL Trees Are Efficient

The most important property of AVL trees is the guaranteed height bound. This is what transforms BST operations from potentially O(n) to always O(log n).

Theorem: AVL Height Bound

For an AVL tree with n nodes:

height ≤ 1.44 × log₂(n + 2) - 0.328

Simplified: height = O(log n)

This means an AVL tree is never more than about 44% taller than a perfectly balanced tree.

Proof Sketch (via Fibonacci numbers):

To prove this, we ask: What is the minimum number of nodes in an AVL tree of height h? If we can show this minimum grows exponentially with h, then h must be logarithmic in n.

Let N(h) be the minimum nodes in an AVL tree of height h.

Base cases:

N(-1) = 0 (empty tree)
N(0) = 1 (single node)
N(1) = 2 (root with one child)

Recurrence: To build a minimal AVL tree of height h:

We need a root
One subtree must have height h-1 (to achieve overall height h)
The other subtree can have height h-2 (minimum allowed by AVL property)
Both subtrees must be minimal AVL trees themselves

Thus: N(h) = 1 + N(h-1) + N(h-2)

This is exactly the Fibonacci recurrence! In fact, N(h) = F(h+3) - 1, where F(i) is the i-th Fibonacci number.

Minimum Nodes in AVL Trees of Given Heights
Height	N(h) = Min Nodes	Fibonacci Relation
0	1	F(3) - 1 = 2 - 1 = 1
1	2	F(4) - 1 = 3 - 1 = 2
2	4	F(5) - 1 = 5 - 1 = 4
3	7	F(6) - 1 = 8 - 1 = 7
4	12	F(7) - 1 = 13 - 1 = 12
5	20	F(8) - 1 = 21 - 1 = 20
10	143	F(13) - 1 = 144 - 1 = 143
20	17,710	F(23) - 1 = 17,711 - 1

Since Fibonacci numbers grow as F(n) ≈ φⁿ/√5 where φ ≈ 1.618 (the golden ratio), we have:

n ≥ N(h) ≈ φʰ⁺³/√5

Solving for h:

h ≤ logᵩ(n√5) - 3 ≈ 1.44 log₂(n) - 1.33

Comparison with Perfect Balance

A perfectly balanced tree has height exactly ⌊log₂(n)⌋. An AVL tree has height at most 1.44 × log₂(n). The ratio 1.44 comes from the golden ratio: logᵩ(2) ≈ 1.44.

AVL Trees in Context: Why They Matter

AVL trees occupy a unique position in the landscape of data structures. Understanding their role helps you know when to use them and when alternatives might be better.

Historical Significance

•First self-balancing BST (1962) — Adelson-Velsky and Landis invented AVL trees before Red-Black trees (1972), B-trees (1970), or any other balanced tree variant. They proved that efficient, worst-case O(log n) search trees were possible.
•Elegant mathematical foundation — The connection between minimal AVL trees and Fibonacci numbers is one of the most beautiful results in data structures. It demonstrates deep connections between combinatorics and computer science.
•Practical in-memory data structure — AVL trees are still used today in memory-intensive applications where lookup performance is critical. The Linux kernel uses AVL trees for certain memory management tasks.
•Teaching tool — AVL trees are often taught as the canonical example of a self-balancing tree because their invariant is simple to state and their rebalancing mechanism (rotations) is intuitive to visualize.

AVL Trees vs. Standard BSTs
Property	Standard BST	AVL Tree
Worst-case height	O(n)	O(log n)
Search (worst)	O(n)	O(log n)
Insert (worst)	O(n)	O(log n)
Delete (worst)	O(n)	O(log n)
Space overhead	None	O(n) for height/balance info
Implementation complexity	Simple	Moderate (rotations required)
Insertion/deletion cost	Just BST operations	BST + potential rotations

When to Use AVL Trees:

Lookup-heavy workloads: AVL trees maintain stricter balance than Red-Black trees, resulting in shallower trees and faster lookups. If you search far more often than you insert/delete, AVL is excellent.
Real-time systems: The O(log n) guarantee matters when worst-case latency is unacceptable. Games, trading systems, and control systems benefit from predictable performance.
Database indices (in-memory): When data lives entirely in RAM and rapid key lookup is essential.
Ordered data structures: When you need not just lookup buy also predecessor/successor, range queries, and ordered iteration—all of which are O(log n) in AVL trees.

AVL vs. Red-Black Trees

You might have heard of Red-Black trees (used in Java's TreeMap, C++'s std::map). The key tradeoff:

• AVL trees: Stricter balance → fewer levels → faster lookups • Red-Black trees: Looser balance → fewer rotations on insert/delete → faster modifications

In practice, the differences are small. Both are O(log n) for all operations. Choose AVL for read-heavy workloads; Red-Black for write-heavy.

The Structure of an AVL Node

To implement an AVL tree, each node must store additional information beyond the standard BST fields. Let's examine the complete node structure.

avl_node.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class AVLNode:
    """
    A node in an AVL tree. Each node stores:
    - key: The value used for BST ordering
    - left, right: Pointers to child nodes
    - height: Height of the subtree rooted at this node
    
    Note: We store height rather than balance factor because:
    1. Height is needed to compute balance factor anyway
    2. Height updates are straightforward during rotations
    3. Balance factor can be derived: bf = left.height - right.height
    """
    
    def __init__(self, key):
        self.key = key
        self.left = None   # Left child
        self.right = None  # Right child
        self.height = 0    # Height of this node (leaf = 0)
    
    def get_height(node):
        """Return height of a node, handling None as -1."""
        if node is None:
            return -1
        return node.height
    
    def update_height(self):
        """Recalculate height based on children's heights."""
        left_height = AVLNode.get_height(self.left)
        right_height = AVLNode.get_height(self.right)
        self.height = 1 + max(left_height, right_height)
    
    def balance_factor(self):
        """Calculate balance factor: left height - right height."""
        left_height = AVLNode.get_height(self.left)
        right_height = AVLNode.get_height(self.right)
        return left_height - right_height

Key Design Decisions:

Store height, not balance factor: While you could store balance factor directly (it's just -1, 0, or +1), storing height is more robust. Heights are needed for rotation calculations, and deriving balance factor from heights is trivial.
Null convention: Null children have height -1. This ensures that:
- A leaf (no children) has height 0 = max(-1, -1) + 1
- Single-child nodes have correct balance factors
Update height after changes: Any operation that modifies the tree structure (insertion, deletion, rotation) must update affected nodes' heights.

Space Overhead

Summary: Understanding AVL Trees

Let's consolidate what we've learned about AVL trees before moving on to the mechanics of how they maintain balance.

Key Takeaways

•AVL trees are self-balancing BSTs — They automatically maintain balance after insertions and deletions, eliminating the O(n) worst case of standard BSTs.
•The AVL property is simple: |balance factor| ≤ 1 at every node — The balance factor is the difference between left and right subtree heights.
•Height is guaranteed to be O(log n) — Specifically, height ≤ 1.44 log₂(n), ensuring all operations are logarithmic.
•The height bound derives from Fibonacci numbers — Minimal AVL trees follow the Fibonacci recurrence, connecting this data structure to beautiful mathematics.
•AVL nodes store height information — This O(n) space overhead enables O(1) balance factor computation and efficient rebalancing.
•AVL trees excel at lookup-heavy workloads — Their stricter balance (compared to Red-Black trees) makes them faster for searches.

What's Next:

We've defined what an AVL tree IS—but how does it STAY balanced? When we insert or delete a node, the balance factors change. If any node's balance factor becomes ±2, the AVL property is violated.

Page Complete