|COMP1011 Exercises for Week 13|
|Computing 1A 05s2||
Fri 21 Oct 2005 16:03
In the lecture, we discussed how to insert into AVL trees preserving the order of the elements as well as the AVL property. In each recursive iteration of the insertion function, it is necessary to check whether the new balance is still between -1 and 1. If this is not the case, the tree has to be adjusted by rotating elements to the left or to the right. For right rotation, all possible cases are displayed in the figure in the lecture notes. Complete the definition of insertAVLTree. For rightRotate you can simply follow the diagrams in the lecture notes. You might find it useful to draw similar diagrams to analyse the possible cases of leftRotate (they are symmetric to those of rightRotate).
NB: Put this part of the lab into a second module
module Lab12_AVL where type Balance = Int data AVLTree a = Node Balance a (AVLTree a) (AVLTree a) | Leaf deriving(Show) -- insert a new element into an AVL tree insertAVLTree:: (Ord a, Show a) => a -> AVLTree a -> AVLTree a insertAVLTree a t = fst (insertAVLTree' a t) -- insert new element into AVl tree, returns 'True' as a -- second parameter if the depth of the new tree is bigger -- than the depth of the original tree insertAVLTree':: (Show a, Ord a) => a -> AVLTree a -> (AVLTree a, Bool) insertAVLTree' x Leaf = (Node 0 x Leaf Leaf, True) insertAVLTree' x (Node balance y tree1 tree2) | x < y = let (tree1', incDepth) = insertAVLTree' x tree1 in if incDepth then -- depth of tree1' bigger than depth of tree1': -- adjust balance, call rotate to adjust tree -- if necessary rotate (Node (balance+1) y tree1' tree2) else -- depth of new tree is same as that of -- original tree (Node balance y tree1' tree2, False) | x > y = .... -- rotate assumes that balance has been updated -- balance == 2 -> right rotate -- balance == -2 -> left rotate -- balance == 1 -> tree is AVL, depth of tree changed -- balance == -1 -> tree is AVL, depth of tree changed -- balance == 0 -> tree is AVL, depth of tree did not change rotate:: Show a => AVLTree a -> (AVLTree a, Bool) rotate tree@(Node bal x t1 t2) | bal == 2 = rightRotate tree | bal == -2 = leftRotate tree | otherwise = (Node bal x t1 t2, bal /= 0) rotate tree = error "rotate: called on empty tree!" -- Follows the pattern of Figure 3 in the lecture notes -- single or double shift depending on balance of -- root node of left subtree -- -- returns True as second value if the depth of the -- original tree (i.e., before *insertion*, not before -- rotation) is less the depth of result. -- (Compare to the diagrams in the lecture notes. -- Original tree has depth n+1) rightRotate:: Show a => AVLTree a -> (AVLTree a,Bool) -- single rotate: rightRotate (Node 2 x (Node 0 y treeA treeB) tree2) = (Node (-1) y treeA (Node 1 x treeB tree2), True) rightRotate (Node 2 x (Node 1 y treeA treeB) tree2) = ...... -- double rotate: rightRotate ..... leftRotate:: Show a => AVLTree a -> (AVLTree a, Bool) -- single rotate: .... -- double rotate: .....
When you have completed the above exercise show it to your tutor for this week's core mark.
The Trie data structure is useful to store the words from a dictonary. In contrast, the trees we looked at previously, where each node value represents one element of the collection stored, only a single letter of a word is stored in each node. In the lecture, we implemented the functions addWord and checkWord as follows:
data Dictionary = Node Bool [(Char, Dictionary)] deriving (Eq, Show) -- Checks if word is in dictionary -- checkWord :: String -> Dictionary -> Bool checkWord "" (Node isEnd _) = isEnd -- may a word end here? checkWord (c:cs) (Node _ dicts) = case lookup c dicts of Nothing -> False -- character not in trie Just dict -> checkWord cs dict -- check rest of word -- Add a new word to dictionary -- addWord :: String -> Dictionary -> Dictionary addWord "" (Node isEnd dicts) = Node True dicts addWord str (Node isEnd dicts) = Node isEnd (addWordList str dicts) addWordList:: String -> [(Char, Dictionary)] -> [(Char, Dictionary)] addWordList (c:cs)  = [(c, addWord cs emptyDict)] addWordList (c:cs) (dict:dicts) = let (dictChar, rest) = dict in if c == dictChar then (dictChar, addWord cs rest) : dicts else dict : addWordList (c:cs) dicts -- Representation of an empty dictionary -- emptyDict :: Dictionary emptyDict = Node False 
Implement a function dumpDictonary :: Dictionary -> [String] which extracts all the words of a dictonary and returns them as a list of strings.
When you have completed the above exercise show it to your tutor for this week's advanced mark.