• kth.se
  • Studentwebben
  • Intranät
  • kth.se
  • Studentwebben
  • Intranät
Logga in
DD1321 HT20 (50170)
d5
Hoppa över till innehåll
Översikt
  • Logga in
  • Översikt
  • Kalender
  • Inkorg
  • Historik
  • Hjälp
Stäng
  • Min översikt
  • DD1321 HT20 (50170)
  • Uppgifter
  • d5
  • Startsida
  • Uppgifter
  • Sidor
  • Filer
  • Kursöversikt
  • Quiz
  • Moduler
  • Samarbeten
  • Video Recording
  • Media Gallery
  • Course Evaluation

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):
# Sorterar in newvalue i trädet self.root = rekstore(self.root, key, newvalue) def search(self, key):
# returnerar value om key finns i trädet, KeyError annars # TODO def __contains__(self, key):
# True om key finns i trädet, False annars # TODO def write(self):
# Skriver ut trädet i inorder rekwrite(self.root) print("\n")

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 
1613948340 02/21/2021 11:59pm
Inkludera en beskrivning
Ytterligare kommentarer:
Maxresultat för gradering till > poäng
Inkludera en bedömningstitel

Matris

Hitta matris
Inkludera en titel
Hitta en matris
Titel
Du har redan bedömt studenter med den här matrisen. Större ändringar kan påverka resultaten för deras uppgifter.
 
 
 
 
 
 
 
     
Det går inte att ändra en matris efter att du börjat använda den.  
Titel
Kriterier Bedömningar Poäng
Det här kriteriet är länkat till ett lärandemål Beskrivning av kriterium
tröskel: 5 poäng
Redigera beskrivning av kriterium Ta bort kriterium rad
5 till >0 poäng Full poäng blank
0 till >0 poäng Inga poäng blank_2
Det här området kommer användas av utvärderaren för kommentarer relaterade till det här kriteriet.
poäng
  / 5 poäng
--
Ytterligare kommentarer
Det här kriteriet är länkat till ett lärandemål Beskrivning av kriterium
tröskel: 5 poäng
Redigera beskrivning av kriterium Ta bort kriterium rad
5 till >0 poäng Full poäng blank
0 till >0 poäng Inga poäng blank_2
Det här området kommer användas av utvärderaren för kommentarer relaterade till det här kriteriet.
poäng
  / 5 poäng
--
Ytterligare kommentarer
Poängsumma: 5 av 5