15-451 MINI #3 Spring 2007

This mini is due via *email* to your TA, by midnight Tuesday, February 20.
Please use the subject line "15-451 MINI #3" in your email.
Your solutions should be submitted IN THE BODY of the email. 
No attachments please.
Include your name and andrew ID at the top of your solutions.

1. Explain how to find the predecessor of a given key stored in a B-tree.
  

2. 
  (a) Draw a treap containing the following (key, priority) pairs:
    {(A,5),(B,11),(C,2),(D,1),(E,40),(F,13),(G,7),(H,6),(I,41)}
	Feel free to just do an ascii drawing.
	For each of the above integers, if x<y, then x has a lower priority than y.

  (b) Prove that it is always possible to construct a treap for any set of (key, priority) pairs. 
      Furthermore, show that if the keys and priorities are distinct then this treap is unique.