Föreläsning 5: Binära sökträd, abstraktion, forts rekursion från förra föreläsningen

Abstraktion

Abstrakta datatyper Det är ofta praktiskt att beskriva vilka operationer man vill kunna göra på sina data utan att behöva tänka på hur operationerna ska implementeras (dvs hur programkoden ska se ut). En datastruktur som beskrivs på detta sätt kallas för en abstrakt datatyp. En abstrakt datatyp

1. Anger inte lagringssättet
2. Specificerar operationer för åtkomst och ändring

Exempelvis har dictionary flera metoder vars implementation vi inte känner till.

>>> dict.values()
[12332, 231444, 53231]
>>> dict.keys()
['kalle', 'beata', 'cecilia']

Om man kodar mot gränssnittet istället för implementationen så kan man ändra den interna representationen i efterhand.

Stack

En stack fungerar som en trave tallrikar - det man lägger överst på stacken är det som kommer att tas bort först. För en abstrakt stack finns följande operationer:

push(x)	Lägg x överst på stacken.
x=pop()	Hämta det som ligger överst på stacken.
IsEmpty()	Undersök om stacken är tom.

Den som använder datatypen behöver inte bry sig om hur den representeras. Funktionerna läggs i en klass som opererar på data. Så här skulle ett gränssnitt för en stack kunna se ut:

class Stack:
    push()
    pop()
    isEmpty()

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

Stack och kö är två viktiga datastrukturer man kan bygga med en länkad lista. Med två referenser i varje objekt kan man emellertid bygga mer intressanta träd, till exempel ett som beskriver en symfoni-orkesters sammansättning.

All systematisk uppdelning kan beskrivas med träd liknande Treenode ovan, till exempel ett bokverks uppdelning i delar, kapitel, sektioner osv. Man kan också tänka sej det som ett släktträd med firstChild och rightreferensen nextSibling. Det är ganska förvånande att det räcker med två referenser i varje objekt, oavsett hur stora barnaskarorna är.

I labbarna kommer vi använda binärträd.

Högst upp i trädet finns konstigt nog trädets rot och dit har man alltid en referens root. Ett träd är balanserat om höjdskillnaden mellan delträden till varje nod är antingen noll eller ett. 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 (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

Algoritmer för binärträd blir ofta enklast med en rekursiv tanke. Fråga: Hur många objekt finns det i trädet?

Rekursivt svar: Antalet objekt i vänsterträdet plus antalet objekt i högerträdet plus 1. ...men ett tomt träd har 0 objekt.

Följande metod gör att antal(root) blir 5 för vårt träd.

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

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

Sökningen kan implementeras rekursivt om man låter anropet exists(node,word) returnera true ifall ordet finns i det delträd där node är rot. Men den kan också göras utan rekursion med hjälp av en stack. Komplexiteten blir densamma.

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 binärträdet har två stora fördelar.

1. . Insättning av nytt objekt kräver bara log N 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.

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.

Abstrakta sökträd

Ett binärt sökträd med en ordlista bör ha åtminstone tre metoder

class Tree:
    def exists(word): # ... Returnerar true om ordet finns i trädet
    def insert(word): # ... Sorterar in ett nytt ord i trädet
    def printTree(): # ... Skriver ut hela trädet

Binära träd blir lätt obalanserade. Ett sätt att får någorlunda balanserade träd är att efter insättning kontrollera om grenen är obalanserad och i så fall byta plats på noderna och/eller roten. Dessa träd ingår inte i kursen men den intresserade kan läsa vidare om t ex AVL-träd eller röd-svarta träd.

Sökträd med information

Det är sällan man nöjer sej med att veta att en söknyckel finns i databasen; oftast vill man att sökningen ska ge tillbaka information om det sökta. Sökmetoden getInfo(key) blir likadan som exists men returnerar nod.info i stället för true/false. Trädet kommer att fungera som pythons dictionary. Trädstrukturer är hierarkiska och sådana datastrukturer är mycket vanliga. T.ex.

• 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