AD1 -- SML Uppgift 5

Börja implementationen av en abstrakt datatyp för AVL-träd. Typen på denna ska vara 'a avlTree. Varje nod ska lagra en tupel av typen int * 'a där första elementet i tupeln är en nyckel, ett heltal, och andra elementet i tupeln är satellitdata tillhörande denna nyckel. Funktionen insert: (int * 'a) -> 'a avlTree -> 'a avlTree ska ta ett element av typen int * 'a som "första" argument, ett AVL-träd med n element som "andra" argument, och returnera, i O(lg n) tid, ett nytt AVL-träd som är en utökning av det föregående innehållande det nya elementet. Funktionen inOrder: 'a avlTree -> (int * 'a) list ska returnera inorder traverseringen av ett AVL-träd.

Inlämning

Din redovisning, enligt kursens etikregler, måste lämnas in senast måndag 6 mars, klockan 08:14 (på morgonen), med hjälp av inlämningssystemet, och ska innehålla:

SML abstrakta datatypen 'a avlTree och SML funktionerna insert och inOrder, i en *.sml textfil, körbar under Moscow ML version 2.01 (det som inte är kod ska vara bortkommenterat), och dokumenteras, på engelska, enligt kursens kodkonventionerna.