Chapter 12: Advanced Data Structures
Master advanced data structures that unlock efficient solutions to complex problems: Union Find for dynamic connectivity, Tries for prefix-based string operations, LRU Cache for O(1) eviction, and Segment Trees for range queries. These structures appear frequently in system design and competitive programming.
Chapter Overview
Advanced data structures go beyond arrays, hash maps, and trees to solve specialized problems with optimal efficiency. Each structure in this chapter addresses a specific class of problems that would be significantly harder or slower to solve with basic data structures.
Union Find (Disjoint Set Union) maintains a partition of elements into non-overlapping sets, supporting near-constant-time merge and membership queries. It is the backbone of Kruskal's algorithm, network connectivity, and image segmentation.
Trie (Prefix Tree) stores strings character by character in a tree, enabling prefix searches, autocomplete, and dictionary lookups in time proportional to the word length rather than the dictionary size.
LRU Cache combines a hash map with a doubly linked list (or Python's OrderedDict) to provide O(1) get and put operations with automatic eviction of the least recently used entry when capacity is exceeded.
Segment Tree supports both range queries (sum, min, max over a subarray) and point updates in O(log n) time, making it indispensable for problems where the underlying array changes frequently.
This chapter covers:
- Union Find: Path compression, union by rank, connected components
- Trie: Insert, search, prefix matching, and autocomplete via DFS
- LRU Cache: OrderedDict-based O(1) implementation
- Segment Tree: Build, query, and update operations
Chapter Roadmap
Click any topic to jump in
Union Find (DSU)
Path compression + union by rank gives amortized $O(\alpha(n))$ per operation.
Connected Components
Static counting via DFS/DSU; dynamic connectivity via link-cut trees.
Each tackles a different aspect
Trie
$O(L)$ insert and search for prefix queries, independent of dictionary size.
Autocomplete with Tries
DFS from prefix nodes and precomputed top-k lists for fast ranked suggestions.
Each tackles a different aspect
LRU Cache
$O(1)$ get/put via hashmap + doubly linked list (or OrderedDict).
Segment Tree
$O(\log n)$ range queries and point updates on any associative aggregate.
Union Find (also called Disjoint Set Union or DSU) is a data structure that tracks a collection of elements partitioned into non-overlapping sets. It supports two primary operations: find (determine which set an element belongs to) and union (merge two sets into one).
The naive implementation uses a parent array where each element points to its parent, with root elements pointing to themselves. Two critical optimizations make both operations run in nearly O(1) amortized time:
- Path compression: During find, make every node on the path point directly to the root
- Union by rank: When merging, attach the shorter tree under the taller tree to keep the structure flat
With both optimizations, the amortized time per operation is O(alpha(n)), where alpha is the inverse Ackermann function---effectively constant for all practical input sizes.
In this topic
Find with Path Compression
The find operation traverses parent pointers from an element up to the root of its set. Path compression flattens the tree during this traversal by making every visited node point directly to the root. This means subsequent find operations on any of those nodes complete in O(1). Without path compression, find could degrade to O(n) on a skewed tree. With it, the amortized cost drops to O(alpha(n)).
Path compression makes every node on the find path point directly to the root. Combined with union by rank, it gives amortized complexity per operation, where is the inverse Ackermann function. For all practical (even ), , so operations are effectively constant time.
Given parent = [0, 0, 1, 1, 3], what does the tree look like after calling find(4) with path compression?
Union by Rank
When merging two sets, union by rank attaches the root of the shorter tree under the root of the taller tree. The rank of a node is an upper bound on its height. If both trees have the same rank, one becomes the child of the other and the new root's rank increases by 1. This keeps the overall tree height bounded by O(log n), ensuring that even without path compression, find operations are logarithmic.
Union by rank attaches the shorter tree under the taller tree's root, which keeps the tree depth at without path compression. With both heuristics, Tarjan proved the amortized bound per operation; omitting either one degrades to amortized, and omitting both gives worst case. Rank is an upper bound on height, not exact height, since path compression only shrinks trees.
Two sets have roots A (rank 2) and B (rank 1). How does union by rank merge them?