XQA
Back to Data Structures & Algorithms
2026-04-246 min read

Rotating the subtrees in an AVL Tree

Learn Rotating the subtrees in an AVL Tree step by step with clear examples and exercises.

Title: Rotating Subtrees in an AVL Tree - A Comprehensive Python Example

Why This Matters

In data structures and algorithms, AVL (Adelson-Velsky and Landis) trees are self-balancing binary search trees that maintain their height balanced to ensure efficient operations. One of the key operations in AVL trees is rotating subtrees to rebalance the tree after insertion or deletion. Understanding this concept is crucial for cracking coding interviews and solving real-world programming problems.

By rotating subtrees, we can keep the height difference between the left and right subtrees of a node within a specific range ([-1, 1]), which ensures that the tree remains balanced and allows for efficient search, insertion, and deletion operations.

Prerequisites

Before diving into rotating subtrees, you should have a good understanding of the following:

  1. Basic Python syntax and data structures (lists, tuples, dictionaries)
  2. Recursion in Python
  3. Binary search trees
  4. AVL tree basics (height balance factor, insertion, deletion)
  5. Familiarity with Python's built-in collections.defaultdict for storing heights of nodes
  6. Understanding the concept of recursive depth in binary trees

Core Concept

In an AVL tree, the height of each node is stored, and the balance factor (BF) for each node is calculated as the difference between the heights of its left and right subtrees. If a node's BF is outside the range [-1, 1], the tree needs to be rebalanced by rotating its subtrees.

There are four types of rotations in an AVL tree: Left Rotation (LL), Right Rotation (RR), Left-Right Rotation (LR), and Right-Left Rotation (RL). Each rotation aims to rebalance the tree while preserving the order of the nodes and their relationships.

Balance Factor Calculation

The balance factor (BF) for a node is calculated as follows:

def get_balance_factor(node):
if node:
return height(node.left) - height(node.right)
else:
return 0

Height Calculation

The height of a node is the number of edges from the root to that node, including itself.

def height(node):
if not node:
return -1
else:
return node.height + 1

Recursive Depth

The recursive depth (RD) of a node is the number of edges from the root to that node, excluding itself.

def get_recursive_depth(node):
if not node:
return -1
else:
return height(node) - 1

Worked Example

Let's consider the following AVL tree implementation:

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

Recursive depth of the current node

self.recursive_depth = -1

def height(node):

if not node:

return -1

else:

return node.height

def get_balance_factor(node):

if node:

return height(node.left) - height(node.right)

else:

return 0

class AVLTree:

def __init__(self, root=None):

self.root = root

Perform left rotation

def rotate_left(self, node):

pass

Perform right rotation

def rotate_right(self, node):

pass

Perform left-right rotation

def rotate_left_right(self, node):

pass

Perform right-left rotation

def rotate_right_left(self, node):

pass

Common Mistakes

  1. Forgetting to update heights and recursive depths after rotations: Remember to update the height and recursive depth of the rotated node as well as its ancestors that might have been affected by the rotation.
  2. Incorrect calculation of balance factor: Ensure you calculate the balance factor correctly, taking into account the heights of both subtrees.
  3. Not handling multiple rotations in a row: Sometimes, one rotation leads to another. Make sure to handle such cases correctly.
  4. Neglecting to check for rebalancing after insertion or deletion: Always remember to check if rebalancing is required after performing an insertion or deletion operation.
  5. Assuming that all rotations are symmetric: While left and right rotations have similar structures, LR and RL rotations differ in their implementation.
  6. Implementing rotations without understanding the underlying logic: Make sure to understand why each rotation is necessary and how it affects the tree's balance.
  7. Not considering the recursive depth when calculating the balance factor: The recursive depth of a node can affect its balance factor, so it should be taken into account during calculations.

Practice Questions

  1. Implement the four types of rotations (LL, RR, LR, and RL) in an AVL tree using Python.
  2. Write a function to insert a node into an AVL tree and maintain balance after each insertion.
  3. Write a function to delete a node from an AVL tree and rebalance the tree if necessary.
  4. Implement a function to find the height of the AVL tree.
  5. Implement a function to check if an given binary search tree is an AVL tree.
  6. Implement a function to find the number of nodes in an AVL tree.
  7. Implement a function to find the minimum and maximum values in an AVL tree.
  8. Implement a function to perform an in-order traversal of an AVL tree.
  9. Write a test case that demonstrates rebalancing after inserting multiple nodes.
  10. Write a test case that demonstrates rebalancing after deleting multiple nodes.

FAQ

Q: Why is it important to keep the height balanced in an AVL tree?

A: Maintaining a balanced AVL tree ensures that all operations (insertion, deletion, search) have logarithmic complexity, making the tree more efficient for large datasets.

Q: Can I use other data structures instead of AVL trees to maintain balance in a binary search tree?

A: Yes, other self-balancing binary search trees like Red-Black Trees and Splay Trees can also be used to maintain balance in a binary search tree. However, AVL trees are simpler and more efficient for small datasets.

Q: What is the time complexity of insertion and deletion operations in an AVL tree?

A: The average time complexity of insertion and deletion operations in an AVL tree is O(log n).

Q: How does the height of a node affect its balance factor?

A: The balance factor of a node is calculated as the difference between the heights of its left and right subtrees. If the height of the left subtree is greater than the height of the right subtree, the balance factor will be positive. Conversely, if the height of the right subtree is greater than the height of the left subtree, the balance factor will be negative.

Q: How does an AVL tree handle a node with a balance factor greater than 1?

A: When a node has a balance factor greater than 1 (i.e., its left subtree is taller), the tree may need to perform a left rotation or a combination of rotations to rebalance it. The specific rotation depends on the height and balance factors of the involved nodes.

Q: How does an AVL tree handle a node with a balance factor less than -1?

A: When a node has a balance factor less than -1 (i.e., its right subtree is taller), the tree may need to perform a right rotation or a combination of rotations to rebalance it. The specific rotation depends on the height and balance factors of the involved nodes.

Q: Why do we use recursive depth in AVL trees?

A: Recursive depth helps us determine the number of rotations needed to reach a particular node from the root, which is essential for implementing some types of rotations like LR and RL.

Q: What are the advantages of using AVL trees over other self-balancing binary search trees?

A: AVL trees have simpler rotation rules compared to Red-Black Trees and Splay Trees, making them more efficient for small datasets. However, they may not be as efficient for very large datasets due to their height-based balancing strategy.

Rotating the subtrees in an AVL Tree | Data Structures & Algorithms | XQA Learn