|COMP1011 Exercises for Week 13|
|Computing 1A 05s2||
Fri 21 Oct 2005 16:03
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:
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.
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