Tutorial Exercises Week 08

Exercise 0

Finish any of the questions from Exercise 7 from last week if you did not get to do them.

Exercise 1

Balanced Trees

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

Exercise 2

Splay Trees

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
- binary search tree with root insertion
- a splay tree
and draw the resulting trees.
Explain the concept of 'amortisation' in the context of binary search trees and splay trees.
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.

Exercise 3

Hashtables

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.

Chaining
Linear Probing
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.