11 Solving real problems with advanced trees
This chapter explains why advanced tree structures are essential when you want both performance and stack safety in purely functional, immutable code. Simple binary trees can degrade into deep recursion and cause stack overflows, and in-place balancing algorithms are a poor fit for immutable data. To address this, the chapter introduces two self-balancing, persistence-friendly structures with complementary goals: the red-black tree for general-purpose ordered collections and the leftist heap for efficient functional priority queues. The common thread is avoiding mutable updates while keeping operations fast through structural sharing and carefully designed balancing strategies.
The red-black tree augments a binary search tree with node colors and strict invariants: empty nodes are black, red nodes have black children, and every root-to-leaf path has the same number of black nodes. Insertions proceed like a regular BST insert, followed by localized rotations and recolorings encoded in a balance function, and the root is finally blackened; deletions are more involved but feasible in a functional setting. Building on this, the chapter implements a persistent Map that delegates to a red-black tree of comparable MapEntry objects (ordered by key), yielding thread-safe updates with data sharing and efficient lookup/updates. The design is extended with folds and ordered value extraction, and a variant supports non-comparable keys by hashing and storing collision buckets as lists, trading a rare linear scan within a bucket for broad API flexibility.
For priority queues, the chapter adopts the leftist heap: a heap-ordered tree where the minimum element resides at the root and a leftist property ensures the right spine is the shortest path. This makes find-min constant time and enables an elegant, recursion-friendly insert built on a merge operation that preserves ranks and structure. The queue-like interface exposes head (min) and tail (merge of children), supports retrieving the nth element by priority, and provides a pop operation that pairs the current head with the remaining heap. By expressing toList via unfold (and then generalizing unfold and foldLeft), the chapter shows how to derive sorted lists and reusable folds from the same abstraction. Finally, the heap is generalized to work with non-Comparable elements through an injected Comparator, keeping the API functional, safe, and efficient across broader use cases.
Figure 11.1. Insertion of integers 1 to 7 into an initially empty tree, step 1
Figure 11.2. Insertion of integers 1 to 7 into an initially empty tree, step 2
Figure 11.3. Insertion of integers 1 to 7 into an initially empty tree, step 3
Figure 11.4. Insertion of integers 1 to 7 into an initially empty tree, step 4
Figure 11.5. Insertion of integers 1 to 7 into an initially empty tree, step 5
Figure 11.6. Insertion of integers 1 to 7 into an initially empty tree, step 6
Figure 11.7. Insertion of integers 1 to 7 into an initially empty tree, step 7
Figure 11.8. A heap-ordered leftist tree, showing that each branch of an element is higher than or equal to the element itself, and each left branch rank is greater than or equal to the corresponding right branch rank.
Summary
- Trees can be balanced for better performance and to avoid stack overflow in recursive operations.
- The red-black tree is a self-balancing tree structure that frees you from caring about tree balancing.
- Maps can be implemented by delegating to a tree storing key/value tuples.
- Maps with non comparable keys must handle collisions in order to store elements with the same key representation.
- Priority queues are structures allowing elements to be retrieved by priority order.
- Priority queues can be implemented using a leftist heap, which is a heap-ordered binary tree.
- Priority queues of non comparable elements can be constructed using an additional comparator.
FAQ
What problem do self-balancing trees solve compared to plain binary search trees?
They prevent pathological height growth and stack overflows while keeping operations efficient. Plain BSTs can degrade to a linked list when data is ordered, and tree operations use two recursive branches, making tail recursion impractical. Self-balancing designs (like red-black trees) maintain near-logarithmic height so inserts, lookups, and deletes stay fast and stack-safe.What are the red-black tree invariants I need to maintain?
- The empty tree is black.- No node has a red child if it is red (no two consecutive reds).
- Every path from the root to an empty subtree has the same number of black nodes (equal black-height).
Insertion and deletion must restore these invariants via rotations and color changes.
How does insertion work in the functional red-black tree presented here?
- Insert like a normal BST, coloring the new node red.- On the way back up, rebalance by pattern-matching rotations and recolorings (a balance function replaces direct construction).
- After rebalancing, force the root to black (blacken).
This yields a balanced tree with logarithmic height.
What are the roles of balance and blacken during insertion?
- balance(color, left, value, right) detects the four classic “red parent with red child” shapes under a black parent and transforms them into a balanced, recolored subtree. It should be used instead of directly calling the node constructor.- blacken() ensures the root is black after insertion, preserving equal black-height from root to leaves.
How is deletion from a red-black tree handled in this chapter?
Deletion is more intricate than insertion. The chapter points to Germane and Might’s functional deletion algorithm for Okasaki-style red-black trees. The full Kotlin implementation is in the accompanying repository; it restores invariants through carefully structured cases and color moves during reattachment.How do we implement an immutable Map with a red-black tree?
- Store MapEntry(key, value) elements in a Tree, ordering by key.- MapEntry compares, equals, and hashes by key only; value is carried alongside.
- Map delegates plus/minus/get/contains/size to the underlying Tree, leveraging structural sharing for fast persistent updates.
This yields a thread-safe, efficient functional map.
How can the Map support non-comparable keys?
- Make MapEntry- Handle hash collisions by storing a List
- Implement plus/minus/get by retrieving the list for the hash and then filtering by actual key equality.
Why use a leftist heap for a functional priority queue?
- Heap-ordered: the smallest element is always the root, so find-min (head) is O(1).- Leftist property keeps the shortest path on the right, making merge efficient (and thus insert and delete-min).
- Suits immutable implementations: insert = merge(heap, singleton); delete-min = merge(left, right); duplicates naturally supported.
How do merge, insert, tail, and get work in the leftist heap?
- merge(h1, h2): Compare roots; make the smaller root the new root and recursively merge its right child with the other heap; swap children to maintain leftist ranks.- plus(x): merge(this, Heap(x)).
- tail(): merge(left, right) of the root, as a Result for safety.
- get(n): traverse by repeatedly taking tail n times; returns a Result to handle out-of-bounds.
The Joy of Kotlin ebook for free
