INDA - Uppgift 5 våren 2006


Uppgiften ska lämnas till din övningsledare på övningen den 24/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 (7.4) i algoritmboken och läs den utdelade artikeln om randomiserade binära sökträd.


Skriftlig uppgift
Implementera ett binärt sökträd i Java. Nycklarna ska vara textsträngar. 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
2006-01-24