bild
Skolan för
elektroteknik
och datavetenskap

F�rel�sning 4: Bin�ra s�ktr�d och bin�ra tal

  • Allm�nna tr�d
  • Bin�ra tr�d
  • Rekursiva tankar f�r bin�rtr�d
  • Bin�ra s�ktr�d
  • Bin�ra tal

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

Bin�rtr�d

N�r man talar om bin�rtr�d brukar man t�nka p� en lite annorlunda bild. Ett bin�rtr�d �r en l�nkad struktur med ett v�rde och tv� pekare i varje nod.
class Node:
  value=None
  left=None
  right=None
Utifr�n n�r man 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. Och det konstaterandet kan ses som en rekursiv definition av begreppet bin�rtr�d!

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

Fr�ga: Hur m�nga noder finns i bin�rtr�det?
Rekursivt svar: En nod mer �n i v�nstertr�det och h�gertr�det tillsammans ...men ett tomt tr�d har noll noder.
    def antal(p):
      if p is None: return 0
      return 1+antal(p.left)+antal(p.right)
Anropet antal(root) ger nu r�tt svar!

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


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
  • 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.
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. Tidskomplexiteten blir densamma.
def finns(p,value):
    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 ges i dess deklaration (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.

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
 - - -          
  if wordlist.exists(word):...# Returnerar True om ordet finns i tr�det 
  wordlist.put(word)          # Sorterar in ett nytt ord i tr�det
  wordlist.write()            # Skriver ut alla ord i bokstavsordning

Endast dessa tre metoder kan anropas utifr�n. Men om man vill implementera metoderna rekursivt m�ste man kunna g�ra anrop av typen finns(p,value) och d�rf�r definierar man ytterligare tre metoder i filen bintree.py, men ovanf�r klassen Bintree. Den metod som anropas, wordlist.exists(word), inneh�ller bara en sats.
  def exists(self,value):
        return finns(self.root,value)


Den l�ter allts� finns g�ra jobbet. Varf�r kan d� inte
huvudprogrammet direkt g�ra anropet if finns(wordlist.root,word)?
Det skulle ju strida mot abstraktionen - det �r inte meningen att n�gon
utomst�ende ens ska k�nna till att det finns en root!

Sv�rast att implementera �r ins�ttningen. Man skulle tro att satsen
putta(self.root,newvalue)
skulle kunna skicka vidare jobbet till en rekursiv metod putta, men det g�r inte. N�r tr�det �r tomt �r rotpekaren None, men n�r den f�rsta noden s�tts in ska rotpekaren peka p� den. Men self.root kan bara �ndras inifr�n objektet, s� d�rf�r f�r man skriva s� h�r.

    def put(self,newvalue):
        self.root=putta(self.root,newvalue)
Anropet till putta returnerar en pekare till det nya tr�det och den l�ggs in i self.root. Men det �r bara f�rsta g�ngen som tilldelningen beh�vs. S� h�r blir principen f�r putta.
def putta(p,newvalue):
    if p is None:                       # Skapa en ny nod med det nya
      - - -                             # v�rdet och returnera den
    if newvalue<p.value:                
        p.left=putta(p.left,newvalue)   # Rekursiv inputtning
    elif newvalue>p.value:
        p.right=putta(p.right,newvalue)
    else:                               # V�rdet fanns redan i tr�det!
      - - -                             
    return p                            # Returnera pekare till det
                                        # modifierade tr�det
Hur ska tr�det reagera om det anv�ndare vill l�gga in redan finns d�r? Ett s�tt �r att alltid spara bara det senaste eller f�rsta av de inlagda sakerna med samma v�rde (vi v�ljer detta i labben). Beskriver man tydligt sin l�sning s� i dokumentationen s� fungerar det bra.

Dessutom kan ju anv�ndaren hela tiden anv�nda exists-funktionen f�r att kontrollera om det den har f�r avsikt att l�gga till redan finns i tr�det...

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.


Obalanserade tr�d

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.

Det finns m�nga s�tt att g�ra om ett obalanserat tr�d till ett balanserat. Till exempel kan man spara hela tr�det i en (sorterad) array och skapa tr�det p� nytt genom att ta elementen i l�mplig ordning. Att g�ra om hela tr�det tar O(n) varje g�ng. B�ttre �r att se till att tr�det �r balanserat efter varje ins�ttning. Ett s�tt att g�ra det �r r�d-svarta tr�d d�r man ger varje nod en extra egenskap (r�d eller svart) och st�ller upp regler f�r hur noderna ska vara ordnade. Om reglerna till�mpas varje g�ng man l�gger till eller plockar bort en nod s� h�lls tr�det balanserat.




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).
  • En kompilator skapar ett syntaxtr�d f�r programmet.
  • Databaser anv�nder tr�d (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�ra tal (och andra baser)

Till vardags anv�nder vi decimala talsystemet med tio siffror: 0-9. Andra talsystem finns, t ex bin�ra tal (tv� siffror: 0-1), oktala tal (�tta siffror: 0-7) och hexadecimala tal (sexton siffror:0-F).

Decimalt Bin�rtOktaltHexadecimalt
0 0 0 0
1 1 1 1
2 10 2 2
3 11 3 3
4 100 4 4
5 101 5 5
6 110 6 6
7 111 7 7
8 1000 10 8
9 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F
16 10000 20 10
17 10001 21 11
18 10010 22 12
19 10011 23 13
20 10100 24 14

Fr�ga: Hur skriver man talet n bin�rt?
Rekursivt svar: F�rst skriver man n/2 (heltalsdivision) bin�rt och sen skriver man en nolla eller etta beroende p� om n var j�mnt eller udda, ...men talen 0 och 1 skrivs likadant bin�rt.

def writebinary(n):
    if n==0 or n==1:
        print n,
    else:
        writebinary(n//2)
        print n%2,

Sidansvarig: Magnus Rosell <rosell@csc.kth.se>
Uppdaterad 2006-09-28