Trees and Balanced Search Trees

Introduction

Trees are hierarchical data structures used whenever information has parent–child relationships. File systems, compiler syntax trees, database indexes, network routing structures, XML documents, and ordered maps all rely on tree concepts. Unlike linear structures such as arrays, stacks, and queues, trees branch into multiple substructures. This branching supports efficient searching, insertion, deletion, and hierarchical organization.

A major challenge is maintaining efficiency. An ordinary binary search tree can become severely unbalanced and degenerate into a linked list. Balanced search trees address this problem by preserving structural properties that keep their height proportional to the logarithm of the number of stored elements.

This chapter develops tree terminology, binary-tree representations and traversals, binary search trees, AVL trees, red–black trees, rotations, balancing invariants, and ordered-map applications.

Learning Objectives

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

• explain fundamental tree terminology and structural properties;
• distinguish general trees, binary trees, complete trees, full trees, and balanced trees;
• perform preorder, inorder, postorder, and level-order traversals;
• implement and analyze binary search tree operations;
• explain why unbalanced search trees can have linear height;
• apply single and double rotations;
• describe AVL balance factors and red–black invariants;
• compare AVL trees and red–black trees for practical applications;
• use balanced trees to implement ordered maps and sets.

1. Tree Terminology and Structure

A tree consists of vertices, called nodes, connected by edges. One node is designated as the root. Every node except the root has exactly one parent, while a node may have zero or more children. A node with no children is a leaf or external node. A node with at least one child is an internal node.

The degree of a node is its number of children. The degree of a tree is the maximum node degree in that tree. A path is a sequence of nodes connected by edges. The path length is the number of edges in it. The depth of a node is its distance from the root; the root has depth 0. The height of a node is the maximum distance from that node to a descendant leaf. The height of a tree is the height of its root.

A node and all its descendants form a subtree. If node u occurs on the path from the root to node v, u is an ancestor of v and v is a descendant of u. Nodes with the same parent are siblings.

A tree with n nodes contains exactly n − 1 edges, provided n ≥ 1. This follows because every node except the root has one incoming parent edge.

Binary trees

A binary tree is a tree in which every node has at most two children. The children are conventionally identified as the left child and right child. A binary tree is not necessarily a binary search tree; the latter imposes an ordering rule on keys.

Important classifications include:

For a perfect binary tree of height h, where the root has height 0, the number of nodes is:

This equation applies only to perfect binary trees. Consequently, a perfect tree has height:

A general binary tree with n nodes may have height as large as n − 1.

2. Representing Binary Trees

A linked representation stores, in each node, a key or value and references to a left and right child. A missing child is represented by null. This representation is flexible and works well for irregular trees.

An array representation is particularly effective for complete binary trees. With zero-based indexing, the node at index i has:

• left child at index 2i + 1;
• right child at index 2i + 2;
• parent at index floor((i − 1) ÷ 2), when i > 0.

Array storage is common for binary heaps. It is usually inefficient for sparse or highly skewed trees because many array positions may be unused.

3. Tree Traversals

A traversal visits every node according to a defined order. Assuming a node has left subtree L, root R, and right subtree Q, the principal depth-first traversals are:

• Preorder: R, L, Q
• Inorder: L, R, Q
• Postorder: L, Q, R

A level-order traversal visits nodes by increasing depth, generally using a queue.

Consider the tree whose root is 8, with left child 3 and right child 10; node 3 has children 1 and 6; node 6 has children 4 and 7; node 10 has right child 14; and node 14 has left child 13. Its traversals are:

• preorder: 8, 3, 1, 6, 4, 7, 10, 14, 13;
• inorder: 1, 3, 4, 6, 7, 8, 10, 13, 14;
• postorder: 1, 4, 7, 6, 3, 13, 14, 10, 8;
• level-order: 8, 3, 10, 1, 6, 14, 4, 7, 13.

The significance of inorder traversal becomes especially important for binary search trees: it produces keys in sorted order.

A recursive inorder algorithm is:

INORDER(node):
    if node = null:
        return
    INORDER(node.left)
    visit(node)
    INORDER(node.right)

Each node is visited once, so traversal time is Θ(n). Recursive space is Θ(h), where h is the tree height. An iterative version can use an explicit stack and has the same asymptotic bounds.

4. Binary Search Trees

A binary search tree (BST) stores keys so that, for every node x:

• every key in x's left subtree is less than x.key;
• every key in x's right subtree is greater than x.key.

The treatment of duplicate keys must be specified. Common policies are to reject duplicates, store a count in each node, or place equal keys consistently on one side. A consistent policy is essential for correctness.

Searching

To search for key k, compare k with the current node. If equal, the search succeeds. If k is smaller, continue in the left subtree; if larger, continue in the right subtree. The search follows one root-to-leaf path, requiring O(h) time, where h is the tree height.

Insertion

Insertion follows the same comparisons until it reaches a null child position. The new node is placed there. Insertion preserves the BST ordering invariant because its location is determined by every comparison on the search path.

Minimum, maximum, successor, and predecessor

The minimum key is found by repeatedly following left children. The maximum is found by repeatedly following right children. The inorder successor of a node is the smallest key greater than it. If the node has a right subtree, its successor is the minimum of that subtree. Otherwise, move upward until reaching an ancestor for which the node lies in the left subtree.

Deletion

Deletion has three cases:

1. Leaf: remove the node directly.
2. One child: replace the node by its only child.
3. Two children: replace its key with its inorder successor's key, then delete that successor. The successor has no left child, so the final deletion reduces to case 1 or 2.

BST operations have the following costs:

The O(log n) claim assumes height Θ(log n). An ordinary BST does not guarantee that condition. Inserting sorted keys 1, 2, 3, 4, 5 produces a chain with height 4, so operations can require linear time.

5. Rotations

A rotation changes local structure while preserving inorder key order. Rotations are therefore useful for balancing search trees.

A right rotation at node y moves its left child x upward. The subtree formerly between x and y becomes y's left subtree. A left rotation is the mirror image: the right child moves upward and the intermediate subtree moves to the former root's right side.

For a right rotation:

y                 x
       / \               / \
      x   D     →       A   y
     / \                   / \
    A   B                 B   D

Before and after rotation, the inorder sequence is A, x, B, y, D. Thus the BST property is preserved. A rotation takes Θ(1) time because it changes only a constant number of references, although heights or metadata may also need updating.

6. AVL Trees

An AVL tree is a BST in which every node satisfies a strict height-balance condition. Define the balance factor of node x as:

The AVL invariant is:

for every node x. A common convention sets height(null) = −1 and height(leaf) = 0. Other conventions are valid if used consistently.

After insertion or deletion, balance factors are recomputed on the path toward the root. If a node becomes unbalanced, rotations restore the invariant.

AVL insertion cases

Let z be the first unbalanced node on the path from the inserted node toward the root.

• Left-left case: insertion occurred in the left subtree of z's left child. Perform a right rotation at z.
• Right-right case: insertion occurred in the right subtree of z's right child. Perform a left rotation at z.
• Left-right case: insertion occurred in the right subtree of z's left child. Perform a left rotation on z.left, followed by a right rotation at z.
• Right-left case: insertion occurred in the left subtree of z's right child. Perform a right rotation on z.right, followed by a left rotation at z.

For example, inserting 30, then 20, then 10 creates a left-left imbalance at 30. A right rotation produces 20 as the subtree root, with 10 on the left and 30 on the right.

AVL trees have height Θ(log n), so search, insertion, and deletion are O(log n). AVL trees are relatively rigidly balanced and often provide excellent search performance. Their stricter balance can require more restructuring after updates than a red–black tree.

7. Red–Black Trees

A red–black tree is a BST whose nodes are colored red or black. The following invariant set is standard:

1. Each node is red or black.
2. The root is black.
3. Every null leaf, often called a sentinel, is black.
4. A red node cannot have a red child.
5. For every node, every path from that node to descendant null leaves contains the same number of black nodes.

The number of black nodes on such a path is its black height. These rules prevent long chains of red nodes and ensure logarithmic height. More precisely, a red–black tree with n internal nodes has height O(log n); a standard bound is h ≤ 2log₂(n + 1), under common definitions.

Insertion initially places a red node as in an ordinary BST. If its parent is black, the invariants remain valid. If its parent is red, a violation exists because red nodes cannot be adjacent. Rebalancing uses recoloring and rotations, considering the color of the node's uncle and whether the configuration is an inner or outer case.

Deletion is more involved because removing a black node can reduce the black count on one path. Implementations repair this temporary imbalance using recoloring and rotations. The important design principle is that the final tree must again satisfy all five invariants.

AVL and red–black comparison

Neither structure is universally superior. If searches greatly outnumber updates, AVL's tighter height may be beneficial. If insertions and deletions are frequent, red–black trees often offer a practical balance between update cost and search performance.

8. Ordered Maps and Sets

An ordered map stores key–value pairs and supports operations such as put, get, remove, minimum, maximum, predecessor, successor, and range queries. A balanced BST is a natural implementation because keys remain ordered.

For example, a map of student records may use student ID as the key and a record reference as the value. A range query for IDs from 2000 through 2999 can be answered by traversing only relevant branches, rather than scanning every record. In a balanced tree, typical search and update operations are O(log n), while reporting k matching values generally requires O(log n + k) time, assuming the output itself requires Θ(k) time.

A set is a map without meaningful associated values. Ordered sets are useful for maintaining sorted event times, routing prefixes under suitable ordering schemes, or retrieving nearest keys.

Balanced trees differ from hash tables. Hash tables usually provide expected O(1) lookup but do not naturally support sorted traversal, predecessor queries, or range queries. Balanced trees provide worst-case O(log n) fundamental operations and preserve order, but generally require more pointer storage and have larger constant factors.

9. Worked Application: An Ordered Student-Record Service

Background

This illustrative case concerns a university service that stores student records keyed by student number. The service must support registration, withdrawal, exact lookup, and queries for all students whose numbers lie within a specified interval.

Problem

A hash table supports exact lookup efficiently but does not directly support ordered range queries. A simple BST supports ordering, but records inserted in nearly sorted student-number order may create a chain and cause poor performance.

Analysis

The service requires:

• exact search;
• insertion and deletion;
• sorted iteration;
• predecessor and successor operations;
• predictable performance under adversarial or highly ordered input.

A balanced search tree satisfies these requirements. A red–black tree is selected because registrations and withdrawals are frequent, while logarithmic worst-case behavior is important.

Approach

Each node stores student number, record reference, color, parent reference, and left and right child references. Insertion first follows the BST search path. The inserted node is colored red, and the red–black repair procedure restores the invariants through recoloring and rotations. Deletion uses the corresponding fix-up procedure.

To answer a range query [a, b], the algorithm prunes subtrees whose keys are entirely below a or above b. It visits the boundary search paths and reports qualifying keys in inorder. Its running time is O(log n + k), where n is the number of records and k is the number reported.

Outcome

The service maintains ordered records without allowing sorted insertion sequences to produce linear-height behavior. Exact operations remain O(log n) in the worst case, and range results are returned in sorted order. A hash table could still be maintained separately if extremely fast exact lookup were more important than ordering, but it would duplicate storage and would not replace the tree's ordered operations.

Learning points

The data structure should be selected from the required operations, not from lookup speed alone. Balance invariants convert a potentially fragile BST into a predictable ordered index. The application also illustrates why asymptotic complexity and workload characteristics must be considered together.

10. Implementation and Design Considerations

Correct implementations must define duplicate-key behavior, null-child representation, height conventions, ownership of stored values, and iterator behavior. Parent references simplify upward rebalancing but increase memory usage. Recursive implementations are conceptually clear, while iterative implementations avoid call-stack limits for very large structures.

Height and color metadata must be updated in the correct order after rotations. A useful testing strategy is to verify after every operation that inorder traversal is sorted, node-parent relationships are consistent, and each balancing invariant holds. Randomized sequences of insertions and deletions can reveal errors that simple examples miss.

Concurrency requires additional design decisions. A tree protected by one global lock is simple but may limit scalability. Fine-grained locking, immutable persistent trees, or specialized concurrent indexes can improve scalability but introduce complexity. Applications handling sensitive records must also enforce authorization and avoid exposing keys or values through unprotected traversal interfaces.

11. Limitations and Contemporary Context

Balanced trees guarantee logarithmic height, but asymptotic bounds do not eliminate cache misses, pointer overhead, allocation costs, or synchronization delays. For massive databases, B-trees and related page-oriented indexes are often preferable because they reduce disk and cache misses by storing many keys per node. For in-memory ordered collections, AVL and red–black trees remain important foundational structures.

Modern libraries frequently provide balanced ordered maps as standard components. Their interfaces may hide rotations and repair algorithms, but developers still need to understand ordering requirements, iterator invalidation, comparator correctness, and worst-case behavior. Artificial intelligence does not replace these invariants: an automatically generated implementation must still be tested against formal structural properties and adversarial inputs.

Best Practices

1. State the ordering and duplicate-key policy explicitly.
2. Use a balanced tree when worst-case ordered operations are required.
3. Preserve and test the BST invariant after every mutation.
4. Treat rotations as local transformations that preserve inorder order.
5. Update height, parent, and color metadata immediately and consistently.
6. Choose AVL for especially search-heavy workloads and red–black trees for balanced update/search workloads, unless measurements indicate otherwise.
7. Use B-tree-family structures for storage systems dominated by block or page access.
8. Test empty trees, one-node trees, duplicate keys, deletion of the root, and long ordered sequences.

Chapter Summary

Trees represent hierarchical relationships through nodes and edges. Binary trees restrict each node to at most two children, while binary search trees additionally require all left-subtree keys to be smaller and all right-subtree keys to be larger under a defined duplicate policy. Preorder, inorder, postorder, and level-order traversals support different processing tasks; inorder traversal of a BST yields sorted keys.

Ordinary BST operations take O(h), where h is tree height. Because h may equal n − 1, an unbalanced BST can have linear-time operations. Rotations preserve inorder order while changing local structure. AVL trees enforce a balance factor of −1, 0, or 1 at every node. Red–black trees use color and black-height invariants to guarantee logarithmic height with generally flexible updates.

Balanced trees are valuable implementations of ordered maps and sets because they combine predictable logarithmic operations with sorted iteration, range queries, predecessor, and successor operations. Choosing between trees, hash tables, and external-memory indexes should depend on workload, ordering requirements, memory behavior, and persistence needs.

Key Terms

Tree: A connected hierarchical structure of nodes and edges.

Root: The unique node with no parent.

Leaf: A node with no children.

Depth: Number of edges from the root to a node.

Height: Maximum distance from a node to a descendant leaf.

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

Complete binary tree: A binary tree filled by levels, with the final level left-aligned.

Traversal: A systematic process for visiting tree nodes.

Binary search tree: A binary tree organized by an ordering relation on keys.

Inorder traversal: Traversal in left-root-right order.

Rotation: A local restructuring that preserves inorder key order.

Balance factor: Left-subtree height minus right-subtree height.

AVL tree: A BST whose node balance factors have absolute value at most one.

Red–black tree: A colored BST satisfying root, red-edge, and black-height invariants.

Black height: Number of black nodes on a path to a descendant null leaf.

Ordered map: A key–value collection supporting sorted operations.

Successor: The smallest key greater than a specified key.

Range query: A query returning keys within a specified interval.

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

Review Questions

Short Answer Questions

1. What is the difference between the height and depth of a node?
2. Why does inorder traversal of a BST produce sorted keys?
3. What are the three cases of BST deletion?
4. State the AVL balance-factor condition.
5. Name the five standard red–black tree invariants.

Long Answer Questions

1. Explain preorder, inorder, postorder, and level-order traversal, including a suitable application for each.
2. Describe BST insertion and deletion and analyze their time complexity in terms of tree height.
3. Explain how a right rotation preserves the BST ordering invariant.
4. Compare AVL trees and red–black trees in terms of balance, metadata, and workload suitability.
5. Explain how a balanced tree supports an ordered map and a range query.

Analytical / Application Questions

1. A BST receives keys in increasing order. Explain the resulting shape and propose a structure that prevents linear-height behavior.
2. An application performs ten times as many searches as updates and requires ordered output. Would you favor an AVL tree or a red–black tree? Justify your choice and identify what measurements could change it.
3. Design the operations and invariants needed for a student-record range-query service. Compare your design with a hash-table solution.

Multiple Choice Questions with Answers

Question 1

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

A. Preorder

B. Inorder

C. Postorder

D. Level-order

Correct Answer: B. Inorder

Question 2

What is the worst-case time complexity of searching an ordinary BST with height h?

A. O(1)

B. O(log n) regardless of shape

C. O(h)

D. O(n log n)

Correct Answer: C. O(h)

Question 3

Which condition defines an AVL balance factor under the convention used in the chapter?

A. It must equal 0 at every node

B. Its absolute value must be at most 1

C. It must always be positive

D. It must equal the node degree

Correct Answer: B. Its absolute value must be at most 1

Question 4

Which operation is used for a left-left AVL imbalance?

A. Left rotation at the unbalanced node

B. Right rotation at the unbalanced node

C. Two left rotations

D. No restructuring

Correct Answer: B. Right rotation at the unbalanced node

Question 5

What does a BST rotation preserve?

A. The exact shape of the tree

B. The inorder key order

C. The color of every node

D. The height of every subtree

Correct Answer: B. The inorder key order

Question 6

Which red–black rule prevents a red node from having a red child?

A. Every leaf is red

B. The root must be red

C. Red nodes cannot have red children

D. All paths contain no black nodes

Correct Answer: C. Red nodes cannot have red children

Question 7

A complete binary tree is characterized by which property?

A. Every node has exactly two children

B. All leaves have equal depth

C. All levels except possibly the last are full, and the last is left-aligned

D. Keys are always sorted

Correct Answer: C. All levels except possibly the last are full, and the last is left-aligned

Question 8

What is the typical complexity of reporting k values in a balanced-tree range query, including search overhead?

A. O(k²)

B. O(log n + k)

C. O(n log n + k)

D. O(1)

Correct Answer: B. O(log n + k)

Question 9

Which structure naturally supports predecessor and successor queries while maintaining sorted order?

A. A balanced search tree

B. An unordered stack

C. A basic queue

D. A hash table without auxiliary ordering

Correct Answer: A. A balanced search tree

Question 10

In a BST node with two children, which replacement commonly reduces deletion to a one-child or leaf case?

A. The root of the entire tree

B. The inorder successor

C. An arbitrary leaf

D. The node's parent regardless of key order

Correct Answer: B. The inorder successor