Uppgift 6 -- AD1 VT04 -- Uppsala Universitet

Solve either this assignment 6 or assignment 5.

Uppgift 6 måste lämnas in senast måndag 8 mars klockan 11:59 (på morgonen). Lämna in den med hjälp av inlämningssystemet (se slutet av denna sida). Se till att läsa igenom kodkonventionerna innan du börjar. Dessa skall följas.

Uppgift

Din uppgift är att 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 som "andra" argument, och returnera 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.

Din redovisning ska innehålla:

Definitionen av den abstrakta datatypen 'a avlTree.
Implementationen av funktionen insert.
Implementationen av funktionen inOrder.

Inlämning

Överst i din fil ska följande finnas (inom kommentartecken):

Ditt namn och klass.
Om du löser uppgiften tillsammans med en annan student, ange den andra studentens namn. I så fall ska endast en av er lämna in en lösning, men båda ska meddela namn, klass och labpartner via inlämningssystemet.
Filens namn (inklusive din hemkatalogs namn; hela sökvägen alltså).
En kort beskrivning (en rad) av vad det är för fil.
Notera att alla kommentarer och all dokumentation ska vara på engelska.

Kontrollera att du hunnit ge svar på varje deluppgift.

Din inlämning ska vara körbar. Det som inte är kod ska vara bortkommenterat!

Glöm inte att alla funktioner ska dokumenteras enligt kodkonventionerna.

Hämta ett formulär för att lämna in uppgiften genom att fylla i fälten nedan.