AVL Tree

An AVL Tree is a Binary Search Tree that is always balanced. Every node has a balance factor (height of left subtree - height of right subtree) of -1, 0, or 1. If the balance factor deviates from this, a rotation is performed.

Balance Factor

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

def balance_factor(node):
    if not node:
        return 0
    return height(node.left) - height(node.right)

Rotations

1. RR Rotation (left)

Occurs when the right subtree is too heavy.

    y                x
   / \             /   \
  A   x    =>     y     C
     / \         / \
    B   C       A   B

2. LL Rotation (right)

Occurs when the left subtree is too heavy.

      y              x
     / \           /   \
    x   C   =>    A     y
   / \                 / \
  A   B               B   C

3. LR Rotation

Left rotation on the left child, then right rotation.

4. RL Rotation

Right rotation on the right child, then left rotation.

Implementation

class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def insert(self, root, val):
        if not root:
            return AVLNode(val)
        if val < root.val:
            root.left = self.insert(root.left, val)
        elif val > root.val:
            root.right = self.insert(root.right, val)
        else:
            return root

        root.height = 1 + max(height(root.left), height(root.right))
        bf = balance_factor(root)

        # LL
        if bf > 1 and val < root.left.val:
            return self._right_rotate(root)
        # RR
        if bf < -1 and val > root.right.val:
            return self._left_rotate(root)
        # LR
        if bf > 1 and val > root.left.val:
            root.left = self._left_rotate(root.left)
            return self._right_rotate(root)
        # RL
        if bf < -1 and val < root.right.val:
            root.right = self._right_rotate(root.right)
            return self._left_rotate(root)

        return root

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

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

Why Are AVL Trees Important?

AVL Trees enforce a stricter balance than Red-Black Trees.