INDA - Uppgift 5 våren 2007
Uppgiften ska lämnas till din övningsledare på övningen den 22/2.
Glöm inte försättsbladet (pdf) och att
alla papper ska häftas samman eller lämnas in i en plastficka.
För godkänt måste du ha gjort samtliga deluppgifter.
Det är tillåtet att göra enstaka fel och misstag men det
är viktigt att du försöker lösa samtliga uppgifter. Om du kör fast med
någon uppgift så finns det som vanligt hjälp att få på labbarna.
Hemuppgift
Studera avsnitten om binära sökträd (3.1) i algoritmboken
och läs
artikeln
om randomiserade binära sökträd.
Skriftlig uppgift
Implementera ett binärt sökträd i Java. Nycklarna ska vara
objekt som implementerar gränssnittet java.lang.Comparable.
Varje nod i trädet ska representeras av ett objekt som innehåller
två pekare, en till det vänstra och en till det högra
subträdet. Använd gärna koden för länkade listor från
övning 2 som en mall. Följande operationer ska implementeras:
- Insättning. (Dubbletter får inte förekomma.)
- Sökning.
- Antal element.
- Trädets höjd.
- Antal löv i trädet.
- toString() (Elementen ska vara sorterade.)
De tre sista metoderna ska implementeras med rekursion.
(Naturligtvis får man avända rekursion även för
de övriga metoderna om det är lämpligt.)
Beräkna tidskomplexiteten i värstafall för samtliga
operationer.
Om man istället använder ett randomiserat binärt sökträd (treap)
så blir tidskomplexiteten bättre. Vad blir den förväntade tiden för
insättning respektive sökning i en treap? Motivera ditt svar.
Valfri extrauppgift
Implementera en treap i Java.
Stefan Nilsson
2007-01-15
|