Föreläsning 4: Rekursion och binära sökträd

• Läs i boken: kap 5.1-5.6 (men vänta med 5.5.1)
• Rekursion
• Allmänna träd
• Binära träd
• Rekursiva tankar för binärträd

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

Sifferexempel

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

Hur fungerar det?

• 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.

Aktiveringsposterna tar extra minne i anspråk och stackhanteringen tar extra tid, så den extremt sparsamme skriver om sina rekursiva funktioner.

Listexempel

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

Rekursiv binärsökning

def binarySearch(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)/2
        if alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return binarySearch(alist[:midpoint], item)
            else:
                return binarySearch(alist[midpoint+1:], item)

Allmänna träd

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

Användningsområden

• 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).

Binärträd

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

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

Rekursiva tankar för binärträd

    def antal(p):
        if p == None: 
            return 0
        else:
            return 1 + antal(p.left) + antal(p.right)

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 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)

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

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.

Algoritmer som går igenom varje nod i trädet (t ex utskrift) har tidskomplexitet O(n).

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 trädet om skillnaden i höjd mellan höger och vänster delträd till varje nod är noll eller ett.

Binära sökträd

• 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):
        if p == None: 
            return False
        if value == p.value: 
            return True
        if value<p.value: 
            return finns(p.left,value)
        if value>p.value: 
            return finns(p.right,value)