AVL Tree

How AVL Tree Works

An AVL tree is a self-balancing binary search tree where the height of the left and right subtrees of any node differ by at most one.

Key features:

• Maintains balance factor (BF) for each node: BF = height(left subtree) - height(right subtree)
• If |BF| > 1 after an insertion or deletion, the tree is rebalanced using rotations
• Ensures O(log n) time complexity for insertion, deletion, and search operations

Balancing operations:

• Left rotation: Used when the right subtree is higher
• Right rotation: Used when the left subtree is higher
• Left-Right rotation: Combination used for specific imbalance cases
• Right-Left rotation: Combination used for specific imbalance cases

AVL trees are useful in applications where frequent insertions and deletions occur, and maintaining a balanced tree is crucial for performance.

class Node:
    value
    left
    right
    height

class AVLTree:
    root

    function insert(value):
        root = insertRecursive(root, value)
        visualize()

    function insertRecursive(node, value):
        if node is null:
            return new Node(value)
        if value < node.value:
            node.left = insertRecursive(node.left, value)
        else if value > node.value:
            node.right = insertRecursive(node.right, value)
        else:
            return node

        node.height = 1 + max(height(node.left), height(node.right))
        balance = getBalance(node)

        // Left Left Case
        if balance > 1 and value < node.left.value:
            return rightRotate(node)

        // Right Right Case
        if balance < -1 and value > node.right.value:
            return leftRotate(node)

        // Left Right Case
        if balance > 1 and value > node.left.value:
            node.left = leftRotate(node.left)
            return rightRotate(node)

        // Right Left Case
        if balance < -1 and value < node.right.value:
            node.right = rightRotate(node.right)
            return leftRotate(node)

        return node

    function rightRotate(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

    function leftRotate(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