Due on Thursday 16th April

You may work in pairs for this assignment. For those questions requiring programming, plan and think out carefully before you start programming.

Question 1

Write an implementation of AVL trees as described in the lecture notes (to ecomomise on time, you need only implement insertion, not deletion). You should use your own (not the Java API) classes for trees and tree iterators as needed. Test your code on a collection of People objects.

Question 2

Write an implementation of B trees as described in the lecture notes (to ecomomise on time, you need only implement insertion, not deletion). You should use your own (not the Java API) classes for trees and tree iterators as needed. Test your code on a collection of People objects.

Question 3

Since a binary search tree with n nodes has (n+1) null references, half the space allocated in a binary search tree for link information is wasterd. Suppose that if a node has a null left child we make its left child link to its inorder predecessor, and similarly for a null right child (to its inorder successor). Such a tree is said to be 'threaded, the extra links being called 'threads'.

1. How can we distinguish such threads from real child links?
2. Write a program to implement such a tree, allowing insertion and deletion of values.
3. What are the advantages of such trees?