d5
- Inlämningsdatum 21 feb 2021 av 23.59
- Poäng 1
- Lämnar in en filuppladdning
- Filtyper py och txt
Mål: implementation av binärt sökträd, rekursion, abstraktion. Se föreläsning 8, övning h5. se också labb d2
Laborationens tema är binära sökträd.
- Första uppgiften är att skriva en klass för binära sökträd.
- Andra uppgiften är att testa ditt binärträd
- Tredje uppgiften är att modifiera laboration d3 till att använda binära sökträd istället för hashtabeller.
Experimentera med binärträd
Gå in på Liangs binärträdsanimation Links to an external site. 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. Klassen ska i princip fungera som en hashtabell med samma gränssnitt men den här gången ska medlemsvariabeln root inte vara privat.
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.store("gurka", "grönsak") # Sortera in "gurka" i trädet - - - if "gurka" in svenska: # Kolla om "gurka" finns i trädet
# (Operatorn in anropar metoden __contains__ Links to an external site.
# som du ska implementera i din Bintree-klass) - - - svenska.write() # Skriver alla trädobjektets ord i bokstavsordning
Ordet (nyckeln) "gurka" kommer att ligga överst i trädet eftersom det lades in först. Nya ord som är större än gurka läggs in på ena sidan sidan (right) och ord som är mindre läggs in på andra sidan (left). Du behöver inte ta hänsyn till att det binära sökträdet kan bli obalanserat om man t.ex. lägger in en sorterad ordföljd.
Klassen Bintree ska alltså ha följande metoder:
- store(nyckel, data) som lagrar data som value i ditt binärträd, med nyckel som key.
- search(x) som returnerar data associerat med x och kastar KeyError om nyckeln inte finns.
- __contains__(x) som returnerar true eller false om nyckeln finns i trädet
- write() som skriver ut trädet i inorder
Men i filen bintreeFile.py ska du dessutom definiera tre hjälpfunktioner. När trädobjektets store("gurka", "grönsak") anropas skickar trädet sin rotpekare, nyckel och värde till en funktion rekstore (rekursiv store) som ser till att en ny nod skapas på rätt ställe, alternativt att en befintlig nod ändrar värde. Funktionen rekstore anropar sig själv rekursivt för att stoppa in nyckel och värde på rätt ställe. Även search ska implementeras rekursivt med en hjälpfunktion som kastar KeyError om nyckeln inte finns (som labb d2). Funktionen __contains__ fungerar som koden till finns i föreläsning F8. Börja med att titta på koden till finns i F8.
class Bintree: def __init__(self): self.root = None def store(self, key, newvalue): |
Här är klassen slut men sedan kommer definitionerna av funktionerna rekstore, reksearch och rekwrite. Det är tillåtet att ha fler hjälpmetoder.. Trädet ska bara lagra en upplaga av varje nyckel som läggs in.
Det finns förstås också en class Node i bintreefilen som innehåller key och value och två pekare: left och right.
Andra uppgiften: Testa din kod med unittest
Använd unittest Links to an external site. för att testa din kod. Utnyttja att root inte är privat. Det finns några specialmetoder i unittest t.ex. assertEqual som testar att två värden är lika och assertRaises som testar om ett undantag kastars. Utöka exempelkoden nedan med egna tester med t.ex. tre insättningar. Döp början av testmetodnamnen till test
import unittest
from bintree import *
class BintreeTest(unittest.TestCase):
def testInsert(self):
""" Testar Subj och Pred """
b = Bintree()
b.store("adam", 123)
self.assertEqual(b.root.key, "adam")
self.assertEqual(b.root.value, 123)
def testInsertMore(self):
# TODO
def testSearch(self):
b = Bintree()
with self.assertRaises(KeyError):
b.search("eva")
def testMore(self):
# TODO
if __name__ == '__main__':
unittest.main()
Tredje uppgiften: Modifiera laboration d3
Kopiera labb d3 till en ny fil d53.py och använd ditt binärträd istället för hashtabellen. Jämför den slutliga koden med d3.py. Hur många rader behövde ändras? Det finns ett unixverktyg diff som du kan prova
> diff d3.py d53.py
Redovisning
Vid redovisningen ska du kunna
- 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 store som anropar rekstore, och write som anropar skriv
- förklara vad skillnaden var att använda binärträd istället för hashtabell i d3