11Module · Goodrich Ch. 11.1–11.3

Week 11 — Search Trees I

Binary search trees, the balanced-tree framework, AVL trees and rotations.

BST search/insert/delete, why height matters, and AVL self-balancing via rotations.

Theory

A binary search tree maintains the invariant: for every node, all keys in the left subtree are smaller and all keys in the right subtree are larger.

Search/insert/delete on a BST run in O(h) where h is the tree height — Θ(n) in the worst case for a skewed tree.

AVL trees enforce |height(left) − height(right)| ≤ 1 at every node, guaranteeing h = O(log n).

Rotations (single and double) restore balance in O(1) after insert or delete.

Key points

Inorder traversal of any BST returns sorted keys.
AVL rebalancing cost per update is O(log n).
Successor on delete = leftmost node of right subtree.

Code examples

BST insert and search

class BSTNode:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

def insert(root, key):
    if root is None:
        return BSTNode(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root

def search(root, key):
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    return search(root.right, key)

AVL right rotation

def rotate_right(y):
    x = y.left
    t2 = x.right
    x.right = y
    y.left = t2
    update_height(y)
    update_height(x)
    return x  # new subtree root