AVL Tree in Data Structure with Example

An AVL Tree (named after inventors Adelson-Velsky and Landis) is a self-balancing Binary Search Tree in which the height difference between the left and right subtrees of every node — called the balance factor — is at most 1.

Balance Factor

Balance Factor = height(left subtree) − height(right subtree). It must be -1, 0, or 1 for every node. If an insertion or deletion violates this, the tree performs rotations to restore balance.

Rotations

• Left Rotation: used when a node is right-heavy.
• Right Rotation: used when a node is left-heavy.
• Left-Right Rotation: a left rotation followed by a right rotation.
• Right-Left Rotation: a right rotation followed by a left rotation.

Worked Example

Inserting 10, 20, 30 in that order into an empty AVL tree causes a right-heavy imbalance at node 10 after inserting 30 (a 'Left-Left' case from the perspective of node 10 being unbalanced due to its right-right chain). The tree performs a single left rotation, making 20 the new root with 10 as its left child and 30 as its right child, restoring balance.

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

def height(node):
    return node.height if node else 0

def right_rotate(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = 1 + max(height(y.left), height(y.right))
    x.height = 1 + max(height(x.left), height(x.right))
    return x

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

Complexity

Applications

• Databases and file systems requiring guaranteed logarithmic lookup time.
• In-memory indexing structures.
• Situations with frequent insertions/deletions where balance must be maintained.