Datastrukturer och databaser för STS

och

Programmeringsteknik II för F

Arne Andersson


Laborations- och programmeringsuppgift 2: binära sökträd.


Java-dokumentation hittar du på http://java.sun.com/docs/
Uppgiften skall göras för både AA-träd och randomiserade sökträd (Treaps). Klasserna som ska användas är hämtade från lärobokens hemsida, men är modifierade för att passa uppgiften. Paketet ligger i katalogen /home/arnea/public_html/datastrukturer/ och heter trees. Bekanta dig med klasserna genom att läsa paketets JavaDoc. Du skall utgå från den givna koden och göra följande modifikatiner och tillägg:
  1. Kopiera paketet till din egen katalog. När detta är gjort måste -classpath användas för att java ska hitta paketet. Läs mer om classpath här.
  2. Skriv en metod treeHeight som returnerar höjden på ett träd. Metoden skall räkna ut höjden med hjälp av rekursivitet. (Höjden av ett löv är 1 (eller 0, vilket man tycker), höjden av en intern nod är 1 plus den största av de två barnerns höjder. Trödets höjd är detsamma som rotens höjd.)
  3. Modifiera metoden printTree så att man får en strukturerad utskrift av trädet, där man kan se nodernas höjd och på så sätt få en uppfattning av trädets form. Den strukturerade utskriften görs så att noden skrivs längre åt höger ju högre upp i trädet den befinner sig. Man får alltså hålla reda på höjden i printTree. OBS: du skall inte använda treeHeight för varje nod; det blir ju väldigt långsamt. I stället tar du först reda på hela trädets höjd genom att använda treeHeight på roten, sedan räknar du ner höjden alteftersom du traverserar nedåt i trädet under printTree.
    Exempel: Det här trädet kan se ut så här:

                   D
             H
          j
                K
                      M
                P
                   Q
          R
             S
                T
       U
          V
             X
          Z
    
    I ditt fall skall du dock visa mer information i den strukturerade utskriften. Förutom nodens nyckel, som i utskriften ovan, skall du skriva ut balanseringsinformationen. För det randomiserade sökträdet innebär detta att exempelvis en nod med nyckeln algoritm och prioritet 4352, skriver du ut algoritm:4352. För ett AA-träd innebär det att en nod med nyckeln algoritm och level 2, skrivs som algoritm:2.
  4. Modifiera definitionen av en binär nod så att den också innehåller nodens vikt, definierad som antalet element som finns under noden, inklusive noden själv. I bilden ovan har noden X vikten 4, medan noden M har vikten 14. Vikterna skall updateras vid insättning och uttag, framförallt gäller det att få det hela rätt vid rotationerna. ( OBS: Uppdatering av vikterna måste givetvis göras på ett effektivt sätt, så att de tinte försämrar tidskomplexiteten hos implementationen.) Skriv en metod findOrder som tar som parameter ett tal index och som returnerar en referens till den nod som innehåller element nr index, räknat i alfabetisk ordning. Metoden skall på ett bra sättt använda sig av viktinformationen.
  5. Skriv ett litet interaktivt program som låter användaren sätta in och ta ut strängar i ett sökträd. programmet börjar med att ge instruktioner till användaren, i stil med:
    Välkommen till mitt trädvisningsprogram för randomiserade träd. 
    Du använder det så här:
    
         + str     sätter in strängen str i trädet
         - str     tar bort strängen str, om den finns i trädet
         f str     svarar om strängen str finns med eller ej.
         o x       anger sträng nr x i bokstavsordning.
         v         visar hur trädet ser ut 
         c         tömmer trädet
         q         avslutar programmet
         ?         skriver ut den här hjälptexten
    
    
Tips: Gör först lösningen för en av trädtyperna, så går den andra lätt.

Förutom programkod skall du lämna in en utskrift av en typisk körning för båda programmen. Se till att utskriften på ett meningsfullt sätt ger goda exempel på strukturerade trädutskrifter.