-
Hajipur, Bihar, 844101
Python AVL Trees
An AVL tree is a self-balancing binary search tree. It keeps the height difference between the left and right subtrees within a safe limit so that searching, inserting and deleting values always stay fast. A normal binary search tree can become unbalanced if too many values fall on one side. This causes slow lookups. AVL trees fix this by rotating nodes whenever the balance breaks. Because of this, AVL trees are widely used in databases, indexing systems, dictionaries and applications that need consistent performance.
In this tutorial, you will learn what an AVL tree is, how balancing works, how rotations fix imbalance, how to insert and delete values and how to write a complete AVL tree implementation in Python. You will also learn real-life uses and step-by-step examples that help build clarity.
What Is an AVL Tree?
An AVL tree is a binary search tree with an extra rule:
The height difference between the left and right subtrees of any node must be at most 1.
This height difference is called the balance factor:
Balance Factor = height(left subtree) - height(right subtree)
Valid balance factors are -1, 0 and 1.
If the balance goes outside this range, the tree rotates and fixes itself.
The name comes from its inventors: Adelson-Velsky and Landis.
Why Use AVL Trees?
AVL trees are helpful because they guarantee:
-
Predictable performance
-
O(log n) search time
-
Fast insertions and deletions
-
Automatic self-balancing
These trees are used in indexing, memory management and structured data systems.
Understanding Rotations
Rotations fix imbalance. There are four types:
1. Left Rotation
Used when the right subtree is too heavy.
2. Right Rotation
Used when the left subtree is too heavy.
3. Left-Right Rotation
When left child is right-heavy.
4. Right-Left Rotation
When right child is left-heavy.
These rotations restructure the tree while keeping the BST property intact.
Creating an AVL Tree Node in Python
Let’s start with a node structure:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1
Each node stores its value, references to children and its height.
Helper Functions: Height and Balance
def get_height(node):
if not node:
return 0
return node.height
def get_balance(node):
if not node:
return 0
return get_height(node.left) - get_height(node.right)
These functions help detect imbalances.
Rotation Functions
Right Rotation
def rotate_right(y):
x = y.left
temp = x.right
x.right = y
y.left = temp
y.height = 1 + max(get_height(y.left), get_height(y.right))
x.height = 1 + max(get_height(x.left), get_height(x.right))
return x
Left Rotation
def rotate_left(x):
y = x.right
temp = y.left
y.left = x
x.right = temp
x.height = 1 + max(get_height(x.left), get_height(x.right))
y.height = 1 + max(get_height(y.left), get_height(y.right))
return y
These operations keep the tree balanced.
Inserting Values in an AVL Tree
The insertion works like a normal BST. After inserting, you calculate the balance factor and apply the necessary rotation.
def insert(root, value):
if not root:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
root.height = 1 + max(get_height(root.left), get_height(root.right))
balance = get_balance(root)
# Left Left Case
if balance > 1 and value < root.left.value:
return rotate_right(root)
# Right Right Case
if balance < -1 and value > root.right.value:
return rotate_left(root)
# Left Right Case
if balance > 1 and value > root.left.value:
root.left = rotate_left(root.left)
return rotate_right(root)
# Right Left Case
if balance < -1 and value < root.right.value:
root.right = rotate_right(root.right)
return rotate_left(root)
return root
This ensures the AVL properties stay intact.
Deleting Values
Deletion also behaves like a normal BST. After removing the node, the tree checks for imbalance and rotates accordingly.
Here is a simple structure for deletion:
def find_min(node):
while node.left:
node = node.left
return node
def delete(root, value):
if not root:
return root
if value < root.value:
root.left = delete(root.left, value)
elif value > root.value:
root.right = delete(root.right, value)
else:
if not root.left:
return root.right
if not root.right:
return root.left
temp = find_min(root.right)
root.value = temp.value
root.right = delete(root.right, temp.value)
root.height = 1 + max(get_height(root.left), get_height(root.right))
balance = get_balance(root)
# Left Left Case
if balance > 1 and get_balance(root.left) >= 0:
return rotate_right(root)
# Left Right Case
if balance > 1 and get_balance(root.left) < 0:
root.left = rotate_left(root.left)
return rotate_right(root)
# Right Right Case
if balance < -1 and get_balance(root.right) <= 0:
return rotate_left(root)
# Right Left Case
if balance < -1 and get_balance(root.right) > 0:
root.right = rotate_right(root.right)
return rotate_left(root)
return root
Inorder Traversal (Sorted Output)
def inorder(node):
if node:
inorder(node.left)
print(node.value)
inorder(node.right)
AVL inorder traversal always gives sorted results.
Building an AVL Tree Example
root = None
values = [20, 4, 15, 70, 50, 80, 30]
for v in values:
root = insert(root, v)
inorder(root)
This builds a balanced tree regardless of insertion order.
Real-Life Uses of AVL Trees
Database Indexing
Fast and predictable access to records.
Memory Allocation
Balanced structures help manage free blocks.
Language Processing
Syntax trees remain well-structured.
Search Tools
Ordering and balancing help lookup speed.
Maps and Sets
Many dictionary-like structures use self-balancing trees.
AVL trees shine in systems where consistent fast performance is required.
Practical Examples
Example 1: Insert values
root = insert(None, 10)
Example 2: Insert multiple
for v in [5, 3, 8]:
root = insert(root, v)
Example 3: Delete a value
root = delete(root, 5)
Example 4: Print sorted output
inorder(root)
Example 5: Check height
print(root.height)
Example 6: Balanced after each insert
Try adding sorted numbers and see it stays balanced.
Example 7: Insert duplicates
AVL usually avoids duplicates manually.
Example 8: Large tree insert
for i in range(100):
root = insert(root, i)
Example 9: Rotate occurrences
Test cases where rotation happens.
Example 10: Visualize structure
Use traversal to understand balance.
Summary of the Tutorial
An AVL tree is a self-balancing BST that ensures the height difference between subtrees always stays within limits. This keeps searching, inserting and deleting operations fast and reliable. You learned how balance factors work, how rotations fix imbalance, how to insert and delete values and how to build a full AVL tree implementation in Python. AVL trees appear in databases, search systems and structured data tools where stable performance is important.
Practice Questions
Q1. Write a Python program to create an AVL Tree using values: 50, 30, 70, 20, 40.
Q2. Write a Python program to insert value 25 and check if the tree balances itself.
Q3. Write a Python program to perform and print Inorder traversal of the AVL Tree.
Q4. Write a Python program to modify your AVL Tree code to count the total number of nodes.
Q5. Write a Python program to display the balance factor of each node during insertions.
Q6. Write a Python program to perform a right rotation manually and print the updated tree.
Q7. Write a Python program to add print statements inside rotation functions to trace when and what type of rotation happens.
Q8. Write a Python program to delete a node from the AVL Tree and ensure it remains balanced.
Q9. Write a Python program to compare basic insertion time between an AVL Tree and a regular BST.
Q10. Write a Python program to count and print the number of leaf nodes in the AVL Tree.
