Lecture 9: Augmentation: Range Trees

What this lecture covers

This lecture asks how far you can push a balanced search tree by attaching extra information to each node. It builds from a general rule for when augmentation is "easy" (the extra field can be computed from a node's children in constant time) through order-statistic trees supporting rank and select, to two more advanced techniques: level-linked 2-3 trees for fast "finger search" between nearby keys, and range trees for answering multi-dimensional box queries.

After watching, you should be able to state the condition under which augmenting a balanced tree keeps insert and delete at O(log n), implement rank and select using subtree sizes, explain why level links with data stored at the leaves give a finger search bound of O(log d) where d is the rank difference between two keys, and describe how nesting one-dimensional range trees inside each other extends range search to two and three dimensions at a cost of one extra log factor per dimension.

Key ideas

• Easy tree augmentation: if a field x.f can be computed in constant time from a node's own data and its children's f values, then any localized update (rotation, split, merge) only needs to refresh f along a single root-to-node path, keeping updates O(log n).
• Order-statistic trees: augmenting with subtree size lets you compute rank(key) by walking up from a node and summing left-subtree sizes past every "left turn," and select(i) by walking down comparing i to the left subtree size at each node, both in O(log n).
• Why not augment with rank directly: rank changes for many nodes on a single insert (for example, inserting a new minimum shifts every other rank), so it fails the easy-augmentation condition and would cost linear time to maintain.
• Level-linked 2-3 trees: adding horizontal pointers between nodes at the same depth, maintainable in constant extra time per split or merge, sets up faster searches between two known nearby keys.
• Finger search property: searching for a key x starting from a known node containing a nearby key y should take O(log d) time, where d is the absolute difference in rank between x and y, rather than a full O(log n) search.
• Data-in-the-leaves trick: storing all keys only at the leaves (with internal nodes holding just routing information such as min/max) is necessary to make finger search work, because graph distance between rank-adjacent nodes can otherwise be Theta(log n).
• Range trees and orthogonal range search: given n points in d dimensions, preprocess them so that a query (an axis-aligned box) can be answered in O(log^d n + k) time, where k is the number of points reported.
• 1D range search via a balanced BST: given interval [a, b], following the paths to a and b down from the root and taking the "off-path" subtrees on the correct side at each branching node gives an implicit answer as O(log n) nodes and O(log n) whole subtrees.
• Nested range trees for higher dimensions: attaching, at every node of a 1D tree sorted by one coordinate, a secondary 1D range tree over the same subtree's points sorted by the next coordinate extends the query bound by one log factor per added dimension, since each point is duplicated across only O(log n) ancestor subtrees, keeping total space O(n log^{d-1} n).

Walkthrough

The general theorem for easy tree augmentation (1:03)

The lecture defines augmentation as storing, at each node x, some function f of the subtree rooted there. If x.f can be computed in constant time from the node and its children's f values, then whenever a set of nodes changes (due to data edits or tree rotations), only their ancestors need updating. Because AVL tree rotations and 2-3 tree splits happen along a single root-to-leaf path, the total update cost after any operation is O(log n).

Order-statistic trees: rank and select (9:36)

Augmenting with subtree size (computable as 1 plus the sum of children's sizes) satisfies the easy-augmentation condition. The lecture derives rank(x): walk up from x to the root, and each time you arrive at a node from its right child (a "left parent" turn), add that parent's left-subtree size plus one. It then derives select(i): walk down from the root, comparing the target rank i to the local rank of the current node (its left-subtree size plus one), moving left, right, or stopping accordingly, taking care never to recompute rank recursively (which would cost O(log^2 n)). Both run in O(log n). The lecture also explains why augmenting directly with rank instead of subtree size is a bad idea: inserting a new minimum key shifts every other node's rank, violating the locality condition.

Level-linked 2-3 trees and the finger search goal (27:00)

The lecture introduces horizontal "level link" pointers between same-depth nodes in a 2-3 tree, showing these can be maintained in constant extra time during splits and merges. The motivation is finger search: given a node already known to store key y, search for a nearby key x faster than a full O(log n) search. The target bound is O(log d), where d is the absolute rank difference between x and y, so adjacent keys are found in constant time while far-apart keys still cost at most O(log n).

Why data must live at the leaves (37:06)

A direct attempt to bound finger search by graph distance fails: two rank-adjacent keys (like a node and its predecessor) can be far apart in the tree (graph distance up to Theta(log n)), for example a root and its predecessor. The fix is to store all keys only in the leaves (a B+-tree style layout), with internal nodes augmented with the min and max key of their subtree. Ordinary search still works by comparing the target key against each child's min/max range in O(log n) time, and insert/delete still work by splitting or merging leaf-level nodes as usual.

The finger search algorithm and its analysis (46:10)

Starting from the leaf containing y, the algorithm alternates moving up to the parent and sideways along a level link, checking at each step whether the current subtree's min/max range brackets x; once it does, a normal downward search finishes the job. The key insight is that at the k-th step, the subtree being skipped over has height roughly k, hence contains a number of leaves exponential in k (between 2^k and 3^k, since 2-3 tree nodes have two or three children). Since only d keys lie strictly between x and y, the loop terminates after O(log d) iterations, and the following downward search costs the same, giving the full O(log d) bound.

Orthogonal range search and the 1D case (58:31)

The lecture turns to range trees, which preprocess a static point set in d dimensions to answer axis-aligned box queries (count or list points inside) in O(log^d n + k) time, where k is the output size. It starts with 1D: given a perfectly balanced BST and a query interval [a, b], follow the search paths to a and b, and at each point where the two paths diverge to the right (for a) or left (for b), include that node and its off-path subtree in the answer. This produces an implicit representation of the answer as O(log n) individual nodes plus O(log n) whole subtrees, which can be counted (via subtree-size augmentation) or enumerated in time proportional to the output.

Extending to 2D and 3D by nesting range trees (1:16:10)

For 2D points, the lecture builds a 1D range tree sorted by x-coordinate, then augments every node with a pointer to a second 1D range tree, sorted by y-coordinate, over exactly the points in that node's subtree. A query first finds the O(log n) nodes and subtrees matching in x, then searches each of those subtrees' y-trees for the y-range, yielding O(log^2 n) implicit answer pieces. The same idea nests a third level for 3D, costing one more log factor. Because each point belongs to only O(log n) ancestor subtrees in the primary tree, the total space overhead for the nested structures is a single extra log n factor, so d-dimensional range trees use O(n log^{d-1} n) space and answer queries in O(log^d n + k) time.

Before you watch

• Be comfortable with AVL tree and 2-3 tree operations (rotations, splits, merges) from earlier lectures, since this lecture builds directly on them.
• Recall subtree-size augmentation, if introduced in a prior course, since it is reused here as the base case before more advanced augmentation is covered.
• Review the earlier lecture's ideas about balanced search tree height and login bounds, since several arguments rely on tree height being O(log n).

Check your understanding

1. State the general condition under which augmenting a node field keeps insert, delete, and rotation costs at O(log n), and explain why augmenting directly with rank fails it.
2. Walk through how the select algorithm avoids recomputing rank at every step of its downward search, and why that matters for its runtime.
3. Why does storing keys only at the leaves matter for achieving the finger search bound, when it does not matter for ordinary search?
4. Explain why the number of leaves skipped at the k-th step of finger search grows exponentially in k, and how that leads to an O(log d) bound.
5. Describe how the 1D range search algorithm produces an "implicit" answer, and how nesting a second range tree at each node extends this to two dimensions.