15-451 Algorithms 9/23/09
RECITATION NOTES
* B-trees and treaps
* Go over practice quiz
=======================================================================
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
=========================
* Remind students of the definition: keys are in BST order, and
priority values are in heap order (if v is a child of u, then
priority(v) > priority(u).
* Algorithm: insert new (key,prio) pair as if doing usual BST
insertion, and then do tree rotations (if needed) to bring up the new
node until the heap condition is satisfied.
* Do an example. You can have students make up (key, priority) pairs
and then insert them in and do the rotations. Remind students of how
tree rotations work.
* Intuition to keep in mind is that tree will look *as if* we inserted
in order of increasing priority. So, if we set priorties at random,
this will look just like the recursion tree of randomized quicksort.
* The lecture notes contain an argument showing that if nodes are
given random priority values, then the treap will have depth O(log n)
with high probability. If you want you could do this (see lecture
notes for details). Maybe better to first go over old quiz, and then
get back to this if you have time.