TILDA, ÖVNING 2 TILDA, EXERCISE 2
______________________________________________________________________ ______________________________________________________________________
********************************************************************** ************************************************** ********************
Binära sökträd Binary search trees
1 TRÄDBYGGEN 1 TREE CONSTRUCTION
* Hur ser det binärträd ut som skapas om man puttar in talen 4 2 1 6 * What is the binary tree created out if you push up rates 4 2 1 6
3 7 5 i denna ordning? 3 7 5 in that order? Och hur ser det ut om man sätter in dom i And how does it look if you insert them in
omvänd ordning, alltså 5 7 3 6 1 4 2? reverse order, ie 5 7 3 6 1 4 2? Är båda träden binära Are both binary trees
sökträd? search tree? Är de balanserade? Are they balanced?
______________________________________________________________________ ______________________________________________________________________
Insättning av 4 2 1 6 3 7 5 ger trädet Insertion of 4 2 1 6 3 7 5 gives the tree
4 4
2 62 6
1 3 5 71 3 5 7
Binärt sökträd: ja Binary search tree: yes
Balanserat: ja Balanced: yes
Insättning av 5 7 3 6 1 4 2 ger trädet Insertion of 5 7 3 6 1 4 2 gives the tree
5 5
3 73 7
1 4 61 4 6
2 2
Binärt sökträd: ja Binary search tree: yes
Balanserat: ja Balanced: yes
______________________________________________________________________ ______________________________________________________________________
********************************************************************** ************************************************** ********************
2 POSTORDERTRÄD 2 POST-ORDER TREES
* Skriv ut något av träden i inordning och bygg upp ett nytt * Print any of the trees in fying and building up a new
träd från denna talföljd. tree from this sequence. Skriv sedan ut dom i preordning och Then, print them in preordning and
bygg upp nya träd från dessa talföljder. building up new trees from these sequences. Skriv slutligen ut Write finally out
dom i postorder och bygg upp nya träd från dessa talföljder. Judgement in the the postorder and building up new trees from these sequences.
______________________________________________________________________ ______________________________________________________________________
Inordning
--------------------
Both trees give 1 2 3 4 5 6 7 ordering
New tree to be a gut, extremely unbalanced.
1
2
3
4
5
6
7
Preordning
---------------------
The first tree in preordning gives 4 2 1 3 6 5 7 and the new tree is
4
2 6
1 3 5 7
(Same as the original tree)
Other tree in preorder gives 5 3 1 2 4 7 6 and new trees will be
5
3 7
1 4 6
2
(Same as the original tree)
Postorder
----------------------
The first tree in the postorder gives 1 3 2 5 7 6 4 and new trees will be
1
3
2 5
4 7
6
Other tree in the postorder gives 2 1 4 3 6 7 5 and new trees will be
2
1 4
3 6
5 7
______________________________________________________________________ ______________________________________________________________________
********************************************************************** ************************************************** ********************
Rekursion Recursion
3 GCD 3 GCD
* För att beräkna största faktorn som två tal m och n har gemensamt * To calculate the largest factor that two numbers m and n are jointly
kan vi använda Euklides algoritm: we can use Euclid's algorithm:
Om m är jämnt delbar med n så är n den största gemensamma faktorn. If m is divisible by n, N is the greatest common factor.
Annars är GCD(m, n) = GCD(n, m%n). Otherwise, GCD (m, n) = GCD (n, m% n). Skriv en rekursiv funktion! Write a recursive function!
______________________________________________________________________ ______________________________________________________________________
def gcd(m, n): def gcd (m, n):
if m%n == 0: IF m% n == 0:
return n return n
else: else:
return gcd(n, m % n) return gcd (n, m% n)
______________________________________________________________________ ______________________________________________________________________
********************************************************************** ************************************************** ********************
4 FIBONACCITAL 4 Fibonacci
* Leonardo Fibonacci skrev år 1225 en bok där han beskrev denna intressanta * Leonardo Fibonacci wrote in 1225 a book in which he described this interesting
talföljd: sequence:
Sista december föds en kaninpojke och en kaninflicka. Last December was born a boy rabbit and a bunny girl. Vid två månaders ålder At two months old
och varje månad därefter producerar varje kaninpar ett nytt kaninpar. and every month thereafter, each producing a new kaninpar kaninpar.
Vi kan skriva en rekursiv formel för antal kaninpar: We can write a recursive formula for the number kaninpar:
f 0 = 0 f 0 = 0
f 1 = 1 f 1 = 1
f n = f n-1 + f n-2 f n = f n-1 + f n-2
Skriv en rekursiv funktion för att beräkna Fibonaccital. Write a recursive function to calculate Fibonacci. Visa vilka See which
rekursiva anrop den ger upphov till vid beräkningen av f(5). recursive calls it generates in the calculation of f (5).
Är det här det effektivaste sättet att beräkna Fibonaccitalen? Is this the most effective way to calculate Fibonacci?
______________________________________________________________________ ______________________________________________________________________
def fib(n): def fib (n):
if n <= 1: if n <= 1:
return n return n
else: else:
return fib(n-1) + fib(n-2) return fib (n-1) + fib (n-2)
Man kan visa att antalet anrop faktiskt växer snabbare än själva Fibonaccitalen! One can show that the number of calls actually growing faster than the Fibonacci!
(För N=40 är Fibonaccitalet ca hundra miljoner men antalet rekursiva anrop är över 300 miljoner.) (For N = 40 Fibonaccitalet is approximately one hundred million but the number of recursive calls are over 300 million.)
Bättre vore här att använda en for-slinga: This would be better to use a for-loop:
def fib(n): def fib (n):
f0 = 0 f0 = 0
f1 = 1 f1 = 1
for i in range(n-1): for i in range (n-1):
f2 = f1 + f0 f2 = f1 + f0
f0 = f1 f0 = f1
f1 = f2 f1 = f2
return f1 return f1
Den här implementationen går i linjär tid, O(n). This is The implementation of linear time, O (n).
______________________________________________________________________ ______________________________________________________________________
********************************************************************** ************************************************** ********************
5 REKURSIV TRÄDSUMMA 5 RECURSIVE TREE TOTAL
* Ge en rekursiv tanke för summan av alla talen i trädet och * Give a recursive view of the sum of all numbers in the tree and
programmera den så att anropet tree.sum() ger rätt svar. program it to call tree.sum () gives the right answer.
______________________________________________________________________ ______________________________________________________________________
Rekursiv tanke: Summan är rottalet plus vänsterträdets summa Recursive view: The sum is rottalet plus left sum tree
plus högerträdets summa ... sum plus the right tree ... men tomt träd har summan noll. but empty tree is zero sum.
def summa(p): def summa(p): # If it is outside of the class, self is unnecessary
if p == None: if p == None:
return 0 return 0
else: else:
return int(p.value)+summa(p.left)+summa(p.right) return int (p.value) + summa(p.left) + summa(p.right)
class Bintree class Bintree
- - - - - -
def sum(self): def sum (self):
return summa(self.rot) return summa(self.rot)
______________________________________________________________________ ______________________________________________________________________
********************************************************************** ************************************************** ********************
6 REKURSIV TRÄDHÖJD 6 RECURSIVE TREE HILL
* Ge en rekursiv tanke för höjden av ett träd. * Give a recursive view of the height of a tree.
Höjden är den maximala nivån som nån av trädets noder befinner sig på. The height is the maximum level which nodes of the tree someone is on.
Ett träd med bara en rotnod har höjden 0, och ett tomt träd har höjden -1. A tree with only one root node has height 0, and an empty tree has height -1.
______________________________________________________________________ ______________________________________________________________________
Rekursiv tanke: Höjden är 1 + max(höjden av vänsterträdet, höjden Recursive view: The height is 1 + max (height of the left tree, height
av högerträdet) ...men tomt träd har höjden -1. right of the tree) ... but empty tree has height -1.
def height(p): def height (p):
if p == None: if p == None:
return -1 return -1
else: else:
h1 = height(p.left) h1 = height (p.left)
h2 = height(p.right) h2 = height (p.right)
return max(h1,h2) + 1 return max (h1, h2) + 1
______________________________________________________________________ ______________________________________________________________________
********************************************************************** ************************************************** ********************
Komplexitet Complexity
7 KÖRTIDER 7 Runtime
En viss algoritm tar 0.5 ms när antal indata är 100. A certain algorithm takes 0.5 ms when the input number is 100.
Hur lång kommer körtiden att bli när antal indata är 500 om man vet How long will run time will be when the input number is 500 if you know
att körtiden är: that driving time is:
* linjär * Linear
* O(NlogN) * O (NlogN)
* kvadratisk * Square
* kubisk * Cubical
______________________________________________________________________ ______________________________________________________________________
Linear 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)
Square 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
Cubical 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