* Monday: Columbus Day. Wednesday: balanced tree schemes. * PS3 is due on Monday! * Today: augmenting data structures. -------------------------------------------- DYNAMIC ORDER STATISTICS Suppose I want to maintain a dynamic set (insert, delete, search) with the additional capability of doing order-statistic queries whenever I want. So you get a sequence of requests of the form insert(3) insert(2) insert(12) delete(2) insert(7) select(2) --> 7 delete(7) select(2) --> 12 and so forth. How do we do this (with good guaranteed worst-case behavior)? One solution: use a balanced tree scheme -- say a 2-3 tree. When you get a select query, use DETERMINISTIC-SELECT to find the appropriate element of the current set. Running times: -- insert O(log n) -- delete O(log n) -- search O(log n) -- select O(n). [btw, what's n?? say, maximum size of the set. upper bounded by the number of operations.] We can do better! The idea is to AUGMENT the data structure to allow select queries to be fast. (We talked about this once before, briefly, with regards to making Max() fast if you store a dynamic set as an unsorted array. Maintain the maximum as a separate value. Whenever you insert, update normally. Whenever you delete, update max by doing a full pass over the data. (still only O(n)). ) For intuition, how would you do this with a regular old BST? I want to add some data to each node that will let me find the ith largest element. What should I add? --> include a count of the number of elements "beneath" each node in the tree! So, how do I do select? Basically it's just regular-old BST-Search(), but with the counts instead. SELECT(i,x) if count(x.left) = i - 1 then return x. if count(x.left) < i - 1 then select(i-count(x.left)-1, x.right) if count(x.left) > i - 1 then select(i, x.left). How do we maintain sizes as we insert and delete? Easy! As you walk down the insertion path, just increment count. As you walk down the deletion path, just decrement count. Now, I want to do this using O(log n) insert/delete time _in the worst case_. Let's use a balanced tree scheme -- say a 2-3 tree. What do I do now? Well, select() is still just the same as before. (Though you have to translate "x.left" and "x.right" to be the right things.) Suppose that while inserting I have to do a split. Say: [ ] / \ [ ] A / | | \ B C D E ===> [ ] / | \ [ ] [ ] A / | | \ B C D E What does this do to the counts? Well, something easy to keep track of. So you just keep track of it, and then all is well. For red-black or AVL trees, you just have to show how to maintain the auxilliary data through a rotation: y w <-- count = y's old count w Z ----> V y <-- y's count = V X X Z 1 + count(X) + count(Z) --------------------------- --------------------------------------------- MEMORY ALLOCATION Design a data structure for memory management for an operating system. I.e., you need to handle allocation and deallocation requests: malloc(size) <-- give me a free block of size size. free(x) <-- mark block x as free. (x.size, x.address) Actual (dumb) implementations: * use an ordered (by address) linked list. * to allocate, walk over the list until you find a block large enough for requested size. O(n) Let's use _first fit_: malloc(size) should find the minimum address x such that the range (x,x+size) is free. E.g., (0,3) (15,20) (22,32) (35,55) (65,77) (80,82) (83,90) malloc(2) --> 0. malloc(5) --> 15. malloc(12) --> 35. Let's implement this in O(log N) time, eh? We'll use an augmented red-black tree (or other balanced tree). A node will store: -- key=beginning of block, end of block, left, right. -- size of maximum free block in subtree. malloc == find minimum node with enough free space. FIND(size,T) if size-max-free(T) < size, then return NIL. if size-max-free(left[T]) > size, return FIND(size,left[T]) else if (end - beginning > size) block = [beginning, beginning + size] delete [beginning, end] from tree if beginning + size + 1 < end insert [beginning + size + 1, end] into tree. return block. else return FIND(size,right[T]). how do we insert/delete nodes from the red-black tree in time O(log N)? well, it's easy to maintain through a rotation. y w <-- max = y's old max. w Z ----> V y <-- y's max = largest of V X X Z max(X),max(Z),size(y). FREE(start,size,T) if (end(Predecessor(start+size+1)) >= start), then fail // you're freeing a free block, dolt! blockstart = start blockend = start + size if end(Predecessor(start)) == start-1 then blockstart = beginning(Predecessor(start)) delete(Predecessor(start)) if beginning(Successor(blockend)) == blockend+1 then blockend = end(Successor(blockend)) delete(Successor(blockend)) insert [blockstart, blockend] into tree. ---------------------------------------------------- POPULATION TRACKING You are given a (dynamic) stack of birth and death certificates. At any point, you want to answer the question: considering the stack currently in front of you, what was the maximum living population at any time? [you _can_ go negative, i.e., want to find the maximum over all times t of (# birth certificates dated <= t) - (# death certificates dated <= t). or you can consider a guarantee that if you have the death certificate, then you also have the birth certificate. it turns out not to matter for this problem.] assume distinct dates. We can achieve O(1) insertion, deletion. O(n log n) query. (sort by date; keep a running tally.) Let's make everything O(log n) or better. Use a balanced BST. ADD (birth or death): insert the date into the tree. if birth, tag as a +1. if death, tag as a -1. DELETE: delete the node from the tree. intuition: if we look at the tags of the sorted sequence of dates: v[1], v[2], ... then the population after the first i "events" is v[1] + v[2] + ... + v[i]. we want to maximize this value. how do we do that? we store at each node in the tree: * date, left, right. * tag (+/- 1) * sum of all tags in the subtree rooted at the node. * maximum "prefix" population in the subtree rooted at the node. i.e., if we have v[l], v[l+1], ... v[r] in the subtree we store the maximum v[l] + v[l+1] + ... + v[i]. how do we maintain these with rotation? z X Y sum-of-tags(z) = tag of z + sum-of-tags(X) + sum-of-tags(Y). max-prefix(z) = max(max-prefix(X), sum-of-tags(X) + tag(z), sum-of-tags(X) + tag(z) + max-prefix(Y)). how would you recover the actual date? also store * index achieving max-prefix. easy to maintain, and then the index stored at the root is the best. So we have O(log N) insert and delete, and O(1) [!] query.