Trees and ordered maps

Use a tree to represent nested folders. Add search order when you need to find keys, predecessors, or ranges efficiently.

Separate shape from order

A rooted tree has one root. Every other node has exactly one parent, and following child links never forms a cycle. A binary tree allows at most two children per node. Neither definition says how values are ordered.

A binary search tree, or BST, adds an ordering invariant. In this example, every key in a node's left subtree is smaller, and every key in its right subtree is larger. Duplicate map keys replace values; a set keeps one copy.

          8
        /   \
       3     12
      / \    /
     1   6  10

lookup 6: 8 -> left to 3 -> right to 6
insert 5: 8 -> 3 -> 6 -> new left child 5

The invariant applies to whole subtrees, not just immediate children. Putting 9 under node 6 would break the rule at root 8.

An in-order traversal visits left subtree, node, then right subtree. It yields sorted keys. A general tree can instead use pre-order to visit parents first, post-order to visit children first, or BFS to visit by level.

Trace deletion

Delete a leaf by clearing its parent's link. Delete a node with one child by connecting its parent directly to that child.

For two children, replace the node's key and value with its successor: the smallest key in its right subtree. Then delete that successor from its original position. It has no left child, so that second deletion is simpler.

In the original diagram, deleting 8 replaces it with 10. Then remove the old leaf 10 under 12. The remaining keys still satisfy the subtree bounds.

Balance determines the cost

A BST operation follows a path of height h, so search, insertion, and deletion take O(h). Sorted insertion into an ordinary BST can create a chain of n nodes. That makes each operation O(n) in the worst case.

A balanced BST maintains height O(log n). AVL trees limit the difference between child heights. Red-black trees use color rules to limit path lengths. Both repair updates using local rotations and bookkeeping.

Right rotation at 8:
        8                  3
       / \                / \
      3   C     ->       A   8
     / \                    / \
    A   B                  B   C

In-order stays: A, 3, B, 8, C

A rotation changes shape while preserving sorted order. Balance rules decide when rotations are necessary; rotations alone do not guarantee balance.

An ordered set stores unique keys in sorted order. An ordered map associates each key with a value. Balanced search trees are common implementations. Hash sets and hash maps instead prioritize equality lookup and do not inherently support sorted ranges.

Predict and modify

1. Insert 1, 2, 3, 4 into an ordinary BST. What is its shape?
2. Why must deletion copy a successor's value as well as its key in a map?
3. Replace ordered with a helper that appends into one result list.

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


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


def contains(root, key):
    while root is not None:
        if key == root.key:
            return True
        root = root.left if key < root.key else root.right
    return False


def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        successor = root.right
        while successor.left is not None:
            successor = successor.left
        root.key = successor.key
        root.right = delete(root.right, successor.key)
    return root


def ordered(root):
    if root is None:
        return []
    return ordered(root.left) + [root.key] + ordered(root.right)


root = None
for key in [8, 3, 12, 1, 6, 10]:
    root = insert(root, key)
root = insert(root, 5)
assert contains(root, 5) and not contains(root, 7)
for key in [8, 1, 12, 3, 5, 6, 10]:
    root = delete(root, key)
    assert not contains(root, key)
assert root is None
root = insert(insert(None, 4), 4)
assert ordered(root) == [4]

Apply the ordering invariant in Validate Binary Search Tree.

Next: B-trees and B+ trees, then heaps.