7. Trees and Balanced Search Structures

Introduction and Context

Linear structures such as arrays, linked lists, stacks, and queues organize data along a single sequence. Many important computing problems, however, involve hierarchy: file systems contain folders and subfolders, compilers represent expressions as syntax trees, databases organize indexes, and networks may be modeled through branching relationships. Trees provide the natural abstraction for such structures.

A tree is also a central search structure. An unordered collection may require linear examination to locate an item, whereas an appropriately organized tree can reduce search time substantially. The difficulty is that tree performance depends on shape. A binary search tree that remains approximately balanced offers logarithmic search, insertion, and deletion; a badly skewed tree degenerates into a linked list. Balanced search structures address this problem by preserving useful height bounds while maintaining dynamic updates.

This chapter develops binary trees, traversal algorithms, binary search trees, AVL trees, red-black tree concepts, B-trees, tries, and threaded trees. The emphasis is not merely on definitions, but on implementation decisions, invariants, complexity, and the relationship between memory-based and disk-oriented indexing.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Define trees and distinguish common structural terminology.

2. Represent binary trees in C and implement recursive and iterative traversals.

3. Construct, search, insert into, and delete nodes from a binary search tree.

4. Explain why imbalance harms performance and apply AVL rotations.

5. Describe the invariants and operational ideas of red-black trees.

6. Explain how B-trees support external-memory indexing.

7. Compare tries and threaded trees with conventional pointer-based trees.

8. Select a suitable tree structure for a practical application.

9. Analyze time, space, implementation, and maintenance trade-offs.

The Tree Abstraction

A tree is a connected, acyclic graph with a distinguished node called the root. Every node other than the root has exactly one parent and may have zero or more children. A node with no children is a leaf. The number of children of a node is its degree. The degree of a tree is the maximum node degree found in it.

The depth of a node is the number of edges on the path from the root to that node. The height of a node is the length of the longest downward path from that node to a leaf. The height of a tree is the height of its root. Some texts count nodes rather than edges; an implementation or algorithm should state its convention explicitly. A subtree consists of a node together with all of its descendants.

A binary tree is a tree in which each node has at most two children, conventionally called left and right. A full binary tree has either zero or two children at every node. A complete binary tree has every level completely filled except possibly the last, with the last level filled from left to right. A perfect binary tree has all internal nodes with two children and all leaves at the same depth. These terms describe different properties and should not be treated as synonyms.

A binary tree can be represented using linked nodes:

```c

typedef struct Node {

int key;

struct Node *left;

struct Node *right;

} Node;

```

The linked representation is flexible and is appropriate when the shape changes dynamically. An array representation is especially effective for complete trees, such as heaps. With zero-based indexing, the left and right children of node `i` are at `2i + 1` and `2i + 2`, respectively. For sparse or highly irregular trees, an array wastes space and is usually inferior to links.

Traversal as a Tree-Processing Framework

Traversal means visiting every node according to a specified order. The three classical depth-first traversals are defined recursively:

• Preorder: visit the node, then its left subtree, then its right subtree.
• Inorder: visit the left subtree, then the node, then the right subtree.
• Postorder: visit the left subtree, then the right subtree, then the node.

For a node `root`, the recursive algorithms are straightforward:

```c

void inorder(Node *root) {

if (root == NULL) return;

inorder(root->left);

printf("%d ", root->key);

inorder(root->right);

}

void preorder(Node *root) {

if (root == NULL) return;

printf("%d ", root->key);

preorder(root->left);

preorder(root->right);

}

void postorder(Node *root) {

if (root == NULL) return;

postorder(root->left);

postorder(root->right);

printf("%d ", root->key);

}

```

Inorder traversal has a particularly important property: when applied to a binary search tree, it produces keys in sorted order. Preorder is useful for copying or serializing a tree because a node is processed before its descendants. Postorder is useful for deleting a tree or evaluating expression trees because children are processed before their parent.

The recursive form uses the call stack and requires O(h) auxiliary space, where `h` is tree height. An iterative traversal replaces implicit recursion with an explicit stack. Level-order traversal, or breadth-first traversal, uses a queue and visits nodes level by level. It is useful for examining tree width, printing levels, and processing complete-tree layouts. All standard traversals visit each node once and therefore require O(n) time.

Binary Search Trees: Order as an Invariant

A binary search tree (BST) is a binary tree satisfying an ordering invariant. For every node with key `k`, all keys in the left subtree are less than `k`, and all keys in the right subtree are greater than `k`, assuming distinct keys. If duplicate keys are permitted, the policy must be explicit: duplicates may be stored consistently on one side, counted within a node, or rejected.

Search follows one path from the root. At each node, the target is either found, or comparison determines whether the search continues left or right:

```c

Node search(Node root, int key) {

while (root != NULL) {

if (key == root->key) return root;

root = (key < root->key) ? root->left : root->right;

}

return NULL;

}

```

Insertion uses the same comparisons and attaches a new leaf at the appropriate null link. Deletion has three cases. A leaf can be removed directly. A node with one child can be replaced by that child. A node with two children is replaced by its inorder successor—the smallest key in its right subtree—or by its inorder predecessor, followed by deletion of the replacement node from its original location.

The expected complexity of search, insertion, and deletion is O(log n) when the tree is reasonably balanced. The worst-case complexity is O(n). Inserting already sorted keys into an initially empty ordinary BST creates a chain, demonstrating that the ordering invariant alone does not guarantee efficient performance.

Maintaining Height: AVL Trees

An AVL tree is a self-balancing BST. For every node, the heights of its left and right subtrees differ by at most one. The balance factor is commonly defined as

`balance factor = height(left subtree) - height(right subtree)`.

A valid AVL node has a balance factor of −1, 0, or +1. After insertion or deletion, an imbalance may occur along the path back to the root. Rotations restore the invariant while preserving inorder key order.

A right rotation corrects a left-heavy configuration:

```c

Node rotateRight(Node y) {

Node *x = y->left;

Node *t = x->right;

x->right = y;

y->left = t;

return x;

}

```

A left rotation is the mirror image. Four structural cases are commonly identified:

1. LL case: a right rotation is required.

2. RR case: a left rotation is required.

3. LR case: rotate the left child left, then rotate the node right.

4. RL case: rotate the right child right, then rotate the node left.

Rotations change parent-child relationships but do not change the sorted inorder sequence. This is the essential reason they can repair shape without violating the BST property. AVL insertion requires at most a constant number of local rotations after the insertion path has been examined. Deletion may require rebalancing at several ancestors.

AVL trees provide tightly controlled height and are attractive when searches are substantially more frequent than updates. Their additional height fields, balance maintenance, and deletion logic increase implementation complexity. In C, height updates must occur after pointer changes and before balance decisions at higher ancestors; failing to do so is a common source of subtle errors.

Red-Black Trees: Flexible Balance Through Color

A red-black tree is another self-balancing BST. It stores one extra bit of structural information, conventionally represented as a color. A standard formulation uses these invariants:

1. Every node is red or black.

2. The root is black.

3. Null leaves, often represented by a sentinel, are black.

4. A red node cannot have a red child.

5. Every path from a node to a descendant null leaf contains the same number of black nodes.

The last quantity is called black height. These rules imply that the longest root-to-leaf path is no more than approximately twice the shortest, so the height remains O(log n). Unlike AVL trees, red-black trees permit somewhat more variation in height, often reducing the amount of restructuring during updates.

Insertion initially places a red leaf according to BST order. If its parent is black, the invariants remain valid. If its parent is red, recoloring and rotations are applied, with the uncle's color and the node's orientation determining the case. Deletion is more complicated because removing a black node can reduce the black count on one path. Fix-up procedures use sibling color, sibling-child colors, recoloring, and rotations.

The practical distinction is one of workload and engineering trade-off. AVL trees usually provide stricter height control and can be favorable for read-intensive workloads. Red-black trees generally tolerate updates with less frequent restructuring and are widely used in ordered maps, sets, schedulers, and library implementations. Both provide O(log n) worst-case search, insertion, and deletion; the choice should consider workload, library support, memory layout, and implementation risk rather than asymptotic notation alone.

B-Trees and External-Memory Indexing

Binary trees are not automatically suitable for storage systems. A disk or solid-state storage access transfers a block or page containing many bytes, and the cost of an operation is often dominated by the number of page transfers rather than by CPU comparisons. A B-tree addresses this issue by storing many keys and child pointers in one node, thereby reducing height and making each node align with a storage page.

A B-tree is a balanced multiway search tree. All leaves occur at the same depth. Internal nodes contain sorted separator keys and child pointers. If a node contains keys `k1, k2, ..., km`, its children represent ranges below `k1`, between successive keys, and above `km`. Minimum and maximum occupancy rules depend on the chosen order and convention. When a node overflows during insertion, it is split and a separator key is promoted to the parent. Deletion may borrow a key from a sibling or merge nodes when occupancy becomes too low.

A B+ tree is a closely related indexing structure in which records or record pointers are stored primarily in leaves, while internal nodes contain separators. Leaves are commonly linked, making range scans efficient. This organization is particularly useful for database indexes and file systems because it separates navigation from sequential retrieval.

The complexity of B-tree operations is O(log_m n) node visits for branching factor `m`, with each visit involving a small search among node keys. In practice, the important measure is often the number of page I/O operations. Increasing branching factor reduces tree height, but very large nodes may increase in-node search cost or complicate updates. B-tree design therefore links algorithmic structure with storage-engine page size, cache behavior, concurrency control, and recovery mechanisms.

Tries for String and Prefix Search

A trie, or prefix tree, organizes keys by their symbols rather than by comparisons between complete keys. A path from the root represents a prefix; a terminal marker indicates that the path corresponds to a complete key. For example, the words “car,” “card,” and “care” share the path for `c-a-r`.

If key length is `L`, lookup, insertion, and deletion can be O(L), independent of the number of stored keys, assuming constant-time access to the next child. This makes tries suitable for dictionaries, autocomplete, routing tables, spell checking, and prefix queries. Their disadvantage is memory consumption: a node may contain many child references, and sparse alphabets can waste space.

Implementations reduce this cost with linked child lists, sorted arrays, hash maps, compressed tries, or radix trees. A compressed trie combines chains of single-child nodes into labeled edges. The correct representation depends on alphabet size, key distribution, update frequency, and whether prefix queries dominate exact-match queries.

Threaded Trees and Traversal Without a Stack

In an ordinary binary tree, many child pointers are null. A threaded binary tree uses selected null pointers to store links to a node's inorder predecessor or successor. Tag fields distinguish a genuine child pointer from a thread. With successor threads, inorder traversal can proceed from one node to the next without recursion or an auxiliary stack.

Threading is useful when predictable traversal with very small auxiliary memory is important. It complicates insertion and deletion because threads must be repaired whenever local links change. Modern systems may prefer parent pointers, explicit stacks, or iterator abstractions, but threaded trees remain valuable for understanding how unused structural fields can support navigation.

Choosing a Structure: A Decision Perspective

The proper tree depends on the dominant operation and environment. A plain BST is simple and appropriate when inputs are controlled or when occasional imbalance is acceptable. An AVL tree is a strong choice for memory-resident, read-heavy ordered data requiring tight height bounds. A red-black tree is attractive for mixed workloads and general-purpose ordered dictionaries. A B-tree or B+ tree is preferable when data resides on storage pages or when range scans are important. A trie is natural for strings and prefix operations, while a threaded tree serves specialized traversal requirements.

The comparison should include more than big-O complexity. Important factors include key type, duplicate policy, memory overhead, cache locality, mutation frequency, range-query requirements, persistence, concurrency, implementation maturity, and failure recovery. A theoretically suitable tree can perform poorly if its pointer-heavy layout causes cache misses or if its balancing logic is unreliable.

Applied Case: Selecting an Index for a Digital Library

Background

Consider an illustrative university digital library containing millions of records. Each record has a numeric identifier, title, author names, subject tags, and publication metadata. Users perform exact identifier searches, title-prefix searches, and range queries by publication year.

Situation and Analysis

A plain BST would support ordered identifiers but could become skewed and would not naturally support prefix searches. An AVL or red-black tree could provide reliable in-memory lookup for a working set of frequently accessed records. However, the complete catalog exceeds main memory, so a pointer-based binary structure would generate excessive storage accesses. Title-prefix queries also require operations not naturally expressed by numeric ordering.

Approach

The system can use a B+ tree on record identifiers and publication years. Its leaves are linked, allowing efficient range scans. A separate trie or compressed trie can index normalized title prefixes. Frequently accessed upper B+ tree nodes and trie portions can be cached in memory. The implementation should define normalization rules for case, punctuation, and Unicode, and should ensure that index updates and catalog updates are transactionally consistent.

Outcome

The B+ tree reduces page visits for exact and range queries, while the trie supports autocomplete and prefix retrieval. A red-black or AVL tree may still be useful inside the application process for temporary ordered sets, but it is not the primary persistent index.

Learning Points

The case illustrates that no single tree is universally best. Storage hierarchy, query type, key representation, and update policy determine the appropriate design. It also shows why an index is a maintained data structure: every insertion, deletion, normalization rule, and recovery procedure affects correctness.

Implementation Risks and Professional Considerations

Tree programs frequently fail through incorrect pointer ownership, missing null checks, stale height values, inconsistent duplicate handling, and deletion cases that are tested only superficially. C adds risks involving memory leaks, double frees, dangling pointers, integer overflow in array indexing, and failure to check allocation results. A robust implementation should centralize node creation and destruction, document invariants, test empty and single-node trees, and validate sorted inorder output after updates.

Balancing metadata should be recomputed or updated systematically. Rotation functions should have clear preconditions and return the new subtree root. Tests should include increasing, decreasing, alternating, duplicate, and random insertion sequences, followed by deletion tests. Instrumentation can verify height bounds, balance factors, color rules, occupancy constraints, and trie terminal markers.

In database and file-system applications, indexing also raises governance and security concerns. Access-control decisions must not be bypassed through an index, and stale or inconsistent indexes can expose incorrect or unauthorized records. Persistent trees require crash recovery, atomic updates, corruption detection, and, in concurrent systems, appropriate latching or locking. Prefix indexes may reveal sensitive terms through autocomplete, so query authorization and information disclosure must be considered.

Current Directions

Contemporary tree implementations increasingly exploit cache-aware layouts, compressed representations, immutable or persistent versions, and concurrent update techniques. Database systems combine B+ trees with buffer managers, logging, and cost-based query optimization. Tries are being optimized through succinct bit-vector representations and adaptive radix structures. Hybrid indexes may combine ordered trees, hashing, and learned or workload-aware components, but such designs must preserve correctness under changing data and must be evaluated against baseline structures rather than assumed to be superior.

Best Practices for Tree-Based Programs

• State the ordering, duplicate, height, and null-pointer conventions before coding.
• Treat invariants as testable contracts, not informal assumptions.
• Keep rotations and node-management functions small and independently testable.
• Use inorder traversal to validate BST ordering.
• Measure height, memory usage, cache behavior, and update cost on representative workloads.
• Choose B-trees for page-oriented persistence and tries for prefix-oriented string operations.
• Separate structural indexing from authorization and business rules.
• Document ownership and destruction responsibilities in C.

Chapter Summary

Trees represent hierarchical data and support structured navigation. Binary-tree traversals provide reusable processing orders: preorder, inorder, postorder, and level order. A BST adds an ordering invariant, making search and updates efficient when its height is controlled. AVL trees enforce strict height balance through rotations, whereas red-black trees achieve logarithmic height through color invariants and more flexible restructuring. B-trees and B+ trees adapt search trees to block-based storage and range retrieval. Tries organize strings by prefixes, and threaded trees reuse null links for traversal. Effective selection depends on workload, storage medium, memory overhead, query type, and implementation reliability. In professional systems, invariants, testing, persistence, security, and recovery are as important as asymptotic complexity.

Key Terms

Tree: A connected acyclic structure with a designated root.

Root: The unique node with no parent.

Leaf: A node with no children.

Height: The length of the longest downward path from a node to a leaf.

Binary tree: A tree in which each node has at most two children.

Full binary tree: A binary tree whose nodes have either zero or two children.

Complete binary tree: A tree filled by levels, with the final level filled left to right.

Traversal: A systematic method of visiting tree nodes.

Binary search tree: A binary tree ordered so left keys precede and right keys follow a node key.

Balance factor: The difference between the heights of a node's left and right subtrees.

AVL tree: A BST whose balance factor at every node is −1, 0, or +1.

Rotation: A local pointer rearrangement that preserves inorder order.

Red-black tree: A colored BST satisfying color and black-height invariants.

Black height: The number of black nodes on a path to a null leaf under a red-black convention.

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

B+ tree: A B-tree variant that stores searchable records or pointers in linked leaves.

Trie: A prefix-based tree for strings or symbol sequences.

Threaded tree: A tree using selected null links as predecessor or successor threads.

Invariant: A property that must remain true throughout an algorithm or data structure's operation.

Review Questions

Short Answer Questions

1. Distinguish tree height from node depth.

2. Why does inorder traversal of a BST produce sorted keys?

3. What are the four imbalance cases in AVL insertion?

4. State two invariants of a red-black tree.

5. Why are B-tree nodes designed to contain multiple keys?

Long Answer Questions

1. Explain binary-tree representations and compare linked and array-based storage.

2. Describe BST deletion in all three structural cases and analyze its complexity.

3. Explain AVL rotations with suitable structural examples.

4. Compare AVL trees and red-black trees in terms of invariants, height, and update behavior.

5. Explain B-trees, B+ trees, node splitting, and their importance in external-memory indexing.

Analytical / Application Questions

1. A BST receives keys in increasing order. Analyze the resulting shape and recommend two suitable remedies.

2. Select an appropriate tree structure for an autocomplete service and justify the choice against AVL, red-black, and B-tree alternatives.

3. Design an indexing strategy for a persistent catalog supporting exact search, prefix search, and date-range queries. Explain the role of at least two different tree structures.

22. Multiple Choice Questions with Answers

Question 1

Which traversal of a binary search tree lists keys in nondecreasing order, assuming a consistent duplicate policy?

A. Preorder

B. Inorder

C. Postorder

D. Level-order

Correct Answer: B. Inorder

Question 2

A BST has a node with two children. Which replacement preserves the BST ordering most directly?

A. Any leaf in the tree

B. The root of the left subtree only

C. The inorder successor or predecessor

D. The deepest node in the right subtree

Correct Answer: C. The inorder successor or predecessor

Question 3

If an AVL node has balance factor +2 and its left child has balance factor −1, which correction is appropriate?

A. Single right rotation

B. Single left rotation

C. Left rotation on the left child followed by right rotation

D. Right rotation on the right child followed by left rotation

Correct Answer: C. Left rotation on the left child followed by right rotation

Question 4

Which property is required in a standard red-black tree?

A. Every leaf must be red

B. A red node may have a red child

C. All root-to-null paths contain the same number of black nodes

D. Every internal node must have exactly two non-null children

Correct Answer: C. All root-to-null paths contain the same number of black nodes

Question 5

Why is a B+ tree generally suitable for range queries?

A. It avoids storing separator keys

B. Its leaves can be linked for sequential scanning

C. It permits arbitrary imbalance

D. It stores every key only at the root

Correct Answer: B. Its leaves can be linked for sequential scanning

Question 6

A trie containing strings of maximum length L performs exact lookup primarily according to which quantity?

A. The number of tree nodes only

B. The height of a comparison BST

C. The key length L

D. The number of disk pages in a B-tree

Correct Answer: C. The key length L

Question 7

What is the main purpose of a threaded binary tree?

A. To guarantee AVL balance

B. To store multiple keys in each node

C. To use selected null links for navigation during traversal

D. To replace all leaves with sentinel colors

Correct Answer: C. To use selected null links for navigation during traversal

Question 8

Which sequence most clearly produces worst-case height in an ordinary unbalanced BST?

A. Randomly permuted distinct keys

B. Keys inserted in increasing order

C. Keys inserted in a balanced recursive order

D. Keys inserted by alternating minimum and maximum values

Correct Answer: B. Keys inserted in increasing order

Question 9

For a disk-resident catalog supporting range scans, which design is most appropriate?

A. A B+ tree with linked leaves

B. A plain linked list of records

C. A stack-based expression tree

D. A trie indexed only by the first character

Correct Answer: A. A B+ tree with linked leaves

Question 10

Which implementation practice best helps detect that a BST update has violated ordering?

A. Printing only the root key

B. Performing an inorder traversal and checking sorted order

C. Counting the number of recursive calls only

D. Checking whether every node has two children

Correct Answer: B. Performing an inorder traversal and checking sorted order