Uppgift 5 våren 2008Uppgiften ska lämnas till din övningsledare på övningen den 21,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 (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. HemuppgiftStudera avsnitten om binära sökträd (3.1) i algoritmboken och läs artikeln om randomiserade binära sökträd. Skriftlig uppgiftImplementera 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:
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 extrauppgiftImplementera en treap i Java. |