Nada

Föreläsning 11: Träd

Binärträd och allmänna träd

Stack och är två viktiga datastrukturer man kan bygga av poster, där varje post pekar på en annan post. I föreläsning 9 såg vi att släktträd också kan byggas med en enda pekare i varje post (faderspekaren).

TRÄD Med två pekare i varje post kan man emellertid bygga mer intressanta träd, till exempel ett som beskriver en symfoniorkesters sammansättning.
Här har posterna följande utseende.

   class Node            {
     String word         ;
     Node down,right     ;}
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-pekaren för firstChild och rightpekaren för nextSibling. Det är ganska förvånande att det räcker med två pekare i varje post, 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. Vi antar att posterna har följande utseende.

   class Node            {
     int tal             ;
     Node left,right     ;}
Högst upp finns konstigt nog trädets rot och dit har man alltid en pekare root.
Antalet nivåer i trädet avgör hur många poster det kan innehålla. Ett fullt träd med k nivåer innehåller 2 höjt till k poster minus 1. Exempel: k=3 i vår bild ger högst 7 poster (det finns plats för två till under 9999). Man kan också säga att ett balanserat träd med N poster har cirka logN nivåer.

Rekursiva tankar för binärträd

Dom flesta problem i samband med binärträd löser man enklast med en rekursiv tanke.
Fråga: Hur många poster finns det i trädet?
Rekursivt svar: Antalet poster i vänsterträdet plus antalet poster i högerträdet plus 1.
...men ett tomt träd har 0 poster.
Följande funktion gör att antal(root) blir 5 för vårt träd.
int antal(Node p)                      {
  if(p==null) return 0                 ;
  return antal(p.left)+antal(p.right)+1;}
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.
int write(Node p)                      { //Inordning
  if(p==null) return                   ;
  write(p.left)                        ;
  System.out.print(p.tal+" ")          ;
  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.

int write(Node p)                      { //Preordning     
  if(p==null) return                   ;
  System.out.println(p.word)           ; 
  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å en post i trädet. Låt oss säga att vi söker efter 666. Vår algoritm blir följande 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 logN. Men binärträdet har två stora fördelar.
  1. Insättning av ny post kräver bara logN jämförelser mot N/2 för insortering i en vektor.
  2. Trädet kan bli hur stort som helst men vektorns storlek ges i dess deklaration.
Enda problemet 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.
Sidansvarig: <henrik@nada.kth.se>
Senast ändrad 23 februari 1999
Tekniskt stöd: <webmaster@nada.kth.se>