DD1320 Tillämpad Datalogi

Föreläsning 4: Binära sökträd och rekursion forts

Allmänna träd
Binära träd
Rekursion
Rekursiva tankar för binärträd

Allmänna träd

Stack och kö är två viktiga datastrukturer man kan bygga av objekt, där varje objekt refererar till ett annat objekt. TRÄD

Med två referenser i varje objekt kan man bygga träd, till exempel ett som beskriver en symfoniorkesters sammansättning.
Här har objekten följande utseende.

    class Node:
       def __init__(self, value):
          self.value = value
          self.down = None
          self.right = None

All systematisk uppdelning kan beskrivas med liknande träd, till exempel ett bokverks uppdelning i delar, kapitel, sektioner osv. Man kan också tänka sej det som ett släktträd och då kallas ofta down-referensen för firstChild och rightreferensen för nextSibling. Det räcker med två referenser i varje nod, oavsett hur stora barnaskarorna är.

Användningsområden

Trädstrukturer är hierarkiska och sådana datastrukturer är mycket vanliga. Några exempel:

Filsystemet använder träd (man kan ha underkataloger i underkataloger).
När du kör ditt Pythonprogram byggs ett syntaxträd upp för programmet.
Databaser använder träd för att få snabb sökning.
Schackprogram använder träd för att gå igenom resultaten av möjliga drag.
Vid datakomprimering kan man använda träd för att få fram en optimal kod (Huffmanträd, kommer på komprimeringsföreläsningen).

Definitioner

Noder är de objekt som trädet är uppbyggt av. De innehåller data och pekare.
Rot är den översta noden i trädet. Den pekas inte ut av någon annan nod.
Barn till en nod är de som pekas ut av noden.
Förälder är noden ovanför i trädet.
Syskon har samma förälder.
Löv är en nod vars bägge pekare är None.
Delträd definieras så här: En godtycklig nod i trädet kan ses som en rot, och den , tillsammans med alla noder under den (barn, barnbarn osv.) bildar ett delträd.
Nivå är det antal steg från roten noden befinner sig. Roten är på nivå noll.
Höjd är den maximala nivån som nån av trädets noder befinner sig på.
Balanserat är binärträdet om skillnaden i höjd mellan höger och vänster delträd till varje nod är noll eller ett.
Fullt är binärträdet om alla noder utom löven har exakt två barn, och alla löv är på samma nivå.

Binärträd

När man programmerar binärträd brukar man använda noder, som i en länkad lista, men med två pekare: en åt vänster och en åt höger:

    class Node:
       def __init__(self, value):
          self.value = value
          self.left = None
          self.right = None

Man når trädet genom variabeln root som pekar på den översta noden (datalogiska träd har roten uppåt). Rotnodens vänsterpekare pekar på ett mindre binärträd och högerpekaren på ett annat mindre binärträd.

Antalet nivåer i trädet avgör hur många noder det kan innehålla. Ett fullt träd med k nivåer innehåller 2^k - 1 noder. Exempel: k=3 i vår bild ger högst 7 noder (det finns plats för två till under 9999). Man kan också säga att ett balanserat träd med n noder har cirka log n nivåer.

Binära sökträd

I vårt exempelträd ligger små tal till vänster och stora tal till höger. När det är på det sättet har man ett binärt sökträd, så kallat eftersom det går så snabbt att söka reda på en nod i trädet. Låt oss säga att vi söker efter 666. Vår algoritm blir följande

Kolla först rottalet.
Om talet är 666 har vi funnit vad vi söker.
Om talet är större än 666 letar vi vidare efter 666 i vänsterträdet.
Om det är mindre än 666 letar vi vidare i högerträdet.
...men om vi når en None-referens finns inte 666 i sökträdet.

    def finns(p,value):
        while True:
            if p == None: 
                return False
            if value == p.value: 
                return True
            if value<p.value: 
                p = p.left
            if value>p.value: 
                p = p.right

Den här funktionen kan du använda i labb 3!
Där ska du göra en klass som fungerar som ett abstrakt binärt sökträd med operationerna put, exists och write.

Rekursion

Rekursiv kommer från latinet och betyder återlöpande. Om man i definitionen av ett begrepp använder begreppet självt så är definitionen rekursiv. Rekursiva tankar kan också användas för problemlösning.

Rekursiv tanke: reducerar problemet till ett enklare problem med samma struktur
Basfall: det måste finnas ett fall som inte leder till rekursivt anrop

Rekursiv bild, rekursivt recept

Sifferexempel

Fråga: Hur många siffror har heltalet n?
Rekursivt svar: En siffra mer än om man stryker sista siffran i n, ...men tal mindre än tio är ensiffriga.

    def antalsiffror(n)
      if n<10: return 1 
      return 1+antalsiffror(n/10)

Fråga: Vilken siffersumma har heltalet n?
Rekursivt svar: Sista siffran plus siffersumman om man stryker sista siffran i n, ...men noll har siffersumman noll.

    def siffersumma(n):
      if n == 0:  
        return 0               
      return (n%10) + siffersumma(n/10)

Triangeltalet S(N) är summan av de N första heltalen. S(4)=1+2+3+4

Fråga: Vad är värdet på S(N)?
Rekursivt svar: S(N) = S(N-1) + N ... men S(1)=1.
Här följer en rekursiv funktion för beräkning av triangeltalen:

    def s(n):
        if n == 1: 
            return 1
        else:
            return s(n-1) + n

Hur fungerar det?

När man skriver egna rekursiva funktioner bör man lita på att det rekursiva anropet fungerar - man behöver inte analysera anropsgången för varje fall. Men för att förstå varför rekursion kan vara extra minneskrävande är det vara bra att känna till hur programspråken hanterar rekursiva anrop.

För varje anrop skapas en aktiveringspost som innehåller data för anropet, t ex parametrar, lokala variabler och anropspunkt.
Aktiveringsposten pushas på en stack.
När det rekursiva anropet är klart poppas aktiveringsposten från stacken, varefter föregående anrop ligger överst på stacken.

s(0)

s(1)

s(2)

s(3)

s(4)

huvudprogram

Listexempel

Vi tänker oss en länkad lista av noder, där varje nod innehåller ett värde och en next-pekare. Variabeln top pekar på den översta noden.
Fråga: Hur många noder finns i listan?
Rekursivt svar: En nod mer än i listan under översta noden ...men en tom lista har noll noder.

    def antal(p):
        if p is None: 
            return 0
	else:        
            return 1 + antal(p.next)

Anropet antal(top) ger nu rätt svar!

Några saker att minnas

En rekursiv funktion kan alltid omformuleras utan rekursion, men om det finns flera rekursiva anrop i funktionen kan det vara besvärligt.
För många problem är en rekursiv funktion mycket enklare att formulera och ger kortare kod än utan rekursion. Ofta måste man gå via den rekursiva lösningen i tanken även om man gör en icke-rekursiv lösning.
Den rekursiva funktionen kräver i regel mer minne (och tar längre tid) än motsvarande icke-rekursiva funktion.

Utskrift av binärträd: inorder, preorder, postorder

Om man ska skriva ut alla talen i trädet vill man oftast göra det i så kallad inordning (eng. inorder), dvs från vänster till höger.
Fråga: Hur skriver man ut trädet i inordning?
Rekursivt svar: Först skriver man ut vänsterträdet, sedan rottalet, sist högerträdet.
...men ett tomt träd skriver man inte alls.
Följande funktion gör att write(root) skriver ut 1 17 666 4711 9999 för vårt träd.

#Inordning
    def write(p):
        if p != None:
            write(p.left)
            print p.value
            write(p.right)

Om man kastar om dom tre sista satserna får man ändå ut alla talen på skärmen men i andra ordningar. Preordning (eng. preorder) innebär att rottalet skrivs först, sedan vänsterträdet och sist högerträdet. I vårt exempel blir ordningen 4711 17 1 666 9999.

Om vi återgår till orkesterträdet kan vi se att preordning faktiskt ger vettigare utskrift. Så här blir koden i det fallet.

#Preordning     
    def write(p):
        if p != None:
            print p.value
            write(p.down)
            write(p.right)

Utskriften blir då den naturliga. Om vi för tydlighets skull använder indragning av orden på lägre nivå blir utskriften

    Orkester              
        Blås
            Trä
            Bleck
        Stråk
            Vi
            Va
            Vc
            Kb
        Slag

(Hur gör man för att få dessa indragningar?)

Slutligen kan man skriva ut i postordning (eng. postorder) och det innebär att vänsterträdet skrivs först, sedan högerträdet och sist roten. Det ger 1 666 17 9999 4711 i vårt exempel.