Deadline: 29th May.

In this lab you will implement red-black trees in Haskell. The goal of the lab is to:

  • let you compare the functional and object-oriented approaches to programming,

  • let you practise defining modules and abstract data types in Haskell, and

  • let you practise defining recursive functions over recursive data structures.

The task

You will define and test an implementation of red-black trees. Your code will consist of two files, RedBlackTree.hs and Main.hs:

  • RedBlackTree.hs is the red-black tree itself. It should be implemented as a Haskell module and export the same functions as BinSearchTree and AVLTree in the Haskell compendium. It should also export the following two functions:

    • size :: RBTree a –> Int, which returns the number of nodes in the tree;

    • maxheight :: RBTree a –> Int, which returns the height of the tree, that is, the length of the longest path from the root to a leaf.

    The function checkTree is already defined for you. It checks that a tree fulfils all the requirements (i.e. satisfies the invariant) of a red-black tree. Unfortunately, it is not yet fully implemented. You need to complete the following helper functions:

    • isSorted :: Ord a => [a] –> Bool, which checks that a list is sorted;

    • checkRedParents : RBTree a –> Bool, which checks that all red nodes only have black children.

    One function in RedBlackTree.hs is optional: you don’t need to implement remove, but you must implement all other functions!

  • Main.hs is the main program. It should read in words from standard input and make a tree from them. Then it should compute and print out the tree’s size (n) and height (h), the optimal height (h' = ⎡log2(n+1)⎤-1), and the ratio (h/h') between the actual and optimal height. (In a correct implementation of red-black trees, the ratio should never be greater than 2.) It should also test the tree with the function checkTree and print the result. Finally, it should print the first 20 words in the tree in dictionary order.

    Example output from Main.hs with swahili-small.txt:

    Size: 65317
Height: 24
Optimal height: 15
Height / Optimal height: 1.6
checkTree: True
First 20 words: A A A A A A A A A A ABP AC AC AD AD AD AD ADLugha ADNa ADR

    The words in the input data are separated with spaces or newlines. The easiest way to read them in is with the standard functions getContents and words.

Testing

First try some small examples, which should involve rotations. One example you could try is the sentence "The quick brown fox jumps over the lazy dog".

You must also use the test program, CheckInsert.hs. This program builds trees from all possible permutations of lists up to length 10. Each tree is then tested if it satisfies the invariant by calling the function checkTree.

Then test with the following two files:

You can download all files in one go as this big zip file.

Useful links

Submission

Submit Main.hs and RedBlackTree.hs to Fire. Your code should compile without warnings. It must also pass the testing section above. All function definitions should be adequately commented. Give the time complexity of each function. Also comment how you modify the tree in insert — say what you do and why.