AD1 -- SML Assignment 5

Goal of Assigment

To start the implementation of an abstract datatype for AVL-tree. The type of it should be 'a avlTree. Every node should contain a tuple of type int * 'a, whose first element in the tuple is a key, which is an integer, and the second element in the tuple is a satellite data corresponding the key.

Implement the function insert: (int * 'a) -> 'a avlTree -> 'a avlTree, which takes an element of type int * 'a as the first argument, an AVL-tree with n elements as the second argument, and returns, a new AVL-tree that is the given tree into which the input element was inserted. The time complexity of this function should be O(lg n)

Implement the function inOrder: 'a avlTree -> (int * 'a) list, which takes a AVL-tree as argument and returns the in-order walk, represented as a list, of the AVL-tree.


Your report complying with ethics rules of the course should be handed in latest deadline at 08:14 on 07 Mar, lesson on 12 March via the online course manager system, and should contain: