COMP1011 Exercises for Week 13
Computing 1A 05s2	Last updated Fri 21 Oct 2005 16:03 Mail cs1011@cse.unsw.edu.au

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
               deriving(Show)

Before attempting to solve the programming exercise, you should try to answer the following questions:

How many elements does an augmented binary tree (with elements only in the nodes) of depth n have at least, how many at most?
How many elements does an AVL tree (as defined in the lecture) of depth 3 have at least, how many at most?
What is the advantage of AVL trees over regular ordered binary trees?

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.

Examples:

(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