Balanced Search Trees and Multiway Trees

Introduction

Search trees organize ordered keys so that search, insertion, and deletion can be performed more efficiently than in an unsorted collection. An ordinary binary search tree (BST) has expected logarithmic performance when its shape is reasonably balanced, but it can degenerate into a chain when keys arrive in sorted or nearly sorted order. Balanced search trees address this problem by maintaining structural invariants that limit height. Multiway trees extend the idea by allowing each node to contain several keys and children, making them especially suitable for external storage, databases, and file systems.

This chapter examines AVL trees, red-black trees, splay trees, treaps, B-trees, and B+ trees. The emphasis is not only on implementation, but also on choosing an appropriate structure for a workload. In-memory symbol tables, caches, schedulers, indexes, and disk-resident databases impose different requirements. A tree that is theoretically excellent for one workload may be inefficient for another.

Learning Objectives

After completing this chapter, a learner should be able to:

• explain the balancing invariant of major balanced and multiway trees;
• implement search, insertion, deletion, rotations, splitting, and merging operations;
• derive and compare worst-case, amortized, and expected complexity;
• select a tree for in-memory, database, storage, or indexing workloads;
• analyze practical issues including locality, concurrency, persistence, and failure recovery.

1. Foundations: Search-Tree Invariants

For a BST, every key in the left subtree of node x is less than x.key, and every key in the right subtree is greater, subject to the chosen duplicate-key policy. An in-order traversal therefore produces keys in sorted order. If the tree height is h, a search examines at most h + 1 nodes. A perfectly balanced tree with n nodes has height Θ(log n), whereas a chain has height Θ(n).

A balancing method adds an invariant that constrains h. The invariant may be deterministic, probabilistic, amortized, or based on node occupancy. The central operations are:

• Rotation: a local restructuring that preserves in-order key order.
• Recoloring: changing metadata colors in a red-black tree.
• Splaying: moving an accessed node toward the root.
• Priority repair: restoring heap order in a treap.
• Split and merge: changing the number of keys or children in a multiway node.

For a binary tree, a rotation changes parent-child relationships without changing the sorted sequence. A right rotation at y, where x is y’s left child, makes x the local root and moves x’s right subtree to become y’s left subtree. Left rotation is symmetric. Rotations take Θ(1) time and are the fundamental repair operation in AVL, red-black, and treap trees.

2. AVL Trees: Strict Height Balance

An AVL tree is a BST in which, for every node v, the height difference between its left and right subtrees is at most one. Define the balance factor as

Here height may be defined with an empty subtree of height −1 or 0; either convention is valid if used consistently. The AVL condition is BF(v) ∈ {−1, 0, 1}.

Height bound

Let N(h) be the minimum number of nodes in an AVL tree of height h, using empty-tree height −1. A minimum-height AVL tree consists of a root and minimum AVL subtrees of heights h − 1 and h − 2:

This Fibonacci-like recurrence implies N(h) grows exponentially in h, so h = O(log n). Thus search, insertion, and deletion are O(log n) in the worst case.

Rotations during insertion

Insertion first follows ordinary BST search. The new leaf has height zero. Moving upward, heights and balance factors are updated. If a node becomes unbalanced, one of four configurations occurs:

For example, inserting 30, 20, and 10 creates a left-left imbalance at 30. A right rotation makes 20 the local root, with 10 on its left and 30 on its right.

Deletion

Deletion uses ordinary BST deletion. Removing a node with two children normally replaces it by its in-order successor or predecessor. Unlike insertion, deletion may cause imbalance at several ancestors, so repairs can continue to the root. The worst-case time remains O(log n), but deletion generally requires more bookkeeping than insertion.

AVL trees provide tight height control and therefore excellent lookup performance. Their disadvantages are additional height or balance metadata and potentially more rotations during updates than red-black trees. They are attractive when searches substantially outnumber updates and predictable lookup latency matters.

3. Red-Black Trees: Relaxed Balance with Strong Guarantees

A red-black tree is a BST whose nodes are colored red or black. A common formulation uses these invariants:

1. Every node is red or black.
2. The root is black.
3. Every absent child, represented conceptually by a NIL leaf, is black.
4. A red node cannot have a red child.
5. Every path from a node to a descendant NIL leaf contains the same number of black nodes.

The number of black nodes on such a path is its black height. Because red nodes cannot be adjacent, no root-to-leaf path is more than twice as long as another of comparable black height. Consequently, the height is O(log n); more specifically, a red-black tree with n internal nodes has height at most 2 log₂(n + 1).

Insertion and deletion

A newly inserted node is initially red. This preserves black height, but may create a red-red violation with its parent. Repair uses recoloring and rotations. If the uncle is red, the parent and uncle become black and the grandparent becomes red, with repair continuing upward. If the uncle is black, a suitable single or double rotation followed by recoloring resolves the local violation.

Deletion is more complex. Removing a black node can reduce black height on one path, often described as a “double-black” condition. Cases involving a sibling’s color and the colors of the sibling’s children are resolved by recoloring and rotations.

Red-black trees guarantee O(log n) search, insertion, and deletion. Compared with AVL trees, they permit somewhat greater height but often require fewer rotations on update. Standard libraries frequently use red-black trees for ordered maps and sets because their performance is robust across mixed workloads.

4. Splay Trees: Adaptive and Amortized Balance

A splay tree is a self-adjusting BST with no explicit balance metadata. After searching for, inserting, or deleting a key, the accessed node is moved to the root by rotations. The three basic patterns are:

• Zig: one rotation when the node is a child of the root.
• Zig-zig: two rotations in the same direction when node and parent are both left or both right children.
• Zig-zag: two rotations in opposite directions.

A splay tree can have height Θ(n) at a particular instant. Nevertheless, a sequence of m operations on n items has amortized cost O(m log n), commonly expressed as O(log n) amortized time per operation. This does not mean that every individual operation is logarithmic.

Splaying exploits temporal locality. Repeatedly accessed keys move near the root, and recently accessed items tend to remain inexpensive to reach. The structure requires no balance factors or colors, which simplifies implementation. However, a single operation may cost linear time, and root changes can complicate concurrency and worst-case latency guarantees. Splay trees are useful for skewed access distributions, compiler structures, and adaptive caches, but less suitable for hard real-time systems.

5. Treaps: Randomized Cartesian Trees

A treap combines a BST ordering on keys with a heap ordering on independently assigned priorities. For a min-priority treap, each node satisfies:

• keys obey BST order;
• a node’s priority is no greater than its children’s priorities.

Insertion first follows BST order, assigns a random priority, and rotates the new node upward until heap order is restored. Deletion can rotate the target downward until it has at most one child, then remove it, or use split and merge operations.

With independent random priorities, the expected height is O(log n), and expected search, insertion, and deletion time is O(log n). These are expected bounds, not deterministic worst-case guarantees. Treaps are elegant and often easy to implement. They support useful operations such as split by key and merge of two appropriately ordered treaps. Their main limitation is dependence on randomness and the possibility, however unlikely, of poor shape.

6. Comparing Binary Balanced Trees

The complexity notation assumes pointer operations and comparison costs are constant. If keys are long strings, comparison itself may cost more than O(1), and the total cost must include that factor.

7. B-Trees: Multiway Search for External Storage

Binary trees are often inefficient on secondary storage because each pointer traversal may cause a page read. A B-tree reduces height by storing many sorted keys and child pointers in one node, usually sized to fit a disk or SSD page. A typical B-tree of minimum degree t satisfies:

• every node has at most 2t − 1 keys;
• every internal node has at most 2t children;
• every non-root node has at least t − 1 keys;
• each internal node with k keys has k + 1 children;
• all leaves occur at the same depth.

Some texts define order as the maximum number of children rather than minimum degree. Implementations must state which convention is being used.

For a B-tree with n keys and minimum degree t, the height is O(log_t n), where the logarithm base reflects the high branching factor. More precisely, for height h, the minimum number of keys is at least 2t^h − 1 under the standard definition and root exception. The practical significance is that a search may require only a small number of page accesses.

Search

Within a node, binary search or linear search locates the interval containing the target key. If the key is absent and the node is internal, the algorithm descends to the corresponding child. The CPU cost of searching a node and the I/O cost of fetching a child should be analyzed separately.

Insertion

A standard top-down insertion splits a full child before descending into it. Splitting a node with 2t − 1 keys promotes its median key to the parent and divides the remaining keys between two nodes. If the root is full, a new root is created first, increasing the height by one.

Deletion

Deletion must maintain minimum occupancy. Before descending into a child with only t − 1 keys, the algorithm either borrows a key from a sibling through the parent or merges the child with a sibling and a separator key from the parent. If the root becomes empty, its only child becomes the new root. These operations preserve sorted order, occupancy bounds, and equal leaf depth.

B-trees are suitable for database indexes, file-system metadata, and large sorted datasets. Node size, cache behavior, fill factor, and write amplification are often more important than asymptotic complexity.

8. B+ Trees: Leaf-Oriented Database Indexes

A B+ tree stores separator keys and child pointers in internal nodes, while records or record pointers reside only in leaves. Leaf nodes are linked in key order. Internal separator keys are routing information and may be repeated in leaves.

This design offers three important properties:

1. Internal nodes hold more routing entries because they do not store full records.
2. Every successful record lookup reaches a leaf at the same depth.
3. Range queries can traverse the leaf-level linked list after locating the first key.

For a range query returning r records, the I/O cost is approximately the cost of reaching the first leaf plus the leaf pages containing the range, assuming sequential leaf traversal and suitable caching. This is why B+ trees are standard for relational database indexes. A clustered B+ tree stores table records in leaf order; a secondary or nonclustered index stores references to records elsewhere.

B+ tree insertion may split a leaf and copy a separator into the parent. Internal-node splitting promotes a separator upward. Deletion may redistribute entries or merge underfull nodes. Database systems often use configurable minimum occupancy rather than enforcing the theoretical minimum rigidly after every operation, because deferred maintenance can reduce write cost.

9. Worked Comparison: Point and Range Workloads

Consider an index containing one million records. A binary tree with approximately 20 levels may require around 20 pointer traversals in a favorable balanced shape. A B+ tree with a page capacity of approximately 100 child references may require only a few page traversals because its effective branching factor is much larger. The exact height depends on key size, pointer size, occupancy, root structure, and page layout; therefore the comparison is conceptual rather than a claim about every implementation.

For a point lookup, both a balanced binary tree in memory and a B+ tree on storage can be logarithmic, but the dominant costs differ. In memory, cache misses and branch prediction matter. On storage, page reads and synchronization dominate. For a range query such as all keys between 500,000 and 510,000, a B+ tree is usually superior because it locates the first leaf and then follows linked leaves. A binary tree must repeatedly discover successors, causing less predictable memory access.

10. Implementation Principles

A robust implementation should separate structural logic from application payloads. Recommended practices include:

• define duplicate-key semantics explicitly: reject, count, store a list, or use a composite key;
• use assertions to check ordering, parent links, colors, balance factors, and occupancy;
• centralize rotations and pointer updates;
• update metadata after every structural change;
• test adversarial sequences, including sorted, reverse-sorted, repeated, and random keys;
• measure actual workload behavior rather than relying solely on asymptotic notation.

For B-trees and B+ trees, node serialization, page identifiers, checksums, logging, and crash recovery are part of correctness. A tree that is structurally valid in memory may still be unsafe if a power failure leaves a parent updated but a split child unwritten. Database implementations therefore use write-ahead logging, shadow paging, or transactional page protocols.

11. Applied Case: An Illustrative Database Index Selection

Background

An online retail platform maintains 200 million orders. Users frequently search by order identifier, while analysts issue date-range queries and occasionally filter by customer identifier. The index must support concurrent updates and recovery after failures.

Problem

A binary AVL index in main memory would provide predictable lookup time, but it cannot economically hold the complete dataset and would require expensive reconstruction after failure. A splay tree might benefit from repeated popular orders but offers poor control over individual operation latency. A treap would be simple but would not directly solve page-oriented storage.

Analysis

The workload has both point and range queries, and the dataset is much larger than memory. The relevant performance unit is a page access rather than a pointer comparison. Range queries benefit from ordered leaves, while concurrent database operations require latching and recovery protocols.

Approach and solution

The platform uses a B+ tree on order date for range analytics and a separate B+ tree on order identifier for point lookup. Leaf entries contain either the full row for a clustered index or a record identifier for a secondary index. Leaf pages are linked in key order. A buffer manager caches frequently accessed pages, and write-ahead logging protects structural changes. Page splits are performed using short-duration latches, while higher-level transaction isolation is handled separately.

Outcome

Point queries traverse a small number of index pages, and date ranges scan consecutive leaf pages rather than repeatedly traversing from the root. The design scales with storage capacity and supports recovery. Its cost is additional storage, maintenance for multiple indexes, and write overhead during page splits.

Learning points

The best structure depends on the access medium and workload. Theoretical O(log n) bounds do not reveal whether the dominant operation is a CPU comparison, a cache miss, or a storage-page read. Indexes should therefore be selected using workload traces, page-layout estimates, concurrency requirements, and recovery constraints.

12. Limitations, Governance, and Contemporary Directions

Balanced trees do not eliminate all performance problems. Highly concurrent updates can create contention near roots or frequently modified pages. Poor key distribution may cause hot spots, and secondary indexes increase write amplification. Variable-length keys reduce fan-out, while compression can improve capacity but increase CPU cost.

In AI and ML systems, trees are used for feature dictionaries, ordered event stores, model metadata, nearest-neighbor variants, and database-backed training pipelines. They should not be confused with decision trees, whose purpose is prediction rather than ordered indexing. Data structures can also affect governance: an index may expose sensitive ordering or membership information, and retained index pages may persist data after an application-level deletion. Access control, encryption at rest, retention policies, audit logging, and verified deletion procedures are therefore relevant in regulated environments.

Modern systems increasingly combine tree indexes with memory hierarchies, compression, learned cost models, and log-structured storage. Bε-trees and related buffered trees reduce update cost by batching messages; cache-oblivious trees seek good performance across unknown memory-block sizes; concurrent B-link trees add sibling links to support safe structural changes. These developments do not replace classical invariants. They extend them to address parallelism, write cost, and multi-level storage.

Best-Practice Selection Guide

• Choose AVL when strict height control and lookup latency are more important than update simplicity.
• Choose red-black for a dependable general-purpose ordered map with mixed updates and queries.
• Choose splay when access locality is strong and amortized performance is acceptable.
• Choose treap when a compact randomized implementation and expected logarithmic height are appropriate.
• Choose B-tree when records and navigation must be organized in page-sized multiway nodes.
• Choose B+ tree for database-style indexes, especially when efficient ordered range scans are required.

Chapter Summary

Balanced search trees preserve efficient ordered access by constraining tree shape. AVL trees enforce strict local height balance; red-black trees use colors and black-height equality to obtain logarithmic worst-case operations with relatively modest update repair. Splay trees obtain logarithmic amortized performance through self-adjustment and exploit temporal locality, while treaps obtain logarithmic expected performance from random priorities.

B-trees and B+ trees reduce external-storage cost through high fan-out and page-sized nodes. B+ trees place records or record references in linked leaves, making them particularly effective for range queries and database indexes. Correct selection requires analysis of point versus range access, update frequency, memory hierarchy, concurrency, recovery, and security. Asymptotic bounds remain essential, but practical performance also depends on cache misses, page occupancy, key size, logging, and workload distribution.

Key Terms

Balanced search tree: A search tree whose height is constrained by a structural invariant.

AVL tree: A BST whose subtree-height difference at every node is at most one.

Balance factor: The height of a node’s left subtree minus the height of its right subtree.

Rotation: A local pointer restructuring that preserves in-order key order.

Red-black tree: A colored BST satisfying red-node and equal-black-height invariants.

Black height: The number of black nodes on a path to a NIL leaf.

Splay tree: A self-adjusting BST that moves accessed nodes toward the root.

Amortized analysis: Analysis of average cost over a sequence of operations.

Treap: A randomized structure satisfying both BST order and heap priority order.

Priority: The random heap key used by a treap.

Multiway tree: A tree whose node may have several keys and children.

B-tree: A balanced multiway search tree designed for block or page storage.

Minimum degree: The parameter governing the minimum and maximum occupancy of B-tree nodes.

B+ tree: A leaf-oriented multiway index with linked leaves.

Fan-out: The number of child references that a node can contain.

Page split: Division of a full storage node into multiple nodes.

Redistribution: Moving entries between neighboring nodes through their parent.

Write amplification: Extra physical writing caused by logical updates.

Temporal locality: The tendency for recently accessed items to be accessed again.

Write-ahead logging: Recording recovery information before writing corresponding data pages.

Review Questions

Short Answer Questions

1. What property makes a BST balanced in the AVL sense?
2. Why can a red-black tree contain red nodes but not adjacent red nodes?
3. What is the purpose of splaying an accessed node?
4. State one major difference between a B-tree and a B+ tree.
5. Why are B+ trees effective for range queries?

Long Answer Questions

1. Explain AVL insertion and the four rotation cases, including why rotations preserve sorted order.
2. Describe red-black insertion and explain how recoloring and rotations restore the invariants.
3. Compare worst-case, amortized, and expected complexity for AVL, red-black, splay, and treap trees.
4. Explain B-tree insertion and deletion, including splitting, borrowing, and merging.
5. Discuss how page size, fan-out, occupancy, and linked leaves influence database-index performance.

Analytical / Application Questions

1. A workload has strict per-operation latency requirements and frequent updates. Compare AVL, red-black, splay, and treap trees and justify a selection.
2. Design indexes for a database that performs both exact order-ID lookups and date-range scans. Explain the role of clustered and secondary B+ trees.
3. An index experiences frequent page splits and write contention. Propose diagnostic measurements and at least three structural or operational remedies.

Multiple Choice Questions with Answers

Question 1

Which AVL condition must hold at every node?

A. The two subtree heights differ by at most one

B. Every path contains the same number of red nodes

C. Every node has exactly two children

D. Priorities increase from root to leaf

Correct Answer: A. The two subtree heights differ by at most one

Question 2

What is the worst-case height bound of a red-black tree with n internal nodes?

A. Θ(1)

B. O(log n)

C. O(√n)

D. Θ(n)

Correct Answer: B. O(log n)

Question 3

Which operation is characteristic of a splay tree?

A. Splitting every full page before descent

B. Moving an accessed node toward the root

C. Assigning equal black height to every node

D. Maintaining two children at every leaf

Correct Answer: B. Moving an accessed node toward the root

Question 4

A treap combines which two ordering properties?

A. BST key order and heap priority order

B. AVL height order and color order

C. Page order and insertion-time order

D. Hash order and FIFO order

Correct Answer: A. BST key order and heap priority order

Question 5

In a standard B-tree of minimum degree t, what is the maximum number of keys in a non-root node?

A. t − 1

B. t

C. 2t − 1

D. 2t

Correct Answer: C. 2t − 1

Question 6

Where are records or record pointers normally stored in a B+ tree?

A. Only in the root

B. Only in internal nodes

C. In every internal node and leaf

D. In the leaf nodes

Correct Answer: D. In the leaf nodes

Question 7

Why do B-trees reduce storage I/O compared with pointer-rich binary trees?

A. They avoid sorting keys

B. They store many keys and child references per page

C. They guarantee zero page writes

D. They use no pointers

Correct Answer: B. They store many keys and child references per page

Question 8

Which tree is especially suited to range scans because its leaves are linked in key order?

A. B+ tree

B. Treap

C. Splay tree

D. AVL tree

Correct Answer: A. B+ tree

Question 9

What is the complexity guarantee commonly associated with a sequence of m splay-tree operations on n items?

A. O(mn) amortized

B. O(m) worst-case for all sequences

C. O(m log n) amortized

D. O(log m) regardless of n

Correct Answer: C. O(m log n) amortized

Question 10

Which repair is associated with an AVL left-left imbalance?

A. Left rotation at the unbalanced node

B. Right rotation at the unbalanced node

C. Recoloring the sibling red

D. Merging two B-tree pages

Correct Answer: B. Right rotation at the unbalanced node