Balanced Trees: AVL & Red-Black Trees

Balanced trees maintain a balanced height to ensure operations like insertion, deletion, and search are efficient (O(log n)). The two popular balanced trees are AVL trees and Red-Black trees.

AVL Trees

AVL trees are self-balancing binary search trees where the balance factor (difference between heights of left and right subtrees) of any node is at most 1.

Operations

• Insertion & Deletion: May cause imbalance, fixed by tree rotations.
• Rotations: Left rotation, Right rotation, Left-Right rotation, Right-Left rotation to maintain balance.

Python Example: AVL Tree Insertion

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

class AVLTree:
    def getHeight(self, root):
        if not root:
            return 0
        return root.height

    def getBalance(self, root):
        if not root:
            return 0
        return self.getHeight(root.left) - self.getHeight(root.right)

    def rightRotate(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 leftRotate(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

    def insert(self, root, key):
        if not root:
            return TreeNode(key)
        elif key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))

        balance = self.getBalance(root)

        # Left Left
        if balance > 1 and key < root.left.key:
            return self.rightRotate(root)

        # Right Right
        if balance < -1 and key > root.right.key:
            return self.leftRotate(root)

        # Left Right
        if balance > 1 and key > root.left.key:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)

        # Right Left
        if balance < -1 and key < root.right.key:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)

        return root

Red-Black Trees

Red-Black trees are binary search trees with an extra color attribute for each node: red or black. They ensure the tree remains approximately balanced through color properties and rotations.

Properties

• Every node is red or black.
• The root is always black.
• Red nodes cannot have red children (no two reds in a row).
• Every path from root to NULL has the same number of black nodes.
• Insertion and deletion maintain these properties using rotations and recoloring.

Use Cases

• Used in OS kernel, databases, and filesystems for efficient searching and balancing.
• Faster insertion and deletion compared to AVL trees in some scenarios.

Red-Black trees are more complex to implement but provide great performance in general balanced tree use cases.