TILDA, ÖVNING 2 12 sept 2007 - Mikas grupp 10-12 i E51 (Linda vikarierar) ************************************************************** Binära sökträd 1 TRÄDBYGGEN * Hur ser det binärträd ut som skapas om man puttar in talen 4 2 1 6 3 7 5 i denna ordning? Och hur ser det ut om man sätter in dom i omvänd ordning, alltså 5 7 3 6 1 4 2? Är båda träden binära sökträd? Är de balanserade? 2 POSTORDERTRÄD * Skriv ut något av träden i inordning och bygg upp ett nytt träd från denna talföljd. Skriv sedan ut dom i preordning och bygg upp nya träd från dessa talföljder. Skriv slutligen ut dom i postorder och bygg upp nya träd från dessa talföljder. Rekursion 3 REKURSION I LISTA * Ge en rekursiv tanke för att räkna antal noder i en lista, och programmera den. 4 REKURSIV TRÄDSUMMA * Ge en rekursiv tanke för summan av alla talen i trädet och programmera den så att anropet tree.sum() ger rätt svar. 5 REKURSIVT LÖVANTAL * Ge en rekursiv tanke för antalet löv i trädet. (Ett löv är en nod utan barn.) Programmera den så att anropet leaves(root) ger rätt svar. 6 REKURSIV TRÄDHÖJD * Ge en rekursiv tanke för höjden av ett träd. (Höjden definieras konstigt nog som antalet nivåer - 1. Ett tomt träd får höjden -1.) Komplexitet 7 SÖKNING I labbarna används en ordfil med cirka 2000 ord. Hur många jämförelser går det åt för att söka efter ordet värst i * en ordnad vektor * en kö * ett binärträd * en hashtabell 8 KÖRTIDER En viss algoritm tar 0.5 ms när antal indata är 100. Hur lång kommer körtiden att bli när antal indata är 500 om man vet att körtiden är: * linjär * O(NlogN) * kvadratisk * kubisk ************************************************************** LÖSNING 1 TRÄDBYGGEN Insättning av 4 2 1 6 3 7 5 ger trädet 4 2 6 1 3 5 7 Binärt sökträd: ja. Balanserat: ja Insättning av 5 7 3 6 1 4 2 ger trädet 5 3 7 1 4 6 2 Binärt sökträd: ja. Balanserat: nej 2 POSTORDERTRÄD Inordning + nybygge -------------------- Båda träden ger 1 2 3 4 5 6 7 8 i inordning Nya trädet bli en tarm, ytterst obalanserat. 1 2 3 4 5 6 7 Preordning + nybygge --------------------- Första trädet i preordning ger 4 2 1 3 6 5 7 och nytt träd blir 4 2 6 1 3 5 7 (samma som ursprungsträdet) Andra trädet i preorder ger 5 3 1 2 4 7 6 och nytt träd blir 5 3 7 1 4 6 2 (samma som ursprungsträdet) Postorder + nybygge ---------------------- Första trädet i postorder ger 1 3 2 5 7 6 4 och nytt träd blir 1 3 2 5 4 7 6 Andra trädet i postorder ger 2 1 4 3 6 7 5 och nytt träd blir 2 1 4 3 6 5 7 3 Rekursiv tanke: Listan har en nod mer än resten av listan (efter första noden). Basfall: En tom lista har noll noder. def antal(p): if p is None: return 0 return 1+antal(p.next) 4 REKURSIV TRÄDSUMMA Rekursiv tanke: Summan är rottalet plus vänsterträdets summa plus högerträdets summa ... men tomt träd har summan noll. def summa(p): # Om den står utanför klassen slipper man self if p==None: return 0 return int(p.value)+summa(p.left)+summa(p.right) class Bintree - - - def sum(self): return summa(self.root) 5 REKURSIVT LÖVANTAL Rekursiv tanke: Antalet löv är antalet löv i vänsterträdet plus antalet löv i högerträdet ...men en ensam rotnod är ett löv ...och ett tomt träd har noll löv. def leaves(p): if p==None: return 0 if p.left==None and p.right==None: return 1 return leaves(p.left)+leaves(p.right) 6 REKURSIV HÖJD Rekursiv tanke: Höjden är 1 + max(höjden av vänsterträdet, höjden av högerträdet) ...men tomt träd har höjden -1. def height(p): if p==None: return -1 h1=height(p.left) h2=height(p.right) if h1>h2: return 1+h1 return 1+h2 7 SÖKNING log2(2000) ~ 11 värst väscht ordnad vektor 10 11 kö 1000 2000 binärträd 10+ 11+ (mer om obalanserat) hashtabell 1+ 1+ 8 KÖRTIDER Linjär k * N N = 500 k * 500 = x ------------- N = 100 k * 100 = 1/2 5 x = - = 2.5 ms (5x längre) 2 O(NlogN) k * NlogN N = 500 k * 500 * log(500) = x ------------------------ N = 100 k * 100 * log(100) = 1/2 5 * log(500) x = ------------ = 3.37 ms (6.74x längre) 2 * log(100) kvadratisk k * N * N N = 500 k * 500 * 500 = x ------------------- N = 100 k * 100 * 100 = 1/2 5 * 5 x = ----- = 12.5 ms (25x längre) 2 kubisk k * N * N * N N = 500 k * 500 * 500 * 500 = x ------------------------- N = 100 k * 100 * 100 * 100 = 1/2 5 * 5 * 5 x = --------- = 62.5 ms (125x längre) 2 **************************************************************