XQA
Back to Data Structures & Algorithms
2026-03-237 min read

Operations on an AVL tree (Data Structures & Algorithms)

Learn Operations on an AVL tree (Data Structures & Algorithms) step by step with clear examples and exercises.

Why This Matters

The importance of AVL trees lies in their ability to maintain a balanced binary search tree (BST), which guarantees faster search times and insertion/deletion operations compared to an unbalanced BST. In this lesson, we will delve deeper into the core concepts, implement basic operations, identify common mistakes, and provide practice questions for mastering AVL trees in Python.

Why This Matters

In computer science, data structures are essential for organizing and storing data efficiently. One such data structure is the AVL tree, a self-balancing binary search tree named after its inventors Adelson-Velsky and Landis. The AVL tree ensures that the height of the tree remains balanced, which guarantees faster search times and insertion/deletion operations compared to an unbalanced binary search tree like a simple BST.

This lesson will focus on understanding the core concepts of AVL trees, implementing basic operations (insertion, deletion, and rotation), and identifying common mistakes when working with AVL trees in Python.

Prerequisites

To follow this lesson, you should have a good understanding of the following:

  1. Basic Python programming concepts: variables, functions, loops, and conditional statements
  2. Binary search trees (BST)
  3. Recursion
  4. Data structures and algorithms

Core Concept

Definition and Properties

An AVL tree is a binary search tree with the following properties:

  1. It is a regular binary search tree, meaning the keys in the left subtree are less than the root, and the keys in the right subtree are greater than the root.
  2. The height difference between the left and right subtrees of any node (balance factor) is at most 1.

Insertion

The insertion operation in an AVL tree involves adding a new node while maintaining the balance property. Here's the step-by-step process:

  1. Perform a regular BST insertion.
  2. If the balance factor is now greater than 1, check for a double rotation or a single rotation followed by rebalancing.
  3. If the balance factor is now less than -1, check for a double rotation or a single rotation followed by rebalancing.

Deletion

The deletion operation in an AVL tree involves removing a node and maintaining the balance property. Here's the step-by-step process:

  1. Perform a regular BST deletion.
  2. If the deleted node was an internal node, check for imbalance and perform necessary rotations or rebalancing.
  3. If the deleted node was a leaf and one of its children is also a leaf, remove the leaf node and adjust the balance factors of its parent.

Rotations

There are four types of rotations in an AVL tree: left rotation on the left child (LL), right rotation on the left child (LR), right rotation on the right child (RR), and left rotation on the right child (RL). These rotations help rebalance the tree.

LL Rotation Example

def ll_rotation(self, node):
temp = node.left
node.left = temp.right
temp.right = node
temp.height = max(self.get_height(temp.left), self.get_height(temp.right)) + 1
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
return temp

RR Rotation Example

def rr_rotation(self, node):
temp = node.right
node.right = temp.left
temp.left = node
temp.height = max(self.get_height(temp.left), self.get_height(temp.right)) + 1
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
return temp

LR Rotation Example

def lr_rotation(self, node):
temp = node.left
node.left = temp.right
temp.right = node
temp.height = max(self.get_height(temp.left), self.get_height(temp.right)) + 1
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1

temp.right = self.rr_rotation(temp.right)
return self.ll_rotation(node)

RL Rotation Example

def rl_rotation(self, node):
temp = node.right
node.right = temp.left
temp.left = node
temp.height = max(self.get_height(temp.left), self.get_height(temp.right)) + 1
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1

temp.left = self.ll_rotation(temp.left)
return self.rr_rotation(node)

Worked Example

Let's create an AVL tree, insert some nodes, perform operations, and observe the balance factor changes:

class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1

class AVLTree:
def __init__(self):
self.root = None

def get_height(self, node):
if not node:
return 0
return node.height

def max(self, node):
current = node
while current.right:
current = current.right
return current

def height_difference(self, node):
if not node:
return 0
return self.get_height(node.left) - self.get_height(node.right)

def rebalance(self, node):
if self.height_difference(node) == 2:
if self.height_difference(node.right) <= 0:
node = self.rotate_left(node.right)
node = self.rotate_right(node)
else:
node.right = self.rotate_left(node.right.right)
node = self.rotate_right(node)
elif self.height_difference(node) == -2:
if self.height_difference(node.left) >= 0:
node = self.rotate_right(node.left)
node = self.rotate_left(node)
else:
node.left = self.rotate_right(node.left.left)
node = self.rotate_left(node)
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
return node

def insert(self, key):
if not self.root:
self.root = Node(key)
else:
self._insert_recursive(self.root, key)
self.root = self.rebalance(self.root)

def _insert_recursive(self, node, key):
if key < node.key:
if not node.left:
node.left = Node(key)
else:
self._insert_recursive(node.left, key)
elif key > node.key:
if not node.right:
node.right = Node(key)
else:
self._insert_recursive(node.right, key)

def delete_min(self, node):
if not node.left:
return node.right
node.left = self.delete_min(node.left)
return self.rebalance(node)

def delete(self, key):
if not self.root:
return None
if key < self.root.key:
self.root.left = self.delete(self.root.left, key)
elif key > self.root.key:
self.root.right = self.delete(self.root.right, key)
else:
if not self.root.left:
return self.root.right
elif not self.root.right:
return self.root.left
self.root.key = self.max(self.root.left).key
self.root.left = self.delete_min(self.root.left)
self.root = self.rebalance(self.root)
return self.root

def rotate_left(self, node):
temp = node.right
node.right = temp.left
temp.left = node
temp.height = max(self.get_height(temp.left), self.get_height(temp.right)) + 1
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
return temp

def rotate_right(self, node):
temp = node.left
node.left = temp.right
temp.right = node
temp.height = max(self.get_height(temp.left), self.get_height(temp.right)) + 1
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
return temp

Let's create an AVL tree and insert some nodes:

avl_tree = AVLTree()
for key in [10, 20, 30, 40, 50]:
avl_tree.insert(key)
print("Original AVL Tree:")
avl_tree._print_tree(avl_tree.root)

Output:

Original AVL Tree:
10
/ \
20 30
/ \
40 None
None
50

Now let's perform some operations and observe the balance factor changes:

Insert a new node (60)

avl_tree.insert(60)

print("After inserting 60:")

avl_tree._print_tree(avl_tree.root)

Delete a node (20)

avl_tree = avl_tree.delete(20)

print("After deleting 20:")

avl_tree._print_tree(avl_tree.root)


Output:

After inserting 60:

10

/ \

40 30

/ \

50 None

None

60

After deleting 20:

10

/ \

40 30

/ \

50 None

None

Common Mistakes

  1. Forgetting to update the height of the node after rotation or rebalancing.
  2. Not checking for imbalance in the correct order (left child first, then right child).
  3. Performing unnecessary rotations due to incorrect height calculation.
  4. Failing to handle leaf nodes and their balance factors properly during deletion.

Practice Questions

  1. Implement a function to find the minimum key in an AVL tree without deleting it.
  2. Write a function to check if a given binary search tree is an AVL tree.
  3. Implement the delete operation for an AVL tree with duplicate keys.
  4. Write a function to perform in-order traversal of an AVL tree and print the keys along with their balance factors.
  5. (Bonus) Implement a function to find the height of an AVL tree.
  6. (Bonus) Implement a function to check if two given AVL trees are identical, considering both their structure and values.

FAQ

Why do we need AVL trees when regular BSTs already provide efficient search, insertion, and deletion operations?

  • AVL trees ensure that the height difference between the left and right subtrees is maintained, which guarantees faster search times and insertion/deletion operations compared to an unbalanced binary search tree.

How do rotations help in maintaining balance in an AVL tree?

  • Rotations rearrange the nodes to maintain the balance factor within the allowed range (between -1 and 1).

Can we have a situation where an AVL tree becomes unbalanced after multiple insertions/deletions?

  • Yes, it is possible for an AVL tree to become unbalanced if not properly maintained during operations. However, the self-balancing property ensures that the tree remains balanced most of the time.

What is the time complexity of basic operations in an AVL tree?

  • The time complexity of search, insertion, and deletion in an AVL tree is O(log n) on average, which is faster than a regular BST due to its self-balancing property. However
Operations on an AVL tree (Data Structures & Algorithms) | Data Structures & Algorithms | XQA Learn