Tutorial Solutions Week 08

Exercise 1

Explain how we could globally balance a binary search tree using the partition function. We can use partition to move the median element of a given tree to the root of the tree. 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 2

• 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.
• Explain the concept of 'amortisation' in the context of binary search trees and splay 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.
• Insert the same keys into a randomised binary search tree - get someone to flip a coin each time a decision needs to be made as to whether the node is inserted at the leaf or root of the given subtree. Heads can mean root, tails can mean leaf. Note: in the actual implementation from lectures the probability that it is inserted at the root is approx 1/n and not just 0.5 like a coin toss. Answer will depend on coin toss :)

Exercise 3

Draw a hash table of size 13. Use the hash function "k%13" and insert the keys: 5, 29, 32, 0, 31, 20, 23 and 18 into your table (in that order) using the following strategies for handling collisions.

1. Chaining
2. Linear Probing
3. Double Hashing with a second hash function "7 - (k%7)". (Why would a second hash function such as "k%7" not be very useful?)

If there is any remaining time, use it to finish any questions that you did not cover in previous weeks.

1. Chaining

   Solution

   

2. Linear Probing

   Solution

   

3. Double Hashing with a second hash function "7 - (k%7)".

   Solution

   

   (Why would a second hash function such as "k%7" not be very useful?)

   Because you would get values in the range of 0 - 6. Values of 0 would not be very useful as you would just checking indexes 0 away - ie in the same spot the original collision was in.