An AVL Tree is the first self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. If at any time they differ by more than one, rebalancing is done to restore this property.

How does an AVL Tree maintain its balance?

AVL trees maintain balance by performing 'rotations' after insertions or deletions that cause an imbalance. There are four types of rotations: Left rotation (LL), Right rotation (RR), Left-Right rotation (LR), and Right-Left rotation (RL). These rotations restructure the tree to restore the balance property while preserving the binary search tree property.

Data Structures

AVL Tree

The original self-balancing binary search tree, guaranteeing O(log n) time complexity for search, insert, and delete operations.

AVL Tree Rotations in Python

Implementing a full AVL tree is extensive. The core logic lies in the rotation functions that maintain balance. Below is a conceptual look at the right and left rotation helpers.

# Conceptual implementation of AVL Tree rotations

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

class AVLTree:
    # ... (getHeight, getBalance, etc.)

    def right_rotate(self, z):
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
        return y

    def left_rotate(self, z):
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right))
        y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
        return y

    # ... (insert, delete methods would use these rotations)

AI Coach Hint: In an interview, you should be prepared to draw the four rotation cases (LL, RR, LR, RL) on a whiteboard. Understanding visually how the nodes are rearranged is crucial to explaining the rebalancing process correctly.