Write a program to simulate a self-balancing binary search tree (e.g.,…

A self-balancing binary search tree maintains its height automatically so that operations such as insertion, deletion, and searching remain efficient. One common example is an AVL tree, where the difference in height between left and right subtrees of any node is at most 1.

(a) Python program (AVL Tree insertion)

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

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

def rotate_right(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 rotate_left(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

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

def insert(node, key):
    if not node:
        return Node(key)

    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

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

    if balance > 1 and key < node.left.key:
        return rotate_right(node)
    if balance < -1 and key > node.right.key:
        return rotate_left(node)

    return node

(b) Performance evaluation with insertion order

If numbers are inserted in sorted order such as 1, 2, 3, 4, 5, a normal binary search tree becomes skewed and behaves like a linked list with time complexity O(n). However, an AVL tree automatically performs rotations to maintain balance, keeping the height close to log n.

For example, inserting 10, 20, 30 will trigger a rotation so that the tree becomes balanced with 20 as the root.

(c) Need for balancing in practical systems

Balancing is necessary because real systems handle large datasets where unbalanced trees degrade performance significantly. Self-balancing trees guarantee search, insertion, and deletion operations in O(log n) time. They are widely used in database indexing, file systems, and memory management because they maintain predictable performance regardless of the input order.