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.
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.
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.
- 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.
- 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�rt | Oktalt | Hexadecimalt |
---|
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,