A tree organizes elements through parent-child relationships, giving each connected component a root and avoiding cycles. Its usefulness depends on the operation being optimized: parent pointers represent disjoint-set partitions, while search trees support dynamic dictionary operations. section 5.5.2 section 6.1.1
Tree implementations in these applications rely on a few practical ideas:
- Represent each disjoint-set element by its parent; initialize every element as its own parent, making each element a root. section 5.5.2
- Find a partition by following parent links recursively until an element points to itself; the number of calls equals the tree height. section 5.5.2
- Use a balanced search tree for dynamic dictionary operations such as contains, insert, and remove, with average and maximum traversal of O(log n) nodes. section 6.1.1
Parent-pointer partitions
Suppose elements are stored in parentsMap. A root points to itself. Calling findPartition on a non-root follows its parent recursively to that root, while merge connects the roots of two distinct partitions. Without assumptions about tree shape, finding a root can take time proportional to the number of elements in the worst case. section 5.5.2
Listing 5.6 Tree-based solution, findPartition
class DisjointSet
#type HashMap[Element, Tree[Element]]
parentsMap
function findPartition(elem) #1
throw-if (elem == null or not parentsMap.has(elem))) #2
parent ← this.parentsMap[elem] #3
if parent != elem then #4
parent ← this.findPartition(parent) #5
return parent #6
Trace the recursive findPartition implementation from input validation through parent lookup, root detection, recursive ascent, and return. section 5.5.2
Figure 6.1 A BST storing (part of) a dictionary, and the steps to search the word “antic”. In this example, it’s a miss because the word was not stored in the tree shown.
Inspect a binary search tree used as part of a dictionary and follow the search for the missing word “antic.” section 6.1.1
