Trees & Balanced Search Trees

A tree is a hierarchy of nodes connected by parent-child edges. Its usefulness comes from paths: organizational containment, syntax nesting, file directories, spatial partitions, and search decisions all become walks through a hierarchy. A binary search tree (BST) adds key order so a comparison can discard one subtree. A balanced tree adds a shape discipline so that this path remains short even under hostile insertion order.

Tree vocabulary carries exact structural claims #

For a rooted tree:

• the root has no parent;
• every other node has exactly one parent;
• a leaf has no children;
• depth is edge distance from root to a node;
• height of a node is the longest downward edge path to a leaf;
• a subtree contains a node and all descendants;
• siblings share a parent.

A tree with $n$ nodes has $n-1$ parent-child edges. A structure with a reachable cycle or a node having two parents is not a tree under this model; it may be a graph or DAG and requires different traversal/lifetime reasoning.

Several representations preserve the same abstract hierarchy:

Ownership should follow the actual structure. Unique ownership from parent to child fits a tree. Parent pointers are then non-owning. Shared ownership in both directions creates cycles unless broken deliberately.

Traversal order is part of the algorithm #

For binary trees:

• preorder: node, left, right—useful for copying/prefix serialization;
• inorder: left, node, right—yields sorted keys for a BST;
• postorder: left, right, node—children are processed before teardown/aggregation;
• level order: breadth-first by a FIFO queue.

Each visits $n$ nodes in $O(n)$ time. Recursive depth-first traversal uses $O(h)$ call-stack space for tree height $h$; an explicit stack uses the same asymptotic auxiliary space while permitting depth limits and controlled failure. A queue for level order may hold the maximum width, potentially $\Theta(n)$.

template<class Node, class Visit>
void inorder(Node* root, Visit visit) {
    std::vector<Node*> stack;
    Node* current = root;
    while (current || !stack.empty()) {
        while (current) {
            stack.push_back(current);
            current = current->left;
        }
        current = stack.back();
        stack.pop_back();
        visit(*current);
        current = current->right;
    }
}

Traversal must also define mutation semantics. Deleting the current node during a traversal can invalidate the saved continuation. Snapshot, retain the next handle under a stable-handle contract, or use a container-provided erase iterator pattern.

A BST is an ordering invariant, not merely a binary tree #

With a strict weak ordering less, one common unique-key invariant is:

$$\forall x\in left(v):x.key < v.key, \qquad \forall y\in right(v):v.key < y.key.$$

Search compares the query with a node and chooses at most one child. Its time is $O(h)$, where $h$ is current height—not automatically $O(\log n)$. Sorted insertion into an unbalanced BST can create a chain of height $n-1$, degrading search, insertion, deletion, recursion depth, and destruction to linear behavior.

Duplicate policy belongs to the symbol-table contract. Options include rejection, replacement, a count/value collection inside one node, or a tie-breaker making occurrences distinct. “Put equals on the right” alone can interact badly with rotations unless the invariant and ordering make those elements distinguishable.

Inorder traversal proves a useful correspondence: if each left key precedes the node and the node precedes each right key, recursively concatenating inorder(left), node, inorder(right) yields sorted order.

Deletion has three structural cases #

To delete node z:

1. no child: remove its parent link;
2. one child: splice that child into z's position;
3. two children: replace the logical item with its inorder successor/predecessor, then remove that node, which has at most one child.

The third case is where identity contracts matter. Copying successor key/value into z preserves the node address but changes which logical record it holds. Transplanting the successor node preserves record identity but changes addresses/links differently. If clients retain node handles, specify which semantics are intended.

Augmented trees store metadata such as subtree size, interval maximum, or aggregate. Every insert, delete, and rotation must recompute it from changed children. With subtree size

$$size(v)=1+size(v.left)+size(v.right),$$

rank and select become $O(h)$. A correct BST with stale augmentation is still an incorrect order-statistics tree.

Rotations change shape without changing inorder order #

A left rotation around x promotes y=x.right; y's left subtree becomes x's right subtree, and x becomes y's left child. Before and after, the inorder blocks remain

$$A, x, B, y, C.$$

That preservation is why balancing algorithms can repair shape locally without breaking search order. The implementation must update the parent link, child links, optional parent pointers, root, and all augmentation/balance metadata. Rotation is $O(1)$ only because the number of rewritten links is bounded; finding the rotation point and propagating metadata can take $O(h)$.

Balanced and self-adjusting families make different promises #

Red-black color rules ensure no root-to-leaf path is more than twice another in the relevant black-height argument, bounding height by $O(\log n)$. The rules are the proof device; the client usually observes ordered operations and worst-case logarithmic complexity, not colors.

Splay trees carry no explicit balance field. Each access uses zig, zig-zig, or zig-zag rotations to move the accessed node to the root. Over a sequence, expensive operations are paid for amortized; a real-time request cannot assume every individual access is logarithmic.

Skip lists are not trees but solve the same ordered dictionary problem. The bottom level contains all keys; higher randomized levels provide express lanes. Expected height/search cost is logarithmic when promotions follow the intended independent distribution. Worst-case shape is linear, so adversarial latency requirements may prefer deterministic balancing.

For large on-disk or database indexes, binary branching wastes each block transfer. B-trees use high fanout so one page read rules out many key ranges; see External-Memory Algorithms & Data Structures.

Search trees are ordered indexes, not universal containers #

Choose an ordered tree when clients require lower/upper bounds, predecessor/successor, ordered iteration, or range queries under online updates. A hash table is often better for equality lookup without order. A sorted vector often wins for small or read-mostly data because binary search and scanning are contiguous. A trie can exploit shared string prefixes. A priority queue exposes only an extremum and is cheaper than promising the entire ordered-map interface.

Comparison cost matters. $O(\log n)$ node visits can compare long strings, perform locale collation, or call user code. The ordering must remain a strict weak ordering for all stored keys; mutating a key in place so its order changes corrupts the tree because physical position no longer matches comparison order.

Concurrency and lifetime complicate rotations #

A rotation atomically looks local only in a single-threaded model. Concurrent readers may observe combinations of old and new links unless protected by a lock, versioned optimistic protocol, copy-on-write snapshot, or a proven concurrent tree algorithm. Deletion additionally needs safe memory reclamation. Making child pointers atomic does not make multi-link invariants atomic.

State whether iterators observe a snapshot, hold locks, tolerate concurrent insertions, or are invalidated. A container can make individual find and insert linearizable while a range iteration still has no single-time snapshot.

Review and failure diagnostics #

1. Is the structure actually a tree—one root path per node and no cycle?
2. Are depth and height measured in edges or nodes consistently?
3. What exact duplicate policy does the comparator support?
4. Is claimed $O(\log n)$ worst-case, expected, or amortized—and which balancing rule proves it?
5. Can adversarial insertion create a chain or stack overflow?
6. Does deletion preserve logical identity and handle rules?
7. Does every rotation update root/parent links and augmentation metadata?
8. Can keys mutate while stored, invalidating ordering?
9. Does workload need ordered ranges, or would a flat/hash/prefix index fit better?
10. Are concurrent traversal and node reclamation covered by one coherent protocol?

Exercises #

1. Insert keys 1,2,3,4,5 into an unbalanced BST and state its height in edges.
2. Explain why a left rotation preserves the sorted inorder sequence.
3. With subtree sizes, describe how to find the key of zero-based rank $k$.