Nada

Föreläsning 9: Binära sökträd

Binärträd och 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 emellertid bygga mer intressanta träd, till exempel ett som beskriver en symfoniorkesters sammansättning.
Här har objekten följande utseende. 

   class Node:
     value=""  
     down=None
     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 ganska förvånande att det räcker med två referenser i varje objekt, oavsett hur stora barnaskarorna är.

BINÄRTRÄD När man talar om binärträd brukar man tänka på en lite annorlunda bild. Högst upp finns konstigt nog trädets rot och dit har man alltid en referens root.
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

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 is None: return
     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 is None: return
     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
(Är det någon som kommer på hur man måste ändra koden för att få just dessa indragningar, så vill jag gärna höra förslaget.)

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.

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å ett objekt i trädet. Låt oss säga att vi söker efter 666. Vår algoritm blir följande Sökningen kan implementeras rekursivt om man låter anropet finns(p,value) returnera True ifall ordet finns i det delträd där p är rot. 
def finns(p,value):
    if p is 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)
Men den kan också göras utan rekursion. Komplexiteten blir densamma. 
def finns(value):
    p=root
    while True:
        if p is None: return False
        if value==p.value: return True
        if value<p.value: p=p.left
        if value>p.value: p=p.right
Det här är ju nästan precis samma sak som binär sökning i en vektor. I båda fallen blir antalet jämförelser cirka log N, men vektorn har två nackdelar.
  1. Insättning av nytt objekt i vektorn kräver att man flyttar i genomsnitt N/2 gamla objekt. I binärträdet flyttar man aldrig noder.
  2. Trädet kan bli hur stort som helst men vektorns storlek anges när den skapas (om det är en sammanhängande följd av minnesceller).
Ett problem med binärträd är att dom kan bli obalanserade, och då försvinner den snabba sökningen. Ett riktigt obalanserat sökträd med dom fem talen i exemplet har 1 i roten, 17 till höger, 666 till höger om det osv. Det blir bara en så kallad tarm. I vissa fall har binärträd en tendens att bli obalanserade med tiden, till exempel när nyfödda förs in i ett träd sorterat på personnummer och då alltid hamnar längst till höger. Ett annat problem är att det är mycket svårt att ta bort en nod mitt inne i trädet. Ofta avstår man från det och dödmarkerar i stället noden.

Abstrakta sökträd

Nu tänker vi oss att binärträdet har implementerats i en egen fil bintree.py och vi vill använda det som en abstrakt ordlista. För en abstrakt ordlista bör åtminstone tre anrop finnas: exists, put och write. 
from bintree import Bintree

wordlist=Bintree()            # Skapar ett trädobjekt

wordlist.put(word)            # Sorterar in ett nytt ord i trädet

if wordlist.exists(word):     # Returnerar True om ordet finns i trädet 

wordlist.write()              # Skriver ut alla ord i bokstavsordning
Endast dessa tre metoder kan anropas utifrån, och det är därför vi säger att vi gjort binärträdet abstrakt. I filen bintree.py finns den konkreta implementationen av vårt abstrakta träd och först i den filen står class Node som vi förut sett. Sen kommer då class Bintree med tre metoder som alla ska ha self som första parameter. 
class Bintree:
    root=None
    def put(self,word):
        - - -
    def exists(self,word):
        - - -
    def write(self):
        - - -
Så ser det ut inne i binärträdsmodulen. Nu kan vi se vad anropen från vårt huvudprogram egentligen betyder. 
from bintree import Bintree   # class Bintree blir synlig (men inte class Node)

wordlist=Bintree()            # nytt objekt med egen root och tre funktioner

wordlist.put(word)            # blir put(wordlist,word) med self=objektet 

if wordlist.exists(word):     # blir exists(wordlist,word) med self=objektet

wordlist.write()              # blir write(wordlist) med self=objektet
Koden för (den icke-rekursiva) finns(value) duger också för exists(self,word) om root byts ut mot self.root. Om man i stället ville använda den rekursiva varianten med anropet finns(p,value) kan man göra exists-koden så här kort. 
    def exists(self,word):
        return finns(self.root,word)
Definitionen av finns skriver man utanför klassen Bintree (före eller efter spelar ingen roll), eftersom den inte ska kunna anropas utifrån.

Att putta in något nytt i ett sökträd innebär att söka efter det och sedan, när man kommit längst ner i trädet, länka in den nya noden på just det stället. 

    def put(self,word):
        ny = Node()                    # Ny nod skapas...
        ny.value=word
        if self.root==None:            # ...om trädet tomt, lägg in...
            self.root=ny
            return
        p=self.root                    # ...börja annars en sökning.
        while True:
            if word<p.value:       
                if p.left==None:       # Om None läggs nya noden in,
                    p.left=ny
                    return
                p=p.left               # annars går sökningen vidare.
            elif word>p.value:
                if p.right==None:
                    p.right=ny
                    return
                p=p.right
            else:                      # Dubblettter läggs inte in.
                return
När det gäller write har man inget val, den måste vara vår rekursiva inorder. Därför skickar exists bara vidare jobbet till en utanför klassen definierad procedur skriv(p) (som är just rekursiva inorder). 
    def write(self):
        skriv(self.root)

Sökträd med information

Det är sällan man nöjer sej med att veta att en söknyckel (som kan vara textsträng eller tal) finns i databasen; oftast vill man att sökningen ska ge tillbaka information om det sökta. I varje trädnod måste det då finnas adressen till ett objekt som innehåller informationen. 
   class Node:
       key=""              # Det som man sorterar på
       info=None           # Informationen om key
       left=None
       right=None
Sökmetoden getinfo(key) blir likadan som exists men returnerar p.info i stället för True/False.

Vetenskaplighet: Hypatia

 Hypatia var matematiker och den sista bibliotekarien på det stora biblioteket i Alexandria. Skalman har ett inramat motto på väggen med texten DEN HÄR GÅNGEN SKA HYPATIA FÖRSVARAS och bakgrunden till det är att Hypatia mördades av en kristen pöbel, påhejad av biskop Kyrillos. Man lär ha flått henne med ostronskal och bränt biblioteket med 40000 böcker. Det behövs ju inga andra böcker än bibeln!

Biblioteket i Alexandria fick leva i sjuhundra år. Hypatia lever fortfarande som symbol för den som offrar sitt liv i kampen mot okunnighet och övertro och för vetenskap och sanning.

Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 6 december 2007
Tekniskt stöd: <webmaster@nada.kth.se>