COMP1011 Exercises for Week 13
Computing 1A 05s2 Last updated Fri 21 Oct 2005 16:03

Tute Exercises Week 13

AVL Trees

We implemented AVL trees in Haskell using the following data type definition:

type Balance = Int

data AVLTree a = Node Balance a (AVLTree a) (AVLTree a)
               | Leaf
Before attempting to solve the programming exercise, you should try to answer the following questions:

Write a function checkAVL:: Ord a => AVLTree a -> Bool which checks whether a tree is an AVL tree. It should return True if and only if the balance stored in each node is in the legal range, it is actually the correct value (that is, the difference between the depth of the left and the right subtree), and the elements are ordered.


(a)       Node 2 5               (b)   Node 2 5        (c)  Node 0 5
         /        \                   /       \            /        \
       Leaf      Leaf             Node 1 3    Leaf      Leaf        Leaf
                                 /        \
                             Node 0 2    Leaf
                             /       \
                          Leaf      Leaf
(a) is an AVL tree, but the balance value is incorrect, (b) is not AVL since the left subtree has depth 2, the right depth 0, and (c) is a correct AVL tree.

Write an auxilliary function that simply checks whether a tree is ordered first.

Multiway Branching Trees

The trie structure discussed in the lecture is a variant of multiway branching trees (also called a rose trees). The general type for such tree is

data RTree a = Node a [RTree a]

Discuss in which ways such trees generalise binary trees. Implement a function

mapRTree :: (a -> b) -> RTree a -> RTree b