Trees and Hierarchical Data Structures

Introduction and Context

Many information systems organize data hierarchically rather than linearly. File systems contain directories and subdirectories; databases maintain indexes; programming-language tools represent expressions as syntax trees; and search interfaces arrange possible completions by shared prefixes. Trees provide the abstract data structure for these relationships.

A tree is a connected, acyclic structure composed of nodes and edges. Unlike a general graph, a tree has a unique path between any two nodes. Its hierarchical organization supports efficient searching, insertion, deletion, sorting, classification, and representation of nested information. However, efficiency depends strongly on shape. A balanced search tree can support operations in logarithmic time, whereas a highly skewed tree may behave like a linked list.

This chapter develops binary trees, traversal algorithms, binary search trees, AVL trees, red-black trees, multiway trees, B+ trees, and tries. It also examines their use in indexing, file systems, databases, autocomplete, and AI-related systems.

Learning Objectives

By the end of this chapter, you should be able to:

1. Define tree terminology and analyze structural properties.

2. Construct and traverse binary trees using standard algorithms.

3. Implement and analyze binary search trees.

4. Explain why balancing is necessary and compare AVL and red-black trees.

5. Describe B-trees, B+ trees, and tries and identify suitable applications.

6. Select an appropriate tree structure for indexing, storage, searching, and prefix queries.

7. Evaluate time, space, implementation, and operational trade-offs.

1. Tree Terminology and Structural Properties

A tree consists of vertices, called nodes, connected by edges. One node is designated the root. Every node except the root has exactly one parent and may have zero or more children.

Important terms include:

• Root: The node with no parent.
• Leaf: A node with no children.
• Internal node: A node with at least one child.
• Degree of a node: Its number of children.
• Depth: The number of edges from the root to a node. The root has depth 0.
• Height of a node: The number of edges on the longest downward path from that node to a leaf. A leaf has height 0 under this convention.
• Height of a tree: The height of its root.
• Subtree: A node together with all of its descendants.
• Ancestor and descendant: A node occurring above or below another node, respectively.
• Path: A sequence of connected nodes.
• Level: Often used synonymously with depth, although some texts count the root as level 1 rather than 0.

A tree with n nodes has exactly n − 1 edges. This follows because the root contributes no incoming edge and every other node has one parent edge. A forest is a collection of disjoint trees.

A binary tree is a tree in which each node has at most two children, conventionally called left and right. A binary tree is full if every node has either zero or two children. It is complete if every level except possibly the last is full and the final level is filled from left to right. It is perfect if every internal node has two children and all leaves occur at the same depth.

If a binary tree has height h, its maximum possible number of nodes is:

2^(h+1) − 1.

This bound assumes the root has height 0. A complete binary tree with n nodes has height Θ(log n), while a general binary tree can have height n − 1.

2. Binary Tree Representation

A linked representation stores each node with a value and references to its left and right children:

```text

Node:

key

left

right

```

A missing child is represented by null. This representation is flexible and is appropriate when the tree changes frequently.

A complete binary tree can also be stored in an array. With zero-based indexing, the left child of a node at index i is at 2i + 1, and the right child is at 2i + 2, provided those positions exist. The parent of a non-root node at index i is at floor((i − 1)/2). Array representation avoids explicit pointers and is especially useful for heaps, but it can waste space for sparse or irregular trees.

3. Tree Traversals

A traversal systematically visits every node. The principal depth-first traversals are preorder, inorder, and postorder. Breadth-first traversal visits nodes level by level.

Preorder Traversal

Preorder processes the root before its subtrees:

```text

preorder(node):

if node is null: return

visit(node)

preorder(node.left)

preorder(node.right)

```

It is useful for copying a tree, generating prefix expressions, and serializing a structure while preserving its hierarchy.

Inorder Traversal

Inorder processes the left subtree, then the node, then the right subtree:

```text

inorder(node):

if node is null: return

inorder(node.left)

visit(node)

inorder(node.right)

```

For a binary search tree, inorder traversal produces keys in nondecreasing order. This property is central to ordered reporting and sorting.

Postorder Traversal

Postorder processes children before their parent:

```text

postorder(node):

if node is null: return

postorder(node.left)

postorder(node.right)

visit(node)

```

It is useful when deleting a tree, evaluating postfix expressions, or computing information from children before processing a parent.

Breadth-First Traversal

Breadth-first traversal uses a queue:

```text

breadthFirst(root):

if root is null: return

enqueue(root)

while queue is not empty:

node = dequeue()

visit(node)

if node.left is not null: enqueue(node.left)

if node.right is not null: enqueue(node.right)

```

Every traversal visits each node once, so its time complexity is Θ(n). Recursive depth-first traversal uses Θ(h) stack space, where h is tree height. Breadth-first traversal may use Θ(w) space, where w is the maximum width of the tree.

Worked Example: Traversal

Consider the tree:

```text

8

/ \

3 10

/ \ \

1 6 14

/ \ /

4 7 13

```

Its preorder sequence is 8, 3, 1, 6, 4, 7, 10, 14, 13. Its inorder sequence is 1, 3, 4, 6, 7, 8, 10, 13, 14. Its postorder sequence is 1, 4, 7, 6, 3, 13, 14, 10, 8. Its breadth-first sequence is 8, 3, 10, 1, 6, 14, 4, 7, 13.

4. Binary Search Trees

A binary search tree (BST) is a binary tree satisfying an ordering invariant. For every node, keys in the left subtree are less than the node's key, and keys in the right subtree are greater, assuming distinct keys. Implementations that permit duplicate keys must specify a policy, such as storing duplicates consistently on one side or maintaining a frequency count.

Search follows the ordering property. At each node, compare the target with the current key and continue left or right. Insertion follows the same path and attaches a new leaf. Deletion has three cases:

1. A leaf can be removed directly.

2. A node with one child can be replaced by that child.

3. A node with two children can be replaced by its inorder successor, the smallest node in its right subtree, or by its inorder predecessor, the largest node in its left subtree. The replacement node is then deleted from its original position.

If h is the tree height, search, insertion, and deletion each take O(h). In a balanced tree h = Θ(log n), producing logarithmic operations. In the worst case, inserting already sorted keys creates a chain with h = n − 1, so operations take Θ(n). A BST is therefore an ordered structure, but it is not automatically balanced.

5. Maintaining Balance: Rotations and Balanced Search Trees

Balancing limits height and protects performance from unfavorable insertion orders. A rotation changes local links while preserving the inorder sequence of keys.

A right rotation at node y, where x is y's left child, makes x the new local root and moves x's right subtree to become y's left subtree. A left rotation is the mirror image. Rotations take Θ(1) time and preserve the BST ordering invariant.

AVL Trees

An AVL tree is a BST in which, for every node, the height difference between the left and right subtrees is at most one. The balance factor is commonly defined as:

balance factor = height(left subtree) − height(right subtree).

Valid values are −1, 0, and +1. After insertion or deletion, balance factors are updated along the path to the root. If a node becomes unbalanced, rotations restore the condition.

The four standard imbalance patterns are:

• LL: A right rotation.
• RR: A left rotation.
• LR: A left rotation on the child followed by a right rotation.
• RL: A right rotation on the child followed by a left rotation.

AVL trees have height Θ(log n), so search, insertion, and deletion are O(log n) in the worst case. Their stricter balance generally makes searches efficient, but updates may require more frequent rotations and height maintenance.

Red-Black Trees

A red-black tree is a BST whose nodes are colored red or black and satisfy structural rules. A common formulation is:

1. Every node is red or black.

2. The root is black.

3. Null leaves, treated as sentinel nodes, are black.

4. A red node cannot have a red child.

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

These rules ensure height O(log n), although red-black trees may be less rigidly balanced than AVL trees. Insertion and deletion use recoloring and rotations. The operations remain O(log n) in the worst case.

AVL trees are often attractive when searches greatly outnumber updates and tight height is valuable. Red-black trees often provide a favorable update balance and are widely used in ordered maps and sets in standard libraries. Actual choice also depends on implementation complexity, memory layout, concurrency, and workload measurements.

6. Multiway Trees and External Storage

Binary trees are not always suitable for large databases or file systems. Accessing secondary storage is much slower than accessing main memory, and a disk or solid-state drive transfers data in blocks. A tree with many small levels may require several expensive block accesses. Multiway trees reduce height by allowing each node to contain multiple keys and children.

A B-tree of order m is a balanced multiway search tree in which a node has at most m children and at most m − 1 keys. Precise minimum occupancy conventions vary between textbooks; a typical non-root node has at least ceil(m/2) children, while the root has special lower bounds. All leaves occur at the same depth. Keys within a node divide the ranges represented by its children.

Search examines keys within a node and follows the appropriate child. If a node is full during insertion, it is split and a separator key is promoted to its parent. Deletion may borrow a key from a sibling or merge nodes when occupancy becomes too low. These operations preserve balance.

If each node can hold many keys, the height is small. With n records and branching factor approximately m, the height is logarithmic in n with base related to m. More importantly, a high branching factor reduces the number of storage blocks accessed.

B+ Trees

A B+ tree is a variant in which internal nodes contain routing keys, while actual records or record pointers are stored in leaves. Leaf nodes are commonly linked in sorted order. This design supports both point queries and efficient range scans:

• A point query descends from the root to a leaf.
• A range query finds the first relevant leaf and follows leaf links until the range ends.

B+ trees are standard choices for database indexes and many file systems. They are particularly effective when nodes are sized to match storage pages. The index may be clustered, meaning records are physically organized according to the index order, or unclustered, meaning the index points to records stored elsewhere. These choices affect the cost of range retrieval.

7. Tries and String-Oriented Trees

A trie, or prefix tree, stores strings according to their characters. Each edge represents a character, and a path from the root represents a prefix. A terminal marker identifies a complete stored word, because one word may be a prefix of another.

For a string of length L, search, insertion, and deletion can take O(L), assuming child access is O(1). This bound depends on the alphabet representation. An array of child pointers gives fast access but may waste memory; a map or balanced structure saves space but adds lookup cost.

A compressed trie merges chains of nodes with only one child, reducing space and sometimes traversal steps. A radix tree is a common compressed form. Tries are useful for autocomplete, dictionaries, routing tables, spell checking, and longest-prefix matching. Unlike comparison-based search trees, their performance depends primarily on key length rather than the number of stored keys.

8. Applied Case: Autocomplete for a University Search Portal

Background

This illustrative case concerns a university portal that allows students to search courses, departments, instructors, and administrative services. The portal must return suggestions after each keystroke.

Problem

A simple list scan compares the query with every stored term. With N terms, this may require Θ(N) comparisons per keystroke and creates unacceptable latency as the catalog grows. Suggestions must also be ranked by popularity, recency, or institutional relevance.

Analysis

A BST can locate complete terms efficiently, but it is not naturally optimized for finding all terms beginning with a prefix. A B+ tree can support ordered range queries and is appropriate when the dictionary is persisted in a database. A trie directly represents prefixes and can locate the node for a prefix in time proportional to the prefix length L.

Approach and Solution

The portal maintains a trie for frequently requested terms. Each terminal or prefix node stores a small ranked list of likely completions rather than every descendant result. The complete catalog is persisted in a database with a B+ tree index for durable lookup and range reporting. Updates are processed asynchronously: new search statistics adjust suggestion scores, while moderation rules remove inappropriate or obsolete terms.

For a query such as “data st”, the system follows the characters to the node representing that prefix, retrieves its ranked suggestions, and returns entries such as “Data Structures” and “Data Storytelling.” A cache stores especially common prefixes.

Outcome

The trie reduces prefix navigation to approximately O(L), while the bounded suggestion list keeps response size predictable. The B+ tree remains useful for full catalog searches and range-based administrative queries. The hybrid design separates low-latency interaction from durable, transactional storage.

Learning Points

No single tree is optimal for every operation. Data representation, update frequency, storage medium, key type, ranking requirements, and memory limits must all be considered. User-facing systems must additionally address privacy, security, accessibility, and content governance.

9. Choosing a Tree Structure

Selection should begin with the dominant query and update patterns.

• Use a general binary tree when hierarchy itself is important and ordered searching is not required.
• Use a BST when an ordered in-memory dictionary is needed and balancing is controlled or guaranteed by the implementation.
• Use an AVL tree when predictable, fast search is especially important.
• Use a red-black tree when a robust ordered map or set requires frequent updates.
• Use a B-tree or B+ tree for large indexes stored on disk or page-oriented systems.
• Use a trie for prefix, dictionary, or character-based queries.
• Use a compressed trie when long single-child chains create excessive memory use.

Performance analysis should include more than asymptotic complexity. Cache locality, pointer overhead, node size, storage-page alignment, concurrency, persistence, fault recovery, and workload distribution can determine practical performance.

10. Challenges, Limitations, and Governance

Trees can consume substantial memory because each node may contain several references, metadata fields, or balancing information. Pointer-heavy structures may have poor cache locality. Recursive implementations can overflow the call stack on deep trees, especially when balance assumptions fail.

Deletion and duplicate-key policies are frequent sources of defects. Implementations should explicitly define whether keys are unique, how equal keys are stored, and what happens when a referenced record is removed. Balanced trees require careful testing of boundary cases, including rotations at the root and deletion from minimally occupied nodes.

In databases, indexes accelerate reads but increase storage requirements and update cost. Excessive indexing can slow inserts and create consistency obligations. In tries used for autocomplete, collected queries may reveal sensitive interests. Systems should minimize data collection, restrict access, apply retention policies, and avoid exposing private or discriminatory suggestions. Moderation and audit procedures are needed when autocomplete influences users' decisions or displays names and categories.

11. Contemporary Developments and Best Practices

Modern systems often combine tree structures with caching, compression, memory mapping, and distributed storage. Database engines adapt page size, fill factor, and index organization to workload. Learned indexes and hybrid search structures use statistical models to estimate key positions, but conventional trees remain important because they provide robust ordering, worst-case guarantees, and well-understood update behavior.

Recommended practices include:

1. State the invariant formally before implementing the structure.

2. Test empty trees, one-node trees, duplicate keys, sorted input, and deletion cases.

3. Verify invariants after randomized sequences of operations.

4. Measure realistic workloads rather than relying only on asymptotic notation.

5. Match node size to memory-cache lines or storage pages where appropriate.

6. Separate logical ordering from physical storage and record ownership.

7. Document height conventions and duplicate-key behavior.

8. Protect indexed or autocomplete data through access control, minimization, and auditing.

Chapter Summary

Trees represent hierarchical relationships and support structured navigation. Binary trees can be traversed in preorder, inorder, postorder, and breadth-first order, each serving different purposes. A binary search tree uses key ordering to support search, insertion, and deletion in time proportional to its height, but can become linear when skewed. AVL and red-black trees maintain logarithmic height through rotations, balance conditions, and recoloring.

B-trees and B+ trees use high branching factors to reduce storage accesses and are central to database and file-system indexing. B+ trees place records or record pointers in linked leaves, making them effective for range scans. Tries organize strings by character prefixes and are especially suitable for autocomplete and dictionary operations. Practical design requires consideration of workload, memory, storage, cache behavior, persistence, security, privacy, and governance.

Key Terms

Tree: A connected acyclic structure of nodes and edges.

Root: The unique node with no parent.

Leaf: A node with no children.

Height: The maximum number of edges from a node to a descendant leaf.

Depth: The number of edges from the root to a node.

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

Complete binary tree: A binary tree filled level by level from left to right.

Traversal: A systematic process for visiting tree nodes.

Binary search tree: A binary tree maintaining an ordering relation between left and right subtrees.

Rotation: A local restructuring that preserves BST order.

AVL tree: A height-balanced BST with balance factors −1, 0, or +1.

Red-black tree: A colored BST satisfying rules that bound its height.

B-tree: A balanced multiway search tree designed for efficient block access.

B+ tree: A B-tree variant storing records or pointers in linked leaves.

Trie: A character-based prefix tree for strings.

Compressed trie: A trie that merges chains of single-child nodes.

Inorder successor: The smallest key in a node's right subtree.

Index: An auxiliary structure that accelerates data retrieval.

Prefix query: A query requesting keys beginning with a specified sequence.

Review Questions

Short Answer Questions

1. Why can a binary search tree have linear-time search in the worst case?

2. What ordering does inorder traversal produce for a valid BST?

3. State the four imbalance patterns handled in AVL insertion.

4. Why are B+ tree leaves commonly linked?

5. What type of query is a trie especially designed to support?

Long Answer Questions

1. Explain preorder, inorder, postorder, and breadth-first traversal, including one application of each.

2. Describe BST deletion and analyze its time complexity in terms of tree height.

3. Compare AVL trees and red-black trees in terms of balance, operations, and suitable workloads.

4. Explain the structure and storage advantages of B-trees and B+ trees.

5. Discuss how memory, storage pages, caching, and governance influence tree selection in an information system.

Analytical / Application Questions

1. Design a data structure for a dictionary containing millions of terms that must support both autocomplete and durable range queries. Justify whether you would use a trie, B+ tree, or a hybrid.

2. A BST receives keys in strictly increasing order. Describe its resulting shape, give the asymptotic cost of searching, and propose two remedies.

3. An application performs many point searches but relatively few updates in main memory. Compare an AVL tree, red-black tree, and hash table, identifying the principal trade-offs and recommending one structure under an ordered-output requirement.

Multiple Choice Questions with Answers

Question 1

Which traversal produces keys in sorted order for a valid binary search tree?

A. Preorder

B. Inorder

C. Postorder

D. Breadth-first

Correct Answer: B. Inorder

Question 2

What is the worst-case time complexity of search in an unbalanced binary search tree with n nodes?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: C. O(n)

Question 3

Which AVL imbalance is corrected by a single right rotation?

A. LL

B. RR

C. LR

D. RL

Correct Answer: A. LL

Question 4

Which property is required in a red-black tree?

A. Every node has exactly two children

B. Every leaf stores a record

C. A red node cannot have a red child

D. All nodes have the same depth

Correct Answer: C. A red node cannot have a red child

Question 5

Why are B+ trees effective for range queries?

A. They prohibit duplicate keys

B. Their leaves are commonly linked in sorted order

C. They store one child per node

D. They avoid all disk accesses

Correct Answer: B. Their leaves are commonly linked in sorted order

Question 6

In a B+ tree, where are actual records or record pointers commonly stored?

A. Only in the root

B. Only in internal routing nodes

C. In the leaves

D. Outside the index with no references

Correct Answer: C. In the leaves

Question 7

What does a trie primarily organize?

A. Strings by their character prefixes

B. Records by disk-sector size

C. Numbers by arithmetic magnitude only

D. Graphs by edge weights

Correct Answer: A. Strings by their character prefixes

Question 8

Using zero-based array indexing for a complete binary tree, what is the left child index of node i?

A. i + 1

B. 2i

C. 2i + 1

D. 2i + 2

Correct Answer: C. 2i + 1

Question 9

What is the time complexity of a standard tree traversal that visits every node once?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: C. Θ(n)

Question 10

Which structure is generally most directly suited to autocomplete by prefix?

A. Trie

B. Stack

C. Queue

D. Heap

Correct Answer: A. Trie