Uppgift 5 -- PK2 VT04 -- Uppsala Universitet
Uppgift 5 måste lämnas in senast måndag 17 maj klockan 10:15 (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.
- En kort beskrivning (en rad) av vad det är för fil.
- 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.