bild
Skolan för
datavetenskap
och kommunikation
KTH / CSC / Kurser / DD1339 / inda13 / Vårens uppgifter / Uppgift 5

Uppgift 5 våren 2014

Uppgiften ska lämnas till din övningsledare på övningen den 21/2.

För godkänt måste du ha gjort samtliga deluppgifter (utom den valfria). 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

Läs följande text om binära sökträd.

Om du vill, läs också den här artikeln om randomiserade binära sökträd. (Jag skrev artikeln 1997 och några av Java-tipsen är föråldrade, men datastrukturen är fortfarande aktuell.)

Skriftlig uppgift

Implementera ett binärt sökträd i Java. Som vanligt ska alla publika metoder vara välspecificerade och testkoden ska förstås också lämnas in.

Nycklarna ska vara objekt som implementerar gränssnittet java.lang.Comparable. En generisk klass med en typparameter som matchar klasser som implementerar Comparable kan skrivas så här:

class Tree<T extends Comparable<T>>

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:

  • Sökning.
  • Insättning, där dubbletter inte får förekomma.
  • Antal element.
  • Trädets djup.
  • Antal löv i trädet.
  • toString(), där elementen ska vara sorterade.

De två första metoderna ska implementeras med iteration och de tre sista med rekursion.

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 sökning respektive insättning i en treap? Motivera ditt svar.

Valfri extrauppgift

Implementera en treap i Java.

Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2013-10-28