Self-Balancing Binary Search Trees

What You’ll Learn 📚

• Core concepts of self-balancing binary search trees
• Key terminology and definitions
• Simple and complex examples with code
• Common questions and answers
• Troubleshooting tips for common issues

Introduction to Self-Balancing Binary Search Trees

Binary Search Trees (BSTs) are a type of data structure that store ‘keys’ in a sorted manner. However, if the tree becomes unbalanced, it can degrade to a linked list in the worst case, making operations like search, insert, and delete inefficient. This is where self-balancing binary search trees come into play. They automatically adjust their structure to maintain balance, ensuring operations remain efficient.

Key Terminology

• Node: A basic unit of a tree containing a value, left child, and right child.
• Height: The number of edges on the longest path from the node to a leaf.
• Balance Factor: The difference in heights between the left and right subtrees.

Simple Example: AVL Tree

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

def insert(node, key):
    # Step 1: Perform the normal BST insert
    if not node:
        return Node(key)
    elif key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    # Step 2: Update the height of this ancestor node
    node.height = 1 + max(get_height(node.left), get_height(node.right))

    # Step 3: Get the balance factor
    balance = get_balance(node)

    # Step 4: If the node becomes unbalanced, then there are 4 cases

    # Left Left Case
    if balance > 1 and key < node.left.key:
        return right_rotate(node)

    # Right Right Case
    if balance < -1 and key > node.right.key:
        return left_rotate(node)

    # Left Right Case
    if balance > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)

    # Right Left Case
    if balance < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

Progressively Complex Examples

# Insert nodes into the AVL tree
root = None
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
    root = insert(root, key)

def delete_node(root, key):
    # Step 1: Perform standard BST delete
    if not root:
        return root
    elif key < root.key:
        root.left = delete_node(root.left, key)
    elif key > root.key:
        root.right = delete_node(root.right, key)
    else:
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp
        temp = get_min_value_node(root.right)
        root.key = temp.key
        root.right = delete_node(root.right, temp.key)

    # Step 2: Update the height of the current node
    if root is None:
        return root
    root.height = 1 + max(get_height(root.left), get_height(root.right))

    # Step 3: Get the balance factor
    balance = get_balance(root)

    # Step 4: If the node becomes unbalanced, then there are 4 cases

    # Left Left Case
    if balance > 1 and get_balance(root.left) >= 0:
        return right_rotate(root)

    # Left Right Case
    if balance > 1 and get_balance(root.left) < 0:
        root.left = left_rotate(root.left)
        return right_rotate(root)

    # Right Right Case
    if balance < -1 and get_balance(root.right) <= 0:
        return left_rotate(root)

    # Right Left Case
    if balance < -1 and get_balance(root.right) > 0:
        root.right = right_rotate(root.right)
        return left_rotate(root)

    return root

Common Questions and Answers

1. Why do we need self-balancing trees?

   Self-balancing trees ensure that operations like search, insert, and delete remain efficient, preventing the tree from becoming a linked list.

2. What is a balance factor?

   The balance factor is the difference in heights between the left and right subtrees of a node. It helps determine if a tree is balanced.

3. How do rotations work?

   Rotations are operations that change the structure of the tree to maintain balance. They involve rearranging nodes in a specific manner.

4. What are the types of rotations?

   There are four types of rotations: Left Rotation, Right Rotation, Left-Right Rotation, and Right-Left Rotation.

Troubleshooting Common Issues

If your tree is not balancing correctly, double-check your rotation logic. Ensure you're updating node heights and balance factors accurately.

Remember, practice makes perfect! Try inserting and deleting nodes manually to see how the tree adjusts.

Practice Exercises

• Implement a function to print the tree in-order and verify it's sorted.
• Try inserting a sequence of numbers and visualize the tree structure after each insertion.
• Delete nodes from the tree and observe how it rebalances.

For further reading, check out the Wikipedia page on self-balancing binary search trees and the GeeksforGeeks AVL Tree tutorial.