Till KTH:s startsida Till KTH:s startsida

Laboration 3

Laboration 3 - Ordträd

Mål: implementation av binärt söträd, rekursion, abstraktion.

Laborationens tema är binära sökträd.

  • Första uppgiften är att skriva en klass för binära sökträd och testa den.
  • Andra uppgiften är att bygga upp ett sökträd från en fil med svenska ord. Alla dubbletter ska skrivas ut.
  • Tredje uppgiften är att kolla orden i en engelsk text mot det svenska sökträdet. Finns det några skenbart svenska ord ska dom skrivas ut, men bara den första förekomsten av varje svenskt ord. (För att veta vilka ord man redan hittat sparar man förstås dom i ett extra sökträd.)

Experiment

Gå in på Liangs binärträdsanimation och gör följande:

  • Skapa ett balanserat binärträd med sju noder
  • Skriv ut trädet i inorder
  • Skriv ut trädet i preorder
  • Skriv ut trädet i postorder

Skriv en klass för binära sökträd

Nu ska du implementera ett binärt sökträd som en klass.

Tänk dig först ett abstrakt binärt sökträd. Eftersom man med Python kan jämföra ord (bokstavsordning) så går det bra att lagra ord i sökträdet, t ex så här:

   svenska = Bintree()              # Skapa ett trädobjekt
   svenska.put("gurka")		    # Sortera in "gurka" i trädet	
   - - -
   if "gurka" in svenska:      # Kolla om "gurka" finns i trädet
      - - -
   svenska.write()                  # Skriver alla ord i bokstavsordning

Klassen Bintree ska alltså ha tre metoder:

  • put(x) som sorterar in x i trädet
  • __contains__(x) som kollar om x finns i trädet (anropas av operatorn in)
  • write() som skriver ut trädet i inorder

Men i filen bintreeFile.py ska du dessutom definiera tre hjälpfunktioner. När trädobjektets put("gurka") anropas skickar trädet sin rotpekare och det nya ordet till en rekursiv funktion putta som ser till att en ny nod skapas på rätt ställe. Analogt gör de övriga anropen, alltså så här.

class Bintree:
    def __init__(self):
        self.root=None

    def put(self,newvalue):
        self.root=putta(self.root,newvalue)

    def __contains__(self,value):
        return finns(self.root,value)

    def write(self):
        skriv(self.root)
        print("\n")



Här är klassen slut men sedan kommer definitionerna av funktionerna putta, finns och skriv. Trädet ska bara lagra en upplaga av varje objekt som läggs in.

Det finns förstås också enclass Node i bintreefilen som innehåller ett värde och två pekare: left och right.

Andra uppgiften: Bygg träd och skriv ut dubbletter


Nu ska du läsa in ett ord i taget från filen word3.txt och lägga in det ditt binära sökträd. Ord som förekommer flera gånger (dubbletter) ska skrivas ut.

from bintreeFile import Bintree
svenska = Bintree()
with open("word3.txt", "r", encoding = "utf-8") as svenskfil:
    for rad in svenskfil:
        ordet = rad.strip()                # Ett trebokstavsord per rad
        if ordet in svenska:
            print(ordet, end = " ") 
        else:
            svenska.put(ordet)             # in i sökträdet
print("\n")



Om du gjort rätt kommer dom dubblettord som spottas ut att bilda ett viktigt budskap.

Tredje uppgiften: Två binära sökträd med ordlistor

När du nu har ett sökträd med alla svenska trebokstavsord kan du blixtsnabbt kolla om ett givet ord finns med. Du ska nu läsa filen engelska ord för ord och putta in orden i ett annat sökträd. Nu vill du inte ha dubbletterna utskrivna, så kolla först if engelska.exists(...). Om ordet redan fanns gör du ingenting, men om det är nytt ska du också kolla om det råkar finnas som svenskt ord. I så fall ska det skrivas ut på skärmen.

Om du har gjort rätt kommer dom utskrivna orden att bilda ännu ett hemligt budskap!

Redovisning

Labben lämnas in via git och redovisas muntligt av bägge gruppmedlemmarna.

Vid redovisningen ska du

  • kunna rita och berätta hur binärträdet byggs upp,
  • visa hur du testat din klass för binära träd,
  • förklara varför det går snabbt att söka i ett binärträd,
  • förklara idén bakom att ha put som anropar putta, etc

Betyg

Denna labb kan endast ge betyg E. Du måste lämna in den och redovisa den i tid för att få göra labbarna för högre betyg nästa period.

Alexander Baltatzis created page 18 January 2016

commented 3 February 2016

Vad står egentligen self.root för? Den verkar inte stå för hela trädets rot, utan ändras varje gång vi stoppar in ett värde. Hur fungerar det egentligen?

Teacher commented 3 February 2016

self.root är en medlemsvariabel (attribut). Det borde stå för hela trädets rot men om du sätter om det med t.ex. self.root = None så pekar det inte på någonting. I exempelkoden ovan sätts det till som returneras av putta. Vad denna funktion returnerar beror på din egen implementation och jag kan inte svara på hur putta fungerar. Det finns hjälptid imorgon efter föresläsningen. 

commented 5 February 2016

Hmmm... okej. Men om vi lägger till två antal element i trädet, så att det får ett djup på 2, hur vet jag då att den börjar söka i roten om jag lägger till ett tredje värde, eller vill hitta ett värde som ligger i trädet? Alltså, hur vet jag att den utgår från hela trädets rot och inte bara ett delträd med sin rot i det senaste värdet vi lade till? Kan man återställa värdet på root på något sätt? 

commented 5 February 2016

Ok, fick hjälp av en okänd hjälte, så nu är det löst.

commented 6 February 2016

Är det meningen att class Bintree inte ska ändras? Ska man använda den som den skrivits i uppgiften helt och hållet, eller är det meningen att man ska lägga till kod som behövs?

commented 7 February 2016

"förklara idén bakom att ha put som anropar putta, etc"

På vilket sätt är det bättre än att ha snarlika (rekursiva) metoder i Node-klassen?

One user removed his/her comment
Teacher commented 8 February 2016

@Albin

"Skriv en klass för binära sökträd

Nu ska du implementera ett binärt sökträd som en klass..."

Du ska implementera klassen - skriva kod. Du ska inte ändra i gränssnittet för klassen, t.ex. ska följande kod gå att köra.

svenska = Bintree()              # Skapa ett trädobjekt
   svenska.put("gurka")		    # Sortera in "gurka" i trädet	
   - - -
   if "gurka" in svenska:      # Kolla om "gurka" finns i trädet
      - - -
   svenska.write()                  # Skriver alla ord i bokstavsordning


Internt får du lägga till vad du vill. Du får även utöka gränssnittet med lämplig metod som du kan motivera. T.ex. finns det inte någon metod remove("gurka") vilket man skulle kunna tycka vore bra. Det är lite klurigt att skriva en remove-metod, du måste stanna på noden ovanför det du vill ta bort. En annan metod som saknas är put(key, value) vilket får binärträdet att fungera som en dictionary. 

Teacher commented 8 February 2016

@Jakob. Det som skiljer metoderna åt är antalet parametrar. Du behöver två parametrar för den rekursiva algoritmen (varför det är så ska du förklara på redovisning). Sett ur den synvinkeln är put, som bara har en parameter överflödig, du klarar dig med den andra (putta). Å andra sidan så är det ett dåligt gränssnitt mot användaren av bintree-klassen att tvingas anropa med en extra pekare. Utåt sett vill man bara stoppa in ett värde i trädet och bryr sig inte så mycket om dess interna detaljer. 

Pythons dictionary skulle man kunna implementera som ett binärträd under ytan. Det skulle vara otympligt att tvingas skicka med en pekare varje gång man vill stoppa in ett värde. 

Jämför

d["Eva"] = 35

d["Eva", dict.root] = 35

commented 8 February 2016

@Alexander. Ja visst är Bintree's put-metod användarvänlig men tekniskt sett överflödig när man har en separat funktion putta. Men min fråga är varför man har en separat funktion putta istället för att lägga den funktionaliteten i en metod Node.put. Bintree's put kan anropa rootNode.put som anropar left.put eller right.put vid rekursion, osv.

commented 8 February 2016

Samma gäller finns och skriv, finns det någon anledning att inte lägga den funktionaliteten som metoder i Node-klassen? Bintree.write -> rootNode.write osv.

Teacher commented 8 February 2016

Om jag stoppar in tio nycklar? Hur många instanser av Node-klassen får du med din lösning? 

commented 8 February 2016

Tio. Det funkar som det ska. Skrev en annan lösning enligt den specifika instruktionen att ha med putta, skriv och finns, båda ger samma resultat. Men jag tycker att den tidigare är mer elegant och undrar om jag missar något skäl till att det är sämre.

Teacher commented 8 February 2016

Svårt att uttala sig om utan att se koden, och jag vill inte att du postar kod publikt. Det går att posta så att enbart lärare/assistenter ser. Annars kanske vi hinner ses imorgon så kan jag förklara. 

commented 8 February 2016

Hej, jag och min labbkompis har haft förhinder att redovisa på tisdag kvällar, förra veckan  och de kommande två tillfällena. Finns det möjlighet att vi kan redovisa vid något annat tillfälle? Kanske efter någon föreläsning, på handledningarna eller går det att vi redovisar dem i klump senare. Vi gör självklart klart labbarna i tid, det är bara förra veckans redovisningstillfälle och kommande två veckor som vi inte kan närvara båda två samtidigt.