RECITATION NOTES 15-451 Algorithms 09/29/04 Plan: * Go over quiz * Material related to recent lectures. ======================================================================= Quiz: 1. recurrences. (go through them or ask students to explain) 2. asymptotic analysis. ditto. 3. quicksort. ditto B-trees ======= Have the class work out the result of inserting A,B,C,D,E,F,G,H,I into an initally empty B-tree with t=2 (i.e., a 2-3-4 tree). For instance, after the first 3 letters you just have one node. Then, the next insert brings the B up, and the D goes in to the leaf with the C. E goes into the leaf, and then F brings up the D. At the very end, the "I" should cause the root to get split. Treaps and tree rotations ========================= Might be good to do an example. You can have students make up (key, priority) pairs and then insert them in and do the rotations. Auxiliary information in search trees: ===================================== By adding extra information to the nodes of a binary search tree, it's often possible to perform other operations you might be interested in. However, the data you add has to have two properties: (1) it's sufficient to solve the problem you want to solve (2) the values of the data in a node can be maintained efficiently. E.g., what if we want to do the following operations: - output the kth smallest element (let's assume all keys are distinct) - do a version of lookup(x) that tells us the rank of x (how many keys are smaller than x). If we had fixed set of data, this would be easy. We just make a sorted array. To output the kth smallest element, we just output A[k]. To get the rank of x, we just do binary search to find it, and then output which location it's in. How could we do this with search trees, if we want to do inserts too? Here would be a *bad* way of solving the problem: have each node store the rank of its key. Why is this bad? Because if you insert a new key (that, say, is smaller than everything else) you may have to update *everyone's* rank. So we don't have property (2). What's a better way? One thing we can do is store the size of the subtree rooted at each node in that node. - how do we use this to solve the problems? - how do we maintain these when we do an insertion or tree rotation?