The AVL Tree

Matt George

Fractional CTO · Founder of Injuria.ai

•19 min read•

The AVL Tree

An AVL tree is a self-balancing binary search tree, a fundamental data structure in computer science used to store and retrieve ordered data efficiently. In a standard binary search tree, the arrangement of nodes depends entirely on the order in which data is inserted. If data arrives in a sorted or nearly sorted sequence, the tree can degrade into a linear chain, causing basic operations like search, insertion, and deletion to degrade to linear time complexity[1]. The AVL tree solves this problem by enforcing a strict structural invariant: for every node in the tree, the heights of its left and right child subtrees can differ by at most one.[19]

When an insertion or deletion violates this height invariant, the AVL tree automatically restores its balance through a series of localized structural modifications known as tree rotations[2]. By maintaining this strict balance, the AVL tree guarantees that its overall height remains logarithmic relative to the number of nodes it contains. This mathematical property ensures that all primary operations execute in logarithmic time[3], even in the worst-case scenario.

Invented in 1962 by Soviet mathematicians Georgy Adelson-Velsky and Evgenii Landis[4], the AVL tree holds historical significance as the first self-balancing binary search tree[5] ever published.[20] Its introduction established the theoretical foundation for guaranteed logarithmic-time data structures, influencing decades of subsequent research in computer science. Today, while other balanced trees have been developed to optimize specific operational tradeoffs, the AVL tree remains a standard subject in algorithmic education and sees active use in specialized software systems requiring fast, predictable read performance.

Definition and the Problem It Solves

A binary search tree is a node-based data structure where each node contains a key, and every node satisfies the binary search property[1]: all keys in the left subtree are less than the node's key, and all keys in the right subtree are greater. This organization allows for efficient searching by repeatedly dividing the search space in half, similar to a binary search on a sorted array.

The efficiency of a standard binary search tree is directly tied to its height, defined as the number of edges on the longest path from the root node to any leaf node. In an optimal, perfectly balanced state, a binary search tree containing $n$ nodes has a height of $\lfloor \log_2(n) \rfloor$. In this state, searching for a specific key requires at most $\log_2(n)$ comparisons. For a dataset of one million records, a perfectly balanced tree requires no more than twenty comparisons to locate any specific record.

However, the standard binary search tree algorithm does not actively maintain this balance. If keys are inserted in ascending or descending order, each new node becomes the right or left child of the previous node. For example, inserting the sequence 1, 2, 3, 4, 5 into an empty standard binary search tree results in a structure where node 1 is the root, node 2 is its right child, node 3 is the right child of 2, and so forth. The resulting structure is structurally identical to a linked list[1], with a height of $n - 1$. In this degenerate case, the time required to search, insert, or delete a node becomes $O(n)$, defeating the primary purpose of using a tree structure. Searching for the last element in a degenerate tree of one million records would require one million comparisons.

The AVL tree addresses this vulnerability by introducing a self-balancing mechanism based on a specific invariant. The invariant dictates that for any given node in the tree, the height of its left subtree and the height of its right subtree may differ by no more than one.[19] This difference is formalized as the "balance factor[5]" of a node, calculated by subtracting the height of the left subtree from the height of the right subtree. In a valid AVL tree, the balance factor of every node must be exactly -1, 0, or +1.

If an operation causes the balance factor of any node to become -2 or +2, the tree is considered unbalanced. The AVL tree algorithm immediately detects this violation and restructures the affected portion of the tree before the operation completes. By strictly enforcing this localized height constraint across all nodes, the AVL tree mathematically guarantees a global property: the maximum height of the tree is bounded by approximately 1.44 log_2(n). Consequently, the worst-case time complexity for search, insertion, and deletion operations is strictly bounded to $O(\log n)$.

Mechanism and Operations

The operational mechanics of an AVL tree rely on augmenting the standard binary search tree node[1] structure to track height information and applying specific restructuring algorithms when the balance invariant is violated.

Node Structure and Memory Layout

Each node in an AVL tree stores its key, optional satellite data, pointers to its left and right children, and an integer representing its height.[21] The height of a leaf node is typically defined as 1 (or 0, depending on the specific implementation convention), and the height of an internal node is one greater than the maximum height of its two children. Storing the height directly in the node allows the balance factor to be computed in $O(1)$ time during traversal.

In low-level systems programming, the memory layout of an AVL tree node is a subject of optimization. A standard node requires space for two memory pointers, the key, and the height integer. On a 64-bit architecture, the pointers consume 16 bytes, while a 32-bit integer key and a 32-bit height integer consume 8 bytes, resulting in a 24-byte node. To reduce memory consumption, some implementations do not store the full height integer. Instead, they store the balance factor (-1, 0, or +1) directly using two bits of memory[3]. These two bits can often be packed into the unused alignment padding of the node structure or hidden within the lowest bits of the child pointers on architectures that enforce pointer alignment, saving space at the cost of slightly more complex bitwise operations during tree modifications.

Searching

The search operation in an AVL tree is identical to that of a standard binary search tree. The algorithm begins at the root and compares the target key to the current node's key. If the target is smaller, the search proceeds to the left child; if larger, it proceeds to the right child. This process repeats until the target key is found or a null pointer is reached, indicating that the key does not exist in the dataset. Because the AVL tree strictly bounds its height, the search operation is guaranteed to complete in O(log n) time. The search operation does not modify the tree structure and never triggers rebalancing, making it entirely read-only and highly efficient for concurrent read access.

Insertion

Inserting a new node into an AVL tree begins with a standard BST insertion[1]: the algorithm traverses down the tree to find the correct empty position and attaches the new node as a leaf.[21] Following the insertion, the algorithm must trace the path back up to the root, updating the height of each ancestor node along the way. During this upward traversal, the algorithm calculates the balance factor for each node.

If a node is found to have a balance factor of -2 or +2, the tree has become unbalanced at that specific node, and a rotation is required to restore the invariant[2]. A defining property of the AVL tree insertion algorithm is that a single rotation (or double rotation) at the lowest unbalanced node is always sufficient to restore the balance of the entire tree. Once the local imbalance is fixed, the height of the subtree rooted at the rotated node returns to the value it had before the insertion, meaning no further imbalances can propagate up the tree.

Deletion

Deletion follows a more complex pattern. The target node is removed using standard binary search tree deletion rules. If the node is a leaf, it is simply removed. If it has one child, the child takes the node's place. If the node has two children, the algorithm must find its in-order successor (the smallest node in the right subtree) or in-order predecessor (the largest node in the left subtree) to replace the deleted node, and then recursively delete that successor or predecessor.

After the physical removal of the node, the algorithm traverses back up to the root, updating heights and checking balance factors. Unlike insertion, where a single rotation operation is sufficient to restore the balance of the entire tree, a deletion can reduce the overall height of a subtree. This reduction in height can cause an imbalance at the parent node. When a rotation is performed to fix the parent, the height of the parent's subtree might decrease again, potentially causing an imbalance at the grandparent node. Consequently, a single deletion can trigger a cascading effect of imbalances, requiring up to O(log n) rotations[5] propagating all the way to the root.

Both insertion and deletion require $O(\log n)$ time to traverse the tree and $O(\log n)$ time to update heights and perform rotations, resulting in a total worst-case time complexity of $O(\log n)$. The space complexity is $O(n)$ to store the nodes, plus $O(\log n)$ auxiliary space for the call stack if the operations are implemented recursively.

Tree Rotations

Tree rotations are the core mechanism[3] by which the AVL tree restores its balance. A rotation changes the structure of the tree by rearranging pointers while strictly preserving the in-order sequence of the keys. There are four specific imbalance scenarios, each addressed by a corresponding rotation strategy.

  1. Left-Left Case: The imbalance occurs because a node was inserted into the left subtree of the left child. This is resolved with a single Right Rotation. The left child becomes the new root of the subtree, and the original unbalanced node becomes its right child.
  2. Right-Right Case: The imbalance occurs because a node was inserted into the right subtree of the right child. This is resolved with a single Left Rotation. The right child becomes the new root of the subtree, and the original unbalanced node becomes its left child.
  3. Left-Right Case: The imbalance occurs because a node was inserted into the right subtree of the left child. This requires a Left-Right Rotation (a double rotation). A single rotation cannot fix this because rotating the unbalanced node to the right would transfer the heavy right subtree of the left child to the left subtree of the root, leaving the tree unbalanced. Instead, the algorithm first performs a Left Rotation on the left child, transforming the structure into a Left-Left case. Then, a Right Rotation is performed on the original unbalanced node.
  4. Right-Left Case: The imbalance occurs because a node was inserted into the left subtree of the right child. This requires a Right-Left Rotation. First, a Right Rotation is performed on the right child, transforming the structure into a Right-Right case. Then, a Left Rotation is performed on the original unbalanced node.

The following pseudocode demonstrates a standard Right Rotation, which resolves a Left-Left imbalance.

function rightRotate(y):
    x = y.left
    T2 = x.right

    // Perform rotation
    x.right = y
    y.left = T2

    // Update heights
    y.height = max(height(y.left), height(y.right)) + 1
    x.height = max(height(x.left), height(x.right)) + 1

    // Return new root
    return x

For a Left-Right double rotation, the algorithm combines the basic rotations:

function leftRightRotate(z):
    z.left = leftRotate(z.left)
    return rightRotate(z)

Mathematical Bounds and Fibonacci Trees

The worst-case height of an AVL tree is analyzed using Fibonacci trees[6], which are AVL trees constructed to have the minimum possible number of nodes for a given height $h$. By understanding the minimum number of nodes required to reach a certain height, computer scientists can determine the maximum possible height for a given number of nodes.

A Fibonacci tree of height $h$, denoted as $T_h$, is constructed by taking a Fibonacci tree of height $h-1$ as its left child and a Fibonacci tree of height $h-2$ as its right child. The minimum number of nodes $N(h)$ in such a tree is defined by the recurrence relation $N(h) = N(h-1) + N(h-2) + 1$, with base cases $N(0) = 1$ and $N(1) = 2$.

This relation closely mirrors the standard Fibonacci sequence. It can be solved exactly by adding 1 to both sides of the equation, resulting in $N(h) + 1 = (N(h-1) + 1) + (N(h-2) + 1)$. This demonstrates that the term $N(h) + 1$ is exactly the Fibonacci sequence shifted by two positions, specifically $F_{h+3}$.

Since the Fibonacci numbers have a known closed-form solution known as Binet's formula, which involves the golden ratio $\phi \approx 1.618$, the height $h$ can be expressed in terms of the node count $N$. Solving the equation for $h$ yields $h \approx \log_\phi(\sqrt{5}(N+1)) - 3$. By converting the base of the logarithm from $\phi$ to 2, the final mathematical bound is established as $h \approx 1.44 \log_2(n)$. This rigorous mathematical foundation guarantees that an AVL tree will never exceed a height approximately 44 percent greater than that of a perfectly balanced binary tree, ensuring predictable and fast execution times.

Discovery and History

The AVL tree was invented by Georgy Adelson-Velsky and Evgenii Landis, two Soviet mathematicians and computer scientists working at the Institute of Theoretical and Experimental Physics[4] (ITEP) in Moscow.[20] In 1962, they published their findings in a paper titled "An algorithm for the organization of information" in the Doklady Akademii Nauk SSSR (Proceedings of the USSR Academy of Sciences). The paper was quickly translated into English and published in the journal Soviet Mathematics Doklady later that same year.

At the time of its publication, computer science was an emerging discipline, and the efficient organization of data in random-access memory was a primary area of theoretical and practical research. While the basic binary search tree was already known, its worst-case linear time complexity made it unreliable for large-scale data processing. Adelson-Velsky and Landis's algorithm was the first published method for maintaining a dynamically balanced search tree, effectively solving the worst-case degradation problem.

The invention of the AVL tree predated other major balanced tree structures. The B-tree[7], designed for disk-based storage, was invented in 1970 by Rudolf Bayer and Edward M. McCreight. The Red-Black tree[8], another highly popular in-memory balanced tree, was formalized in 1978 by Leonidas Guibas and Robert Sedgewick, building upon Bayer's 1972 work on symmetric binary B-trees.

Following its introduction, the AVL tree became a foundational topic in computer science algorithms. Half-balanced binary search trees were introduced in 1980 (or 1982), which attempted to reduce the strictness of the AVL invariant to improve update speeds. Throughout the 1980s, computer scientists like Robert Tarjan extensively analyzed the amortized complexity of balanced trees, leading to the development of splay trees[9] and providing deeper mathematical insights into the efficiency of AVL tree rotations.

Important Variants

Over the decades, researchers have developed several variants of the AVL tree to optimize its performance characteristics for specific workloads.

Red-Black Trees

While not strictly a variant of the AVL tree, the Red-Black tree is its most direct alternative and is frequently compared to it. A Red-Black tree maintains balance using a coloring scheme[10] (nodes are either red or black) and a set of rules that ensure no path from the root to a leaf is more than twice as long as any other path. Because the Red-Black tree allows a looser balance (a height difference up to a factor of 2, compared to the AVL tree's strict difference of 1), it requires fewer rotations[11] during insertions and deletions. However, this looser balance means that Red-Black trees can be taller than AVL trees, resulting in slightly slower search times.

WAVL Trees (Weak AVL Trees)

Introduced in 2009 by Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan[12], the WAVL tree[13] combines the strict height bound of the AVL tree with the efficient restructuring of the Red-Black tree. WAVL trees replace the strict height calculation with a "rank" system, where each node is assigned a non-negative integer rank, and null nodes have a rank of -1. The balance is maintained by enforcing rules on the rank differences between a node and its parent.

In a WAVL tree, insertions require at most two rotations, identical to AVL and Red-Black trees. However, deletions in a WAVL tree require at most two rotations and O(1) amortized time for restructuring[12], matching the deletion efficiency of Red-Black trees. Despite this relaxed restructuring, WAVL trees maintain a worst-case height bound very close to that of a standard AVL tree, making them a highly efficient modern alternative.

Relaxed AVL Trees

Relaxed AVL trees[14] were proposed to address the performance bottleneck caused by the immediate rebalancing requirement of standard AVL trees. In a relaxed AVL tree, the balance factor invariant is allowed to be temporarily violated. Updates are applied quickly, and the resulting imbalances are queued. A separate background process or a delayed maintenance algorithm later traverses the tree to perform the necessary rotations. This variant is particularly useful in concurrent environments where locking the tree for immediate rotations would cause unacceptable contention among multiple threads.

Splay Trees

Other tree structures have been developed that abandon the strict worst-case guarantees of the AVL tree in favor of amortized performance. Splay trees[9], invented by Daniel Sleator and Robert Tarjan, perform rotations to move recently accessed elements to the root, optimizing for workloads with high temporal locality. While these structures adapt to access patterns and do not require storing balance factors in the nodes, they lack the strict $O(\log n)$ worst-case guarantee for every single operation that the AVL tree provides.

Real-World Applications

While Red-Black trees and B-trees are more common in general-purpose standard libraries and databases, the AVL tree is utilized in specific real-world systems where read operations significantly outnumber write operations, and where strict worst-case search performance is required.

Windows NT Virtual Address Descriptor (VAD)

The Microsoft Windows operating system kernel uses an AVL tree to manage the virtual address space of each process. When a Windows process allocates memory using system calls like VirtualAlloc, the kernel creates a Virtual Address Descriptor[15] (VAD) node. This node, typically represented by the _MMVAD structure in the kernel, contains information about the allocated memory range (starting and ending virtual page numbers), its protection flags (such as read, write, or execute), and inheritance properties.

These VAD nodes are organized into an AVL tree rooted in the process's _EPROCESS structure, specifically accessed via the VadRoot field. When a thread accesses a memory address that is not currently mapped in the hardware page tables, a page fault occurs. The Windows page fault handler must quickly determine if the accessed address belongs to a valid allocated region. By storing the VADs in an AVL tree, the kernel ensures that this lookup process completes in strict O(log n) lookup times[15], minimizing the latency of memory access validation. The choice of an AVL tree here is deliberate: memory allocations (insertions) are relatively infrequent compared to the massive volume of memory accesses and page faults (searches) that occur during normal process execution.

Linux Kernel Memory Management

Historically, the Linux kernel utilized AVL trees to manage virtual memory areas (VMAs), represented by the vm_area_struct[16] data structure. Each VMA describes a contiguous block of virtual memory assigned to a process, tracking the start and end addresses, access flags, and the mapped file if applicable. Similar to Windows, the Linux kernel needs to search these structures rapidly during page faults using functions like find_vma.

While AVL trees provided the necessary fast lookups, the Linux kernel eventually transitioned to using Red-Black trees for VMA management[16], storing the root in the mm_rb field of the memory descriptor. The transition occurred because processes frequently map and unmap memory, or expand their stacks, generating a high volume of insertion and deletion operations. The strict balancing of the AVL tree required too many rotations, causing performance overhead in write-heavy scenarios. More recently, Linux kernel developers have begun replacing the Red-Black tree implementation with the Maple Tree[17], an RCU-safe B-tree variant, to further reduce lock contention on multi-core systems.

Language Libraries and Databases

In standard programming language libraries, such as the C++ Standard Template Library[18] (STL), associative containers like std::set and std::map are typically implemented using Red-Black trees. However, some specific implementations or specialized libraries provide AVL trees as an alternative for developers who know their workload is read-dominated. Additionally, certain in-memory databases and routing table implementations use AVL trees to guarantee the fastest possible lookup times for static or slow-changing datasets. In disk-based relational databases, AVL trees are entirely superseded by B-trees, as the deep pointer-based structure of a binary tree requires too many slow disk seeks compared to the wide, shallow structure of a B-tree.

Significance and Tradeoffs

The primary significance of the AVL tree is its historical role in proving that a dynamic data structure can maintain guaranteed logarithmic time complexity[3] for all basic operations. It established the paradigm of self-balancing trees, directly influencing the design of almost all subsequent ordered data structures.

The decision to use an AVL tree in a modern software system depends entirely on the specific tradeoffs of the workload. The strict balancing invariant of the AVL tree ensures that it is always highly compact. Because its maximum height is strictly bounded to $\approx 1.44 \log_2(n)$, search operations require fewer comparisons on average and in the worst case compared to a Red-Black tree, which can have a height of up to $2 \log_2(n)$. This makes the AVL tree an optimal choice for read-heavy applications, such as static dictionaries, routing tables, or memory validation structures where data is written once and read millions of times.

Conversely, this strict invariant is the AVL tree's primary disadvantage in write-heavy workloads. Insertions and deletions are highly likely to violate the strict balance factor, triggering tree rotations. While a single rotation is an $O(1)$ operation, the need to frequently modify pointers and update heights across multiple nodes causes cache invalidation[1] and memory overhead. Modern central processing units rely heavily on cache lines to prefetch contiguous blocks of memory. The AVL tree, like all binary search trees, suffers from poor cache locality because its nodes are dynamically allocated and scattered across the heap. Traversing the tree requires chasing pointers to arbitrary memory locations, which frequently results in cache misses.

In multithreaded environments, these structural modifications require exclusive locks on large portions of the tree, creating contention that degrades concurrent performance. For applications with high mutation rates, Red-Black trees offer a better compromise by reducing the frequency of rotations, and B-trees offer superior performance[7] by optimizing for CPU cache lines and disk blocks. Despite these modern hardware realities, the AVL tree remains a foundational algorithmic design, providing a mathematically perfect solution to the problem of dynamic data organization.

Sources (21)
  1. mitpress.mit.edu: linear time complexity
  2. cs.usfca.edu: tree rotations
  3. www-cs-faculty.stanford.edu: logarithmic time
  4. Wikipedia: Georgy Adelson-Velsky and Evgenii Landis
  5. Wikipedia: first self-balancing binary search tree
  6. Fibonacci trees
  7. ACM Digital Library
  8. ACM Digital Library
  9. ACM Digital Library
  10. Wikipedia: coloring scheme
  11. fewer rotations
  12. ACM Digital Library
  13. Wikipedia: WAVL tree
  14. ACM Digital Library
  15. Virtual Address Descriptor
  16. The Linux Kernel Archives
  17. Maple Tree
  18. C++ Standard Template Library
  19. Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, Sequential and Parallel Algorithms and Data Structures (Springer Nature, 2019)
  20. John O'Donnell, Cordelia Hall, Rex Page, Discrete Mathematics Using a Computer (Springer Science & Business Media, 2007)
  21. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Introduction To Algorithms (MIT Press, 2001)

Recommended reading