# 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.

# Hand-in

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:
- SML abstract datatype
`'a avlTree` and SML functions
`insert` and `inOrder`, in a *.sml text file, running under
Moscow ML version 2.01, and commented, in English, complying with
coding convention.