Tutorial Solutions Week 04

Exercise 1

Heap

Consider the heap-as-array ADT given in lectures: 

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

If a heap is created to hold up to 10 Items, and Items are integer values, and higher values have higher priority, show the state of the heap after each of the following operations: 

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);

Answer:

The following shows each operation and then the state of the heap after that operation. Note that since nslots remains as 10 for the entire lifetime of the Heap, we don't show it 

Operation        nitems   [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 
h = newHeap(10);      0     -   -   -   -   -   -   -   -   -   -
insert(h, 10);        1    10   -   -   -   -   -   -   -   -   -
insert(h, 5);         2    10   5   -   -   -   -   -   -   -   -
insert(h, 15);        3    15   5  10   -   -   -   -   -   -   -
insert(h, 3);         4    15   5  10   3   -   -   -   -   -   -
insert(h, 16);        5    16  15  10   3   5   -   -   -   -   -
insert(h, 13);        6    16  15  13   3   5  10   -   -   -   -
insert(h, 6);         7    16  15  13   3   5  10   6   -   -   -
it = delete(h);       6    15   6  13   3   5  10   -   -   -   -
insert(h, 2);         7    15   6  13   3   5  10   2   -   -   -
it = delete(h);       6    13   6  10   3   5   2   -   -   -   -
it = delete(h);       5    10   6   2   3   5   -   -   -   -   -
it = delete(h);       4     6   5   2   3   -   -   -   -   -   -
it = delete(h);       3     5   3   2   -   -   -   -   -   -   -
it = delete(h);       2     3   2   -   -   -   -   -   -   -   -

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.

Answer:

It's much easier to consider the heap as a tree, e.g.

Exercise 2

Balanced Trees

Derive a formula for the minimum height of a Binary Search Tree 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:

Answer:

A minimum height tree must be balanced. In a balanced tree, the height of the two subtrees differs by at most one. In a perfectly balanced tree, all leaves are at the same level. The single-node tree, and the two trees on the right in the diagram above are perfectly balanced trees. Let us consider perectly balanced trees initially. A perfectly balanced tree of height h will contain 1 node on the first level, 2 nodes on the second level, 4 nodes on the third level, 8 nodes on the fourth level, and so on. The j th level in a perfectly balanced tree always contains 2 j-1 nodes.

The number of nodes in a perfectly balanced tree of height h = 20+21+22+...+2h-1 = 2h-1

And, by rearranging the formula, we have h = log2(n+1)

By inspection of the trees that are not perfectly-balanced above, it is clear that as soon as an extra node is added to a perfectly balanced tree, the height will increase by 1. To maintain this height, all subsequent nodes must be added at the same level. The height will thus remain constant until we reach a new perfectly balanced state.

For a tree with n nodes, minimum h = ceil(log2(n+1))

Exercise 3

Balanced Trees

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

Answer:

We move the median node of a given tree to the root of the tree by partitioning on (size/2). By having the median element at the root of the tree, we will end up with approximately the same amount of keys in the left subtree and the right subtree. If we repeat this process for every subtree in the tree, we will have a balanced tree.

Exercise 4

Splay Tree
  • 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 
      

        10
       /  \
      9    11
     /
    8
   / 
  7
    and draw the resulting trees.

    • With splay trees, whenever a operation has to walk down the spine of the tree, it improves the balance of the tree by rotation. This makes the current operation more expensive, but these extra costs are amortised since follow up operations will require less time on this structure as a consequence.