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.