Inlämningsuppgift 2 - PK3 VT-03


Inlämningsuppgift 2 ska lämnas in senast måndagen den 2 juni. Lämna in den med hjälp av inlämningssystemet i slutet av denna sida. Läs igenom kodkonventionerna innan du börjar. Dessa skall följas.

Efter denna uppgift ska du ha kunskap om

Före uppgiften

Din inlämning

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

Se till att du hunnit ge ett svar på varje deluppgift.

Uppgift

Din uppgift är att implementera en abstrakt datatyp (ADT) 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.) De funktioner som ska finnas är insert för att stoppa in ett element i ett AVL-träd och delete för att ta bort ett element från ett AVL-träd. Det ska även finnas ett värde som representerar ett tomt AVL-träd.

insert ska vara stuvad och 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. delete ska också vara stuvad och ta en nyckel som "första" argument, ett AVL-träd som "andra" argument, och returnera ett nytt AVL-träd som innehåller samma element som det föregående förutom elementet med given nyckel. Om den givna nyckeln inte existerar i det givna AVL-trädet returneras detta utan förändring.

Vidare ska det finnas en funktion listToSearchTree: (int * 'a) list -> 'a bsTree som inte ska vara en del av din ADT. Denna ska ta en lista med element av typen int * 'a (där heltalet i tupeln är nyckeln och det andra elementet i tupeln är det data som ska lagras med nyckeln) som argument och returnera ett binärt sökträd innehållande alla element i inputlistan som uppfyller kraven på skillnad i höjd på delträd som ett AVL-träd har. Du ska alltså använda dig av din insättningsfunktion för ditt AVL-träd och skapa ett sådant innehållande alla element i listan. Därefter översätts detta träd till ett "vanligt" binärt sökträd. Ett exempel på inputdata till denna funktion är [(5,"katt"),(2,"hund"),(4,"varg"),(10,"hamster")].

Här finns en abstrakt datatyp för binära sökträd ('a bsTree) att ladda ner.

Uppgiften består av följande delmoment:

  1. Skapa en ADT för AVL-träd.

  2. Skapa ett värde som representerar ett tomt AVL-träd.

  3. Implementera en funktion, insert, för insättning av ett element i ett AVL-träd enligt ovan.

  4. Implementera en funktion, delete, för borttagning av ett element i ett AVL-träd enligt ovan.

  5. Implementera funktionen listToSearchTree: (int * 'a) list -> 'a bsTree enligt ovan.
Glöm inte att alla funktioner i din inlämning ska dokumenteras enligt kodkonventionerna.

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

Inlämning

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

ID:
PIN:
formulär för inlämning