Lab Exercises Week 13

AVL Trees and Tries

Ex 1:

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 called Lab12_AVL.

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.

Ex 2:

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.