Tutorial Solutions Week 04

typedef struct HeapRep {
   Item *items;  // array of Items
   int  nitems;  // #items in array
   int  nslots;  // #elements in array
} HeapRep;
typedef HeapRep *Heap;

Heap h;  Item it;
h = newHeap(10);
insert(h, 10);
insert(h, 5);
insert(h, 15);
insert(h, 3);
insert(h, 16);
insert(h, 13);
insert(h, 6);
it = delete(h);
insert(h, 2);
it = delete(h);
it = delete(h);
it = delete(h);
it = delete(h);
it = delete(h);

Repeat the above sequence of insertions an deletions, but this time draw the heap as a binary tree, with the highest value at the root and the values decreasing as you move down any branch.

Exercise 2

Balanced Trees

Derive a formula for the minimum height of a BSTree containing n nodes. You might find it useful to start by considering the characteristics of a tree which has minimum height. The following diagram may help:

Exercise 3

Balanced Trees

Explain how we could globally balance a binary search tree using the partition function.

Exercise 4

Splay Tree4

• What is the difference between splay tree insertion and root insertion?
• Insert items with the keys 10, 9, 8, 7, 11
  • in an empty binary search tree

    	    	10
    	      /   \ 
    	     9     11
    	   /
    	  8
    	 /
    	7
    	

  • binary search tree with root insertion

    		    	11
    		      /    
    		     7    
    		      \
    		       8
    		        \
    		         9
    		          \
    		          10
    		

  • a splay tree

          11
         /
        8
       / \
      7   10
         /
        9
    				

  and draw the resulting trees.