Overview
An AVL tree rotates after insertions or deletions so subtree heights differ by at most one, keeping lookups predictably logarithmic.
CoreSource checked
AVL Tree
Maintains a binary search tree with strict height balance after updates.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Balanced Search Tree
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
height balancetree rotationbinary search orderbalance factor
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log n)
Average
O(log n)
Worst
O(log n)
Space
O(n)
When to Use
- Use when fast lookup needs height balance.
- Use when the input matches the assumptions behind balanced Search Tree.
When Not to Use
- Avoid when the operation mix does not benefit from the structure's maintenance cost.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Maintains a binary search tree with strict height balance after updates
- Uses height balance and tree rotation to guide the work.
- Produces stored structure.
Use Cases
- Fast lookup
- Maintaining ordered data
- Representing graphs or spatial data
Inputs
- Items
- Keys or indexes
- Operations to support
Outputs
- Stored structure
- Query results
- Updated state
Key Formulas (1)
Balance factor
balance(v) = height(left(v)) − height(right(v))
balance(v) = height(left(v)) - height(right(v))Detects when a node needs rebalancing.
Pseudocode
- 1.Initialize the storage layout and invariants
- 2.For each update, locate the affected position or node
- 3.Modify pointers, counters, buckets, or summary values
- 4.Repair invariants such as balance, order, or load bounds
- 5.Answer queries from the maintained structure
Canonical Example
- Input
- AVL Tree
- Output
- Stored structure
- Explanation
- AVL Tree applies height balance to produce stored structure.
Implementation Notes
- Test insertion, deletion, lookup, and boundary cases separately.
- Keep the height balance step separate enough to test independently.
- Test updates and queries as sequences, not only one operation at a time.
Common Pitfalls
- Ignoring update costs can make a structure look faster than it is in practice.
- Test edge cases, not only clean examples.
- Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the structure layout and how operations move through or update it.
Step 1 of 5: Initialize the storage layout and invariants
data-structures-mechanismNotes
AVL Tree should be used with the assumptions and tradeoffs of balanced Search Tree in mind.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookAlgorithms textbook support for AVL Tree's invariant, correctness argument, and asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Variant ofBinary Search Tree
Data Structures · Foundation
AVL Tree is a data-structure variant of Binary Search Tree with different update or query tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toRed-Black Tree
AVL trees and red-black trees are balanced binary search trees with different rebalancing tradeoffs.
Variant ofBinary Search Tree
AVL Tree is a data-structure variant of Binary Search Tree with different update or query tradeoffs.
Related Algorithms
Tags
Data StructureTreeBalanced TreeTree Balancing