Program Design II (PK2)
SML Assignment 5 of Spring 2006
AVL Trees
Specify and realise an abstract datatype for AVL trees:
- Declare an abstract datatype, denoted 'a avlTree, where
every node contains a pair of type int * 'a, whose first slot
is for the key and second slot is for the corresponding satellite
data. A node may also contain the height or balance factor of the
tree rooted at it.
- Implement the function insert: (int * 'a) -> 'a avlTree
-> 'a avlTree, which takes an element e of type
int * 'a as "first" argument, an AVL tree t with
n elements as "second" argument, and returns, arguably in
O(lg n) time, a new AVL tree that is t into
which e has been inserted. Note that calling a
height function will add an overhead of Θ(n)
time and thus make insertion in O(lg n) time
impossible!
- Implement the function inOrder: 'a avlTree -> (int * 'a)
list, which returns the in-order walk, represented as a list, of
the AVL tree given as argument.
Submission
Your solution, prepared in compliance with the ethics rules of the course, must be
submitted by the published deadline via the course manager system, and
shall contain:
- SML code for Questions 1 to 3 above, in a .sml file, executable
under Moscow ML version 2.01, and documented, in English,
according to the coding
convention of the course.