Trees, Search Trees and Priority Structures

Introduction and Context

A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike a general graph, a tree is connected and contains no cycles. Trees model relationships in which one object may contain, classify, or depend on other objects: file systems, HTML documents, compiler syntax, organizational structures, indexes, dictionaries, and scheduling systems.

Trees are especially valuable because they combine structured representation with efficient search. A carefully designed tree can support insertion, deletion, and lookup in approximately logarithmic time, even when the data set is too dynamic for a sorted array. Other tree structures specialize in different tasks. Heaps provide rapid access to the minimum or maximum element, tries support prefix search, and B-trees reduce disk accesses in database systems.

This chapter develops the representation and analysis of trees, then examines binary search trees, AVL trees, red-black trees, heaps, priority queues, tries, and B-trees.

Learning Objectives

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

• define trees and distinguish common terminology;
• represent trees using linked nodes and arrays;
• traverse trees using depth-first and breadth-first methods;
• implement and analyze binary search trees;
• explain why AVL and red-black trees maintain balance;
• construct heaps and priority queues;
• use tries for dictionaries and autocomplete;
• explain how B-trees support database and file-system indexing;
• select an appropriate tree structure for a practical application;
• evaluate time, space, implementation, and workload trade-offs.

1. Tree Terminology and Representation

A tree is commonly represented as T = (V, E), where V is a set of nodes and E is a set of edges. For a tree with n nodes, the number of edges is n − 1. This assumes a finite, connected, acyclic tree.

A selected node with no parent is the root. A node directly connected below another node is its child; the node above it is its parent. Nodes with the same parent are siblings. A node with no children is a leaf. The degree of a node is its number of children, while the degree of a tree is the maximum node degree.

The depth of a node is the number of edges from the root to that node. The root has depth 0. The height of a node is the number of edges on the longest downward path from that node to a leaf. A tree’s height is the height of its root. Some texts count nodes rather than edges; implementations must document which convention is used.

A subtree consists of a node and all its descendants. A binary tree is a tree in which each node has at most two children, conventionally called left and right children. A full binary tree has either zero or two children at every node. A complete binary tree has every level full except possibly the last, and the last level is filled from left to right. A perfect binary tree has all internal nodes with two children and all leaves at the same depth.

Linked Representation

A general tree can store a list of child references in each node. A binary tree usually stores:

Node:
    key
    value
    left  → Node or null
    right → Node or null

This representation supports irregular shapes and dynamic insertion. Its disadvantages are reference overhead and poor locality when nodes are allocated far apart in memory.

Array Representation

Complete binary trees, especially heaps, can be stored compactly in an array. With zero-based indexing, the relationships are:

Here i is an array index. These formulas apply because a complete tree fills positions level by level. They do not efficiently represent an arbitrary sparse binary tree.

2. Tree Traversal

Traversal is the systematic visiting of every node. A traversal may process a node before its descendants, between its subtrees, or after them.

Depth-First Traversals

For a binary tree:

• Preorder: visit node, traverse left subtree, traverse right subtree.
• Inorder: traverse left subtree, visit node, traverse right subtree.
• Postorder: traverse left subtree, traverse right subtree, visit node.

For example, in the tree whose root is 8, with left subtree 3 containing 1 and 6, and right subtree 10 containing 14:

• preorder: 8, 3, 1, 6, 10, 14;
• inorder: 1, 3, 6, 8, 10, 14;
• postorder: 1, 6, 3, 14, 10, 8.

Inorder traversal is particularly important because it lists the keys of a binary search tree in sorted order. Postorder is useful for deleting a tree or evaluating expression trees. Preorder can serialize a tree when null-child markers or additional structure information are included.

A recursive traversal uses the call stack. An iterative traversal uses an explicit stack and is often preferable when tree height may be large. Recursive algorithms have O(h) auxiliary stack space, where h is tree height.

Breadth-First Traversal

Breadth-first, or level-order, traversal visits nodes by increasing depth. It uses a queue: enqueue the root, repeatedly remove the front node, process it, and enqueue its children. Its time complexity is O(n), and its auxiliary space is O(w), where w is the maximum width of the tree.

3. Binary Search Trees

A binary search tree (BST) is a binary tree satisfying an ordering invariant. For every node with key k, keys in the left subtree are less than k and keys in the right subtree are greater than k. Duplicate-key policies must be explicit: duplicates may be rejected, counted in a node, or placed consistently on one side.

Search, Insertion, and Deletion

To search for a key, compare it with the current node. If it matches, the search succeeds. If it is smaller, continue left; otherwise continue right. Insertion follows the same comparisons until a null child position is reached.

Deletion has three cases:

1. A leaf is removed directly.
2. A node with one child is replaced by its child.
3. A node with two children is replaced by its inorder successor (the smallest key in its right subtree) or its inorder predecessor (the largest key in its left subtree), after which that replacement node is removed from its original location.

If h is the tree height, search, insertion, and deletion take O(h) time. In a balanced tree h = O(log n), giving logarithmic operations. In a degenerate tree formed by inserting already sorted keys, h = n − 1 and operations become O(n). Thus, the BST ordering invariant alone does not guarantee good performance.

Worked Example: BST Deletion

Suppose a BST contains 20 as the root, with 10 and 30 as children. Node 30 has children 25 and 40. To delete 30, select its inorder successor, 40, because 40 is the smallest key in the right subtree. Copy 40 into the position formerly occupied by 30, then remove the original leaf 40. The ordering property remains valid: 25 < 40 and all keys below the root remain greater than 20.

A BST is useful when ordered operations are required, including predecessor, successor, range reporting, and sorted iteration. Hash tables generally provide faster average exact lookup, but they do not naturally provide sorted order or efficient range queries.

4. Balanced Search Trees

A balanced search tree limits height by restructuring after updates. Balance does not mean that every path has exactly the same length; it means that height remains bounded by a logarithmic function of n.

AVL Trees

An AVL tree is a BST in which the balance factor of every node is −1, 0, or +1. With height convention based on edges:

The height of an AVL tree is O(log n). After insertion or deletion, rotations restore the balance condition. A right rotation and a left rotation preserve inorder key order while changing local structure.

The four imbalance patterns are:

• LL: right rotation;
• RR: left rotation;
• LR: left rotation on the left child, then right rotation;
• RL: right rotation on the right child, then left rotation.

For example, inserting 30, then 20, then 10 produces an LL imbalance at 30. A right rotation makes 20 the local root, with 10 on its left and 30 on its right.

AVL trees generally provide stricter balance than red-black trees. Consequently, searches can be especially efficient, but updates may perform more rebalancing work. They are suitable for read-intensive ordered data.

Red-Black Trees

A red-black tree is a BST whose nodes are colored red or black and obey rules such as:

1. the root is black;
2. a red node cannot have a red child;
3. every path from a node to its null leaves contains the same number of black nodes;
4. null leaves are treated as black sentinels.

These invariants imply height O(log n). Rotations and recoloring repair violations after insertion and deletion. Red-black trees usually allow less rigid balance than AVL trees, often reducing update overhead. They are widely used for ordered maps and sets in standard libraries.

Comparison

The correct choice depends on update frequency, search frequency, implementation complexity, and whether predictable worst-case performance is required.

5. Heaps and Priority Queues

A priority queue stores items with priorities and supports access to the item with minimum or maximum priority. It differs from a FIFO queue: removal is determined by priority rather than arrival time.

A binary heap is a complete binary tree satisfying the heap property. In a min-heap, each parent key is less than or equal to its children. In a max-heap, each parent key is greater than or equal to its children. The property guarantees that the root is the minimum or maximum, but does not sort all elements.

Heap Operations

• peek: return the root in O(1) time;
• insert: append at the next complete-tree position and move upward, called sift-up, in O(log n);
• extract-min/max: replace the root with the last element, remove the last position, and sift down in O(log n);
• build-heap: transform an arbitrary array into a heap in O(n) time;
• heap sort: repeatedly extract the root, taking O(n log n) time overall.

Build-heap is O(n), not O(n log n), because most nodes are near the leaves and require little movement. A common proof sums the possible work by height; the resulting geometric series is bounded by a constant multiple of n.

A priority queue may be implemented using a heap, balanced BST, or specialized structure. A heap is usually preferred when only the extreme priority is needed. A BST is preferable when arbitrary ordered queries, such as finding the next priority in a range, are also needed.

Applications include CPU scheduling, event simulation, Dijkstra’s shortest-path algorithm, emergency-room triage, bandwidth management, and merging sorted streams. If equal priorities require fair ordering, store a sequence number with each item and compare (priority, sequence number).

6. Tries and Autocomplete

A trie, or prefix tree, stores strings by sharing prefixes. Each edge represents a character, and the path from the root spells a prefix. A terminal marker identifies a complete stored word; without this marker, a word that is a prefix of another word could not be distinguished.

For a string of length L, insertion and exact lookup take O(L), assuming child access is O(1), such as with a fixed alphabet array. With a map of outgoing characters, the cost also depends on map operations. Memory usage can be high because many nodes and child references may be required.

Autocomplete proceeds as follows:

1. follow the characters of the user’s prefix;
2. if the path is absent, return no matches;
3. traverse the corresponding subtree;
4. rank terminal words by frequency, recency, language model score, or a combination;
5. return the best k suggestions.

A trie can be compressed by merging chains of nodes with only one child; this produces a radix tree or Patricia trie. Compressed representations reduce space while preserving prefix operations. Production autocomplete systems may combine tries with caches, frequency tables, personalization, and privacy controls.

7. B-Trees and External Indexing

Main-memory trees are not automatically efficient when data resides on storage. Disk and solid-state storage operate in blocks or pages, so an index should minimize expensive page accesses. A B-tree is a multiway balanced search tree designed for this environment.

A B-tree node stores multiple sorted keys and multiple child pointers. All leaves occur at the same depth. Nodes are maintained within lower and upper occupancy bounds, except for permitted root exceptions. When a node overflows, it splits and promotes a separator key to its parent. When deletion causes underflow, keys may be redistributed with a sibling or nodes may be merged.

If a B-tree has height h and each node can contain many keys, a search performs O(h) page accesses. With branching factor b, height is approximately logarithmic in the number of records, with the base determined by b. A B+ tree is a common variant: internal nodes contain separator keys, while records or record pointers reside in leaves; leaf nodes are linked, making range scans efficient.

Database indexes commonly use B+ trees for queries such as:

SELECT * FROM Orders
WHERE customer_id = 1042
  AND order_date BETWEEN '2025-01-01' AND '2025-03-31';

An index on (customer_id, order_date) can support the equality condition followed by an ordered range condition. Index design must consider selectivity, write cost, storage size, and the leftmost-prefix behavior of composite indexes. An index is not universally beneficial: every insert, update, and delete may require index maintenance.

8. Choosing a Tree Structure

Selection should begin with the dominant operations rather than with the name of a data structure.

Important design questions include: Are keys unique? Are range queries needed? Is the data in RAM or on storage? Is the workload read-heavy or update-heavy? Are worst-case guarantees required? How important are memory locality and predictable latency?

9. Applied Case: A University Registration Platform

Background

Consider an illustrative university registration platform that stores courses, schedules, and student requests. The system must search courses by code, show courses in sorted order, suggest course names while users type, and process wait-list requests by priority.

Problem

A single unsorted list causes linear searches. A hash table improves exact course-code lookup but does not naturally support sorted course listings or date ranges. Wait-list processing requires an efficient highest-priority removal operation, while autocomplete requires prefix matching.

Analysis and Approach

The platform can use several specialized structures:

• a red-black tree for courses keyed by course code, supporting ordered iteration and predictable updates;
• a B+ tree in the database for persistent indexes on department and course number;
• a trie for course-title prefixes such as “data str…”;
• a max-heap for wait-list requests, with priority based on graduation urgency and request time;
• a hash table as a cache for frequent exact lookups.

The wait-list priority can be represented lexicographically as (graduation urgency, request time), with a sequence number breaking ties. The system must define whether a larger urgency score means higher priority and must preserve fairness within equal categories.

Outcome

Each operation is matched to a suitable access pattern. Search and sorted reports use ordered trees, persistent range queries use a page-oriented index, prefix suggestions use the trie, and repeated top-priority selection uses the heap. The design is more complex than using one structure, but it reduces latency and expresses business rules explicitly.

Learning Points

Data-structure choice is a workload and governance decision. Correctness includes both algorithmic invariants and application policies. A priority queue that silently breaks ties unfairly, or an index that exposes unauthorized records, is not a successful production design.

10. Correctness, Complexity, and Engineering Practice

Tree algorithms rely on invariants. A BST must preserve ordering; an AVL tree must preserve balance factors; a red-black tree must preserve coloring rules; a heap must preserve parent-child priority; a B-tree must preserve sorted keys, occupancy constraints, and equal leaf depth.

Testing should include empty trees, one-node trees, duplicate keys, deletion of the root, deletion of nodes with zero, one, and two children, highly sorted input, repeated priorities, long strings, missing prefixes, and storage-page failures. Property-based tests can verify that inorder output is sorted, heap parents dominate children, and every search-tree path follows the comparison rules.

Complexity claims depend on assumptions. O(log n) search for an AVL tree assumes rotations and height metadata are correctly maintained. O(L) trie lookup assumes character access and child lookup have bounded cost. B-tree analysis focuses on page accesses because CPU comparisons are often less expensive than storage I/O. Real performance also depends on cache locality, allocation, concurrency, persistence, and workload distribution.

11. Limitations, Security, and Contemporary Developments

Trees can consume substantial memory through pointers, metadata, and unused child slots. Poorly chosen comparison functions or adversarially ordered input can degrade an ordinary BST. Recursive implementations may overflow the call stack on pathological height. Concurrent updates require synchronization or specialized lock-free and copy-on-write techniques.

Indexes can create security risks. A trie or search index may reveal sensitive terms through autocomplete suggestions. Database indexes can expose information through timing or error behavior if authorization filters are applied after, rather than within, the indexed query. Access control, encryption at rest, audit logging, data retention, and careful logging are therefore part of responsible tree-based system design.

Contemporary systems use cache-conscious layouts, adaptive radix trees, learned indexes, and distributed sorted structures. Learned indexes use models to predict key positions and may reduce search work for suitable data distributions, but they require fallback mechanisms, retraining strategies, and careful evaluation under updates and distribution shifts. They complement rather than eliminate classical trees, whose invariants provide robust correctness guarantees.

Best Practices

1. State the duplicate-key policy before implementing a BST.
2. Document whether height and depth count edges or nodes.
3. Encapsulate rotations and test them independently.
4. Use heaps only when their limited ordering is sufficient.
5. Include stable tie-breaking in priority queues.
6. Choose trie child storage according to alphabet size and memory limits.
7. Design database indexes from actual query predicates and workload measurements.
8. Test invariants after every structural update during development.
9. Measure page accesses, cache behavior, and update cost—not only asymptotic time.
10. Protect indexed and autocomplete data with authorization and privacy controls.

Chapter Summary

Trees represent hierarchical relationships and support specialized forms of efficient access. Traversals provide systematic processing: inorder traversal sorts BST keys, postorder supports safe deletion, and breadth-first traversal processes levels. Ordinary BST operations take O(h), which may become linear without balance. AVL and red-black trees maintain O(log n) height through rotations, recoloring, and structural invariants. Heaps provide O(1) access to an extreme priority and O(log n) insertion and extraction, making them effective priority-queue implementations. Tries organize strings by shared prefixes and support autocomplete, while B-trees and B+ trees reduce storage-page accesses and support database range queries. Effective engineering requires matching the structure to workload, memory and storage behavior, correctness invariants, fairness, security, and governance requirements.

Key Terms

Tree: A connected acyclic structure of nodes and edges.

Root: The node with no parent.

Leaf: A node with no children.

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

Binary tree: A tree with at most two children per node.

Traversal: A systematic method of visiting nodes.

Binary search tree: A binary tree ordered by key comparisons.

Inorder traversal: Left subtree, node, right subtree.

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 with invariants guaranteeing logarithmic height.

Heap: A complete tree satisfying a parent-child priority relation.

Priority queue: An abstract structure that removes items by priority.

Trie: A character-based tree for strings and prefixes.

Radix tree: A compressed trie that merges single-child paths.

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

B+ tree: A B-tree variant with records in linked leaf nodes.

Invariant: A property that must remain true during operations.

Range query: A query retrieving keys within an ordered interval.

Review Questions

Short Answer Questions

1. What is the difference between a complete binary tree and a perfect binary tree?
2. Why does inorder traversal of a valid BST produce sorted keys?
3. State the time complexity of insertion and extraction in a binary heap.
4. What problem does balancing solve in a binary search tree?
5. Why are B+ trees effective for database range queries?

Long Answer Questions

1. Explain BST deletion in all three structural cases and justify why the ordering invariant is preserved.
2. Compare AVL trees and red-black trees in terms of balance, rotations, update cost, and suitable workloads.
3. Describe binary-heap insertion, extraction, and build-heap, including their time complexities.
4. Explain trie construction and autocomplete, including memory trade-offs and radix-tree compression.
5. Describe B-tree node splitting and merging and relate them to disk-page efficiency.

Analytical / Application Questions

1. A system performs millions of minimum-priority removals but rarely asks for arbitrary ordered ranges. Which structure would you choose, and why?
2. A BST receives keys in increasing order. Explain the resulting performance and propose two remedies.
3. A database must support equality filtering on department and date-range filtering within that department. Propose an index design and explain the query-order reasoning.

Multiple Choice Questions with Answers

Question 1

Which traversal of a valid binary search tree lists keys in nondecreasing order?

A. Preorder

B. Inorder

C. Postorder

D. Level-order

Correct Answer: B. Inorder

Question 2

In a zero-based array representation of a complete binary tree, what is the left child index of node i?

A. 2i

B. 2i − 1

C. 2i + 1

D. i + 2

Correct Answer: C. 2i + 1

Question 3

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

A. O(1)

B. O(log n)

C. O(√n)

D. O(n)

Correct Answer: D. O(n)

Question 4

An AVL node has left-subtree height 4 and right-subtree height 2. What is its balance factor using left height minus right height?

A. −2

B. 0

C. 2

D. 6

Correct Answer: C. 2

Question 5

Which operation is guaranteed to take O(1) time in a binary min-heap, ignoring the cost of returning the value?

A. Finding the minimum

B. Inserting an arbitrary key

C. Deleting an arbitrary key

D. Sorting all keys

Correct Answer: A. Finding the minimum

Question 6

Why can a trie support lookup in time proportional to the string length?

A. It compares the string with every stored string

B. It follows one edge for each character

C. It always uses binary search on integers

D. It stores only complete strings in sorted arrays

Correct Answer: B. It follows one edge for each character

Question 7

Which property is characteristic of a B+ tree?

A. Every node has exactly two children

B. The root is always a leaf

C. Records or record pointers are stored in linked leaves

D. Keys are never duplicated as separators

Correct Answer: C. Records or record pointers are stored in linked leaves

Question 8

Building a binary heap from an arbitrary array using the bottom-up method has which asymptotic time complexity?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: C. O(n)

Question 9

Which structure is most appropriate for autocomplete based on shared character prefixes?

A. Trie

B. Max-heap

C. Disjoint-set forest

D. Circular queue

Correct Answer: A. Trie

Question 10

A priority queue must process equal-priority requests in arrival order. What is the best tie-breaking addition?

A. A random value

B. A sequence number increasing with arrival

C. The memory address of the item

D. The item’s unsorted hash value

Correct Answer: B. A sequence number increasing with arrival