Program Design II (PK2)

SML Assignment 5 of Spring 2006

AVL Trees

Specify and realise an abstract datatype for AVL trees:
  1. 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.
  2. 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!
  3. 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.


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: