TILDA, ÖVNING 2 12 sept 2008
**************************************************************
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 FIBONACCITAL
* Leonardo Fibonacci skrev år 1225 en bok där han beskrev denna intressanta
talföljd:
Sista december föds en kaninpojke och en kaninflicka. Vid två månaders ålder
och varje månad därefter producerar varje kaninpar ett nytt kaninpar.
Vi kan skriva en rekursiv formel för antal kaninpar:
f0 = 0
f1 = 1
fn = fn-1 + fn-2
Skriv en rekursiv funktion för att beräkna Fibonaccital. Visa vilka
rekursiva anrop den ger upphov till vid beräkningen av f(5).
Är det här det effektivaste sättet att beräkna Fibonaccitalen?
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 REKURSIV TRÄDHÖJD
* Ge en rekursiv tanke för höjden av ett träd.
Höjden är den maximala nivån som nån av trädets noder befinner sig på.
Ett träd med bara en rotnod har höjden 0, och ett tomt träd har höjden -1.
Komplexitet
6 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: ja
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 def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
Man kan visa att antalet anrop faktiskt växer snabbare än själva Fibonaccitalen!
(För N=40 är Fibonaccitalet ca hundra miljoner men antalet rekursiva anrop är över 300 miljoner.)
Bättre vore här att använda en for-slinga:
def fib(n):
f0 = 0
f1 = 1
for i in range(n-1):
f2 = f1 + f0
f0 = f1
f1 = f2
return f1
Den här implementationen går i linjär tid, O(n).
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
else:
return int(p.value)+summa(p.left)+summa(p.right)
class Bintree
- - -
def sum(self):
return summa(self.rot)
5 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
else:
h1 = height(p.left)
h2 = height(p.right)
return max(h1,h2) + 1
6 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
**************************************************************