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

• Binärträd och allmänna träd
• Rekursiva tankar för binärträd
• Binära sökträd
• Vetenskaplighet: Examina och tjänster

Binärträd och allmänna 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

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

//Inordning
   def write(p):
     if p is None: return
     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 is None: return
     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.

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 nullreferens finns inte 666 i sökträdet.

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)

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

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

Abstrakta sökträd

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

  def exists(self,value):
        return finns(self.root,value)

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)

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,
      - - -                             # gör felutskrift!
    return p                            # Returnera pekare till det
                                        # modifierade trädet

Sökträd med information

   class Node:
       key=""              # Det som man sorterar på
       info=None           # Informationen om key
       left=None
       right=None

• Timanställd övningsassistent - teknolog
• Adjunkt - civ ing eller licentiat
• Doktorand - civ ing eller licentiat
• Lektor - doktor eller docent
• Professor - docent

Adjunkt är en ren undervisningstjänst - en lektor ska forska i tjänsten och undervisar kanske åttio procent - en professor leder en forskargrupp och hinner sällan undervisa mer än femtio procent.