Lecture 9: Augmentation

Lecture 9 Augmentation 6.046J Spring 2015 Lecture 9: Augmentation This lecture covers augmentation of data structures, including • easy tree augmentation • order-statistics trees • finger search trees, and • range trees The main idea is to modify “off-the-shelf” common data structures to store (and update) additional information. Easy Tree Augmentation The goal here is to store x.f at each node x, which is a function of the node, namely f (subtree rooted at x). Suppose x.f can be computed (updated) in O(1) time from x, children and children.f . Then, modification a set S of nodes costs O(# of ancestors of S) to update x.f , because we need to walk up the tree to the root. Two examples of O(lg n) updates are • AVL trees: after rotating two nodes, first update the new bottom node and then update the new top node • 2-3 trees: after splitting a node, update the two new nodes. • In both cases, then update up the tree. Order-Statistics Trees (from 6.006) The goal of order-statistics trees is to design an Abstract Data Type (ADT) interface that supports the following operations • insert(x), delete(x), successor(x), • rank(x): find x’s index in the sorted order, i.e., # of elements < x, • select(i): find the element with rank i. 1 Lecture 9 Augmentation 6.046J Spring 2015 We can implement the above ADT using easy tree augmentation on AVL trees (or 2-3 trees) to store subtree size: f (subtree) = # of nodes in it. Then we also have x.size = 1 + c.size for c in x.children. As a comparison, we cannot store the rank for each node. In that case, insert(−∞) will change the ranks for all nodes. rank(x) can be computed as follows: • initialize rank = x.left.size + 1 1 • walk up from x to root, whenever taking a left move (x → x' ), rank += x' .left.size + 1 x' x select(i) can be implemented as follows: • x = root • rank = x.left.size + 1 2 • if i = rank: return x • if i < rank: x = x.left • if i > rank: x = x.right, i −= rank Finger Search Trees The goal of finger search trees [Brown and Tarjan, 1980] is that, if we already have node y, we want to search x from y in O (lg |rank(y) − rank(x)|) time. Intuitively, we would like the search of x to be fast if we already have a node y that is close to x. One idea is to use level-linked 2-3 trees, where each node has pointers to its next and previous node on the same level. 1 2 omit the +1 term if indices start at 0. same as above. 2 Lecture 9 6.046J Spring 2015 Augmentation The level links can be maintained during split and merge. split new merge delete We store all keys in the leaves. Non-leaf nodes do not store keys; instead, they store the min and max key of the subtree (via easy tree augmentation). Then the original top-down search(x) (without being given y) can be implemented as follows: • start from the root, look at min & max of each child ci • if ci . min ≤ x ≤ ci . max, go down to ci • if ci . max ≤ x ≤ ci+1 . min, return ci . max (as predecessor) or ci+1 . min (as successor) search(x) from y can be implemented as follows. Initialize v to the leaf node containing y (given), and then in a loop do • if v. min ≤ x ≤ v. max (this means x is in the subtree rooted at v), do top-down search for x from v and return • elif x < v. min: v = v.prev (the previous node in this level) • elif x > v. max: v = v.next (the next node in this level) • v = v.parent Analysis. We start at the leaf level, and go up by 1 level in each iteration. At step i, level link at height i skips roughly ci keys (ranks), where c ∈ [2, 3]. Therefore, if |rank(y) − rank(x)| = k, we will reach the subtree containing x in O(lg k) steps, and the top-down search that follows is also O(lg k). 3 Lecture 9 Augmentation 6.046J Spring 2015 Orthogonal Range Searching and Range Trees Suppose we have n points in a d-dimension space. We would like a data structure that supports range query on these points: find all the points in a give axis-aligned box. An axis-aligned box is simply an interval in 1D, a rectangle in 2D, and a cube in 3D. To be more precise, each point xi (for i from 1 to n) is a d-dimension vector xi = (xi1 , xi2 , . . . , xid ). Range-query(a, b) takes two points a = (a1 , a2 , . . . , ad ) and b = (b1 , b2 , . . . , bd ) as input, and should return a set of indices {i | ∀j, aj ≤ xij ≤ bj }. 1D case We start with the simple case of 1D points, i.e., all xi ’s and a and b are scalars. Then, we can simply use a sorted array. To do range-query(a, b), we simply perform two binary searches for a and b, respectively, and then return all the points in between (say there are k of them). The complexity is O(lg n + k). Sorted arrays are inefficient for insertion and deletion. For a dynamic data struc­ ture that supports range queries, we can use finger search tree from the previous section. Finger search trees support efficient insertion and deletion. To do rangequery(a, b), we first search for a, and then keep doing finger search to the right by 1 until we exceed b. Each finger search by 1 takes O(1), so the total complexity is also O(lg n + k). However, neither of the above approaches generalizes to high dimensions. That’s why we now introduce range trees. 1D range trees A 1D range tree is a complete binary search tree (for dynamic, use an AVL tree). Range-query(a, b) can be implemented as follows: • search(a) • search(b) • find the least common ancestor (LCA) of a and b, vsplit • return the nodes and subtrees “in between”. There are O(lg n) nodes and O(lg n) subtrees “in between”. Analysis. O(lg n) to implicitly represent the answer. O(lg n + k) to output all k answers. O(lg n) to report k via subtree size augmentation. 4 Lecture 9 6.046J Spring 2015 Augmentation find(a) find(b) Figure 1: 1D range tree. Range-query(a, b) returns all hollow nodes and shaded subtrees. Image from Wikipedia http://en.wikipedia.org/wiki/Range_tree 2D range trees A 2D range tree consists of a primary 1D range tree and many secondary 1D range trees. The primary range stores all points, keyed on the first coordinate. Every node v in the primary range tree stores all points in v’s subtree in a secondary range tree, keyed on the second coordinate. Range-query(a, b) can be implemented as follows: • use the primary range tree to find all points with the correct range on the first coordinate. Only implicitly represent the answer, so this takes O(lg n). • for the O(lg n) nodes, manually check whether their second coordinate lie in the correct range. • for the O(lg n) subtrees, use their secondary range tree to find all points with the correct range on the second coordinate. Analysis. O(lg2 n) to implicitly represent the answer, because we will find O(lg2 n) nodes and subtrees in secondary range trees. O(lg2 n + k) to output all k answers. O(lg2 n) to report k via subtree size augmentation. Space complexity is O(n lg n). The primary subtree is O(n). Each point is dupli­ cated up to O(lg n) times in secondary subtrees, one per ancestor. 5 Lecture 9 Augmentation 6.046J Spring 2015 d-D range trees Just recurse: primary 1D range tree → secondary 1D range trees → tertiary 1D range trees → · · · Range-query complexity: O(lgd n + k). Space complexity: O(n lgd−1 n). See 6.851 for Chazelle’s improved results: O(lgd−1 n + k) range-query complexity ( )d−1 and O n lglglgnn space complexity. 6