Bisekcija + seznami = bisekcija na steroidih (alias drevo)¶
Kjer so seznami, tam so tudi drevesa, pravi star kenijski pregovor. (Tole sem si seveda gladko izmislil.)
Takole razmislimo. Radi bi bisekcijo. In nočemo tabel. Se pravi, da hočemo sezname. Vendar na seznamih ni bisekcije. Razen ... Razen, če bi si zapomnili tudi, kje je srednji element. (Vnaprej svarim, da se bo to končalo tako, da ne bomo imeli ne seznama ne bisekcije, temveč nekaj tretjega.)
Vzemimo gornji seznam. Če se bomo šli bisekcijo, bomo začeli pri Helgi. Torej moramo vedeti, kje je Helga. (To spet diši po goljufiji in kako se to konča, vemo. Najbrž ni posebnega razloga, da bi se nam s Helgo zgodilo kaj drugače kot s Fanči. Hmnja. Manjše težave nas sicer čakajo, vendar se bomo tokrat uspeli izmotati.)
Žal to, da vemo, kje je Helga, ne bo dovolj. Če bomo iskali ime, ki je levo od nje, bomo razpolovili desni del, torej bomo nadaljevali z Dani. Torej moramo vedeti, kje je Dani. Če bomo nadaljevali na desni strani in razpolavljali desni del, bomo hoteli vedeti, kje je Liza. (Že vidimo, kam to pelje, pravijo skeptiki. Za vse bomo morali vedeti, kje so. Toliko spremenljivk, kolikor oseb. In to se ne da. Vemo. Iz Programiranja 1. Ne moreš imeti toliko spremenljivk, kolikor je elementov. Zato, ker spremenljivke napišemo v program, ko programiramo. Ko program teče, pa se lahko pojavi poljubno število novih oseb. Ne gre. Ne gre.)
Preskočimo ostanek in narišimo, kar mislimo. (Razlagali pa bomo potem. Pa tudi oklepajev bo počasi dovolj.)
(((Tule lahko to poskusimo v živo.)))
Kako sprogramirati to reč?
Malo spominja na seznam, le da je tam vsak objekt kazal na naslednji objekt, tu pa kaže na objekta pod sabo. Imenovali ju bomo (danes res ne manjka presenečenj!) levi in desni.
class Oseba:
def __init__(self, ime, stevilka, levi=None, desni=None):
self.ime = ime
self.stevilka = stevilka
self.levi = levi
self.desni = desni
Zdajle rokohitrsko zložimo podatke v drevo.
osebe = [("Ana", 356), ("Berta", 374), ("Cilka", 698), ("Dani", 781),
("Ema", 972), ("Fanči", 941), ("Greta", 613), ("Helga", 197),
("Iva", 919), ("Jana", 591), ("Klara", 62), ("Liza", 196),
("Micka", 718), ("Nina", 417), ("Olga", 682)]
def v_drevo(osebe):
if not osebe:
return None
pol = len(osebe) // 2
ime, stevilka = osebe[len(osebe) // 2]
return Oseba(ime, stevilka, v_drevo(osebe[:pol]), v_drevo(osebe[pol + 1:]))
koren = v_drevo(osebe)
Funkcija je vrnila samo najzgornejši element. Ker bomo celotno reč imenovali drevo in ker računalnikarji mislijo, da imajo drevesa korenine zgoraj in liste spodaj, temu elementu rečemo koren.
Preverimo, kaj imamo.
koren.ime
koren.levi.ime
koren.levi.levi.ime
koren.levi.desni.ime
V skladu z zadnjo modo iz domače naloge naredimo razred, ki bo vseboval koren in metode za delo z drevesom - recimo iskanje.
class Drevo:
def __init__(self):
self.koren = None
def poisci(self, ime):
vozlisce = self.koren
while vozlisce and vozlisce.ime != ime:
if vozlisce.ime > ime:
vozlisce = vozlisce.levi
else:
vozlisce = vozlisce.desni
return vozlisce
Porinimo drevo, ki smo ga nagoljufali zgoraj, v tole drevo. Kasneje bomo te stvari delali lepše, zdajle pa bomo praktični.
t = Drevo()
t.koren = koren
ana = t.poisci("Ana")
ana.stevilka
Koliko časa - operacij, korakov, kakorkoli jih že hočemo imenovati - je vzelo tole iskanje? V zanki while smo se spuščali po drevesu navzdol, dokler nismo prišli do iskanega elementa. Potrebujemo torej največ toliko korakov, kolikor je visoko drevo.
Rekurzivno iskanje¶
Bisekcijo smo sprogramirali (tudi) rekurzivno in ugotavljali, da je to pravzaprav lažje. Naredimo enako še z drevesi.
class Drevo:
def __init__(self):
self.koren = None
def poisci0(self, vozlisce, ime):
if not vozlisce:
return None
if vozlisce.ime == ime:
return vozlisce
if vozlisce.ime > ime:
return self.poisci0(vozlisce.levi, ime)
else:
return self.poisci0(vozlisce.desni, ime)
def poisci(self, ime):
return self.poisci0(self.koren, ime)
t = Drevo()
t.koren = koren
jana = t.poisci("Jana")
jana.stevilka
Metoda poisci0(vozlisce, ime) v poddrevesu vozlisce poišče ime. Če vozlišča ni (None), ker je drevo prazno ali pa tega, kar iščemo, ni v njem, vrnemo None. Če smo našli, kar iščemo, vrnemo trenutno vozlišče. Sicer pa pokličemo poisci0 na levem ali desnem poddrevesu trenutnega vozlišča.
Metoda poisci0 ni točno to, kar želimo, saj sprejme še dodatni argument, prvo vozlišče. Zato smo za ime dodali še ničlo. Prava metoda se imenuje poisci in pokliče poisci0, tako da ji kot argument poda koren.
Da bodo stvari kasneje lepše tekle, se naučimo še nečesa v Pythonu. Ker je funkcija poisci0 interna zadeva funkcije poisci, jo lahko damo kar znotraj nje.
class Drevo:
def __init__(self):
self.koren = None
def poisci(self, ime):
def poisci0(vozlisce):
if not vozlisce:
return None
if vozlisce.ime == ime:
return vozlisce
if vozlisce.ime > ime:
return poisci0(vozlisce.levi)
else:
return poisci0(vozlisce.desni)
return poisci0(self.koren)
t = Drevo()
t.koren = koren
jana = t.poisci("Jana")
jana.stevilka
Ker je poisci0 zdaj znotraj poisci, vidi tudi spremenljivko (no, argument) ime, tako da se ga ni več potrebno podajati v rekurzivnih klicih. En argument manj torej. Poleg tega namesto self.poklici0 zdaj rečemo poklici0, saj to zdaj ni več metoda, temveč običajna funkcija. Še en argument, self, manj.
(Didaktični medklic: funkcije znotraj funkcije najbrž še niste videli? Načelno je zelo slaba ideja učiti dve stvari hkrati. Moj namen je, da vas učim o drevesih in ne bi bilo dobro, če se spotaknete, ker sem uporabil lokalne funkcije in še nekaj, o čemer res ne boste nikoli slišali, namreč closure. Vendar je funkcija poisci0 zaradi tega precej preprostejša, izgubila je dva argumenta in kar nekaj šare. Če bi šlo le za poisci, tega ne bi počel. Ker nas kasneje čaka še ena pomembna funkcija, ki je precej bolj zapletena, pa vas raje mimogrede naučim tole, saj vam bo to v manjšo nadlego kot bi vam bila dodatna šara kasneje.)
Izpis drevesa¶
Dodajmo še izpis drevesa, ker nam utegne priti kdaj prav. Ker (še?) ne znamo izpisovati po nivojih, ga bomo izpisali z leve proti desni, takole:
class Drevo:
def __init__(self):
self.koren = None
def poisci(self, ime):
def poisci0(vozlisce):
if not vozlisce:
return None
if vozlisce.ime == ime:
return vozlisce
if vozlisce.ime > ime:
return poisci0(vozlisce.levi)
else:
return poisci0(vozlisce.desni)
return poisci0(self.koren)
def izpisi(self):
def izpisi0(vozlisce, s):
if not vozlisce:
return
izpisi0(vozlisce.desni, s + " ")
print(s, vozlisce.ime)
izpisi0(vozlisce.levi, s + " ")
izpisi0(self.koren, "")
t = Drevo()
t.koren = koren
t.izpisi()
Zasukajte za 90 stopinj, pa dobite drevo, kakršno je na zgornji sliki. Kako deluje funkcija - morate vedeti. Le preštudirajte jo, to je snov Programiranja 1.
Drevesa¶
Čeprav drevesa spoznavamo v zvezi z iskanjem, jih bomo srečali še kdaj. Kar bomo napisali tule, je splošno in nam bo prišlo prav tudi kasneje.
Drevo je sestavljeno iz vozlišč (node). Nekatera so notranja vozlišča (inner node), ki jim bomo včasih rekli kar vozlišča, tista na koncu pa so listi drevesa (leaf). Drevesa navadno rišemo odzgoraj navzdol (kadar jih bomo izpisovali, nam jih bo bolj praktično obrniti z leve proti desni). Čisto zgornjemu vozlišču rečemo koren (root). Povezavam med vozlišči bomo rekli veje ali povezave (branch, edge).
Notranja vozlišča imajo enega ali več otrok (child); listi se od njih razlikujejo po tem, da nimajo otrok. Število otrok pogosto omejimo. Drevesom, katerih vozlišča imajo največ dva otroka, pravimo dvojiška drevesa (binary tree). V dvojiških drevesih bomo govorili o levem in desnem otroku (pogosto bomo uporabili tudi šovinistično terminoogijo in jim rekli sinovi). Govorjenje o levem in desnem otroku je smiselno tudi in predvsem zato, ker so otroci navadno urejeni - vemo, kdo je prvi, drugi in tako naprej. Poleg njih se pogosto uporabljajo B-drevesa, ki imajo največ B otrok, popularna so tudi 2-3 drevesa, v katerih ima vsako vozlišče natančno dva ali tri otroke.
Polno dvojiško drevo (full binary tree) je drevo, v katerem vozlišča zapolnijo vse nivoje razen, kvečjemu, zadnjega. Z drugimi besedami: v polnem dvojiškem drevesu ima vsako vozlišče natančno dva otroka, razen vozlišč na zadnjih dveh nivojih, ki imajo lahko le enega ali nobenega (listi). S tretjimi besedami: v polnem dvojiškem drevesu so vsi listi na zadnjih dveh nivojih.
Primer drevesa, ki ni takšno, bi bilo drevo, v katerem ima koren dva otroka; desni otrok je list, pod levim pa visi večje drevo.
Seznam, ki smo ga videli prejšnjič, je vrsta drevesa. Namreč eniško drevo, v katerem ima vsako vozlišče, razen zadnjega, ima natančno enega otroka. Izraz "eniško drevo" sem si pravkar izmislil, saj o seznamih ne razmišljamo kot o drevesih.
Vsako vozlišče, razen korena, ima enega starša (parent). Po potrebi damo rodbinska imena tudi drugim vozliščem in govorimo o dedih, vnukih in bratih, v neki posebni vrsti dreves (rdeče-črna drevesa) so pomembni celo strici.
Pomembna lastnost drevesa je njihova višina. Koren je na nivoju 0, njegovi otroci na nivoju 1 in tako naprej. Višina (ali globina - kakor bomo kdaj gledali) drevesa je enaka nivoju, na katerem je najbolj spodnje vozlišče. Drevo na gornji sliki ima višino 3. Višino drevesa lahko vidimo tudi kot število povezav od korena do najglobjega lista.
Poddrevo (subtree) je del drevesa pod določenim vozliščem. Vsako vozlišče je koren poddrevesa, ki visi pod njim. Neke vrste podkoren torej.
Pri Programiranju 1 smo trepetali pred rekurzivnimi funkcijami - funkcije, ki so definirane sama s seboj. Drevo je rekurzivna podatkovna struktura. Drevo bi lahko definirali tako: drevo je sestavljeno iz korena, na katerega vejah so obešena poddrevesa. Iz te, rekurzivne definicije, lahko pridelamo druge lastnosti drevesa. Lahko definiramo recimo višino: višina drevesa je za 1 večja od višine največjega poddrevesa.
Ker so drevesa rekurzivna struktura, jih bomo v resnici veliko lažje premetavali z rekurzivnimi funkcijami. Zanje bodo veliko bolj naravne kot iterativne.
Se še spomnite, kako smo se pri Programiranju 1 učili rekurzijo? Z rodbinskimi drevesi. Zakaj? Ker se mi je zdelo, da je tam rekurzija najbolj naravno doma.
Lastnosti dvojiških dreves¶
Polno dvojiško drevo ima na $i$-tem nivoju $2^i$ vozlišč, razen na zadnjem, kjer je vozlišč med 1 in $2^h$. Tole je komaj vredno dokaza, če že, pa dokazujemo s popolno indukcijo. Na ničtem nivoju ($i=0$) je koren. Zdaj pa imamo $i >0 $ in se delamo, da za vse manjše $i$ že vemo, da izrek velja. Ker ima na vseh nivojih do predzadnjega vsako vozlišče dva otroka, je število otrok na $i$-tem nivoju dvakrat večje o števila otrok na enem prej; torej pri $i>0$ velja, da je število otrok enako $2\times 2^{i-1} = 2^i$. Na zadnjem nivoju pa imamo vsaj eno vozlišče (sicer tega nivoja ni), največ pa jih je lahko dvakrat toliko kot na prejšnjem, kar je, spet, $2^i$.
Polno dvojiško drevo višine $h$ ima največ $2^{h}$ listov. To smo pravzprav pravkar dokazali: to se zgodi, ko je tudi zadnji nivo poln. Takšnim drevesom bomo rekli "čisto polna drevesa".
Polno dvojiško drevo višine $h$ ima vsaj $2^{h - 1}$ listov. Predstavljajmo si čisto polno drevo višine $h-1$; to ima, kot smo pravkar ugotovili, $2^{h-1}$ listov. Pod enega od listov pripnimo eno samo vozlišče. Število listov je ostalo enako, torej smo dobili najmanjše drevo višine $h$, in to ima $2^{h-1}$ listov.
Dvojiško drevo višine $h$ ima manj kot $2^{h + 1}$ vozlišč. Predstavljajmo si čisto polno drevo višine $h$. Število vozlišč je $\sum_{i=0}^h = 2^{h+1} - 1$. Torej, kakor smo rekli: manj kot $2^{h + 1}$.
Polno dvojiško drevo višine $h$ ima vsaj $2^h$ vozlišč. Najmanjše polno dvojiško drevo višine $h$ dobimo tako, da k čisto polnemu dvojiškemu drevesu višine $h - 1$ dodamo eno samo vozlišče ne $h$-tem nivoju. Čisto polno drevo višine $h - 1$ ima, kot smo prejle izračunali $2^h - 1$ vozlišč. Naše najmanjše drevo višine $h$ jim ima torej $2^h$.
Vse te lastnosti vodijo v tisto, ki je bistvena. Zadnji dve lahko preobrnemo tako, da iz števila vozlišč računamo višino. Za polno drevo (ki nima nujno polnega zadnjega nivoja) velja $2^h < n \le 2^{h + 1}$. Vse strani logaritmiramo in dobimo
$$h < \log_2 n \le h + 1$$
ter preberemo: za $n$ vozlišč potrebujemo dvojiško drevo višine $\log_2 n$. Točneje, če je $n$ enak potenci števila $2^{h+1}-1$ pri nekem $h$, bo zadoščalo drevo višine $h$. Točneje in splošneje, potrebujemo višino $\lceil\log_2 (n + 1)\rceil$.
Zaokrožanje in enice gor ali dol: pomembno je, da višina drevesa narašča z logaritmom števila vozlišč. Če si od vsega tega ne zapomnimo nič drugega, si moramo zapomniti to.
Za nas to pravzaprav ne bi smelo biti presenečenje. Čeprav smo rekli, da bomo bisekcijo malo pozabili, se spet majčkeno spomnimo nanjo: drevesa so v žlahti z bisekcijo. Vsak korak navzdol po drevesu ustreza enemu koraku bisekcije, zato je jasno, da mora višina drevesa naraščati približno tako kot časovna zahtevnost bisekcije.
Smo zmagali?¶
Že od prvih predavanj iščemo isti sveti Gral: radi bi podatkovno strukturo, ki bi omogočala, da po njej hitro iščemo, istočasno pa želimo tudi hitro dodajati in brisati. Bisekcija je bila obetavna, vendar je zahtevala urejene sezname, v katere pa ni bilo mogoče hitro dodajati. V drugem tednu smo spoznali "prave" sezname, v katere je bilo mogoče hitro dodajati, vendar pa ni bilo mogoče hitro iskati (vključno s hitrim iskanjem mesta za dodajanje), saj na njih ni bilo mogoče pognati bisekcije. Nakazal sem, da bodo drevesa - tisto pravo.
Bodo res? Ali pa sem lagal in se bo spet nekje zalomilo?
Iskanje že imamo in vemo, da je hitro. Manjka še dodajanje.
Obeti so dobri, načrt je očiten: poiskali bomo vozlišče, pod katerim bi moralo biti tisto, kar dodajamo. Če hočemo dodati, recimo, Francko, bo ta levi otrok Grete. No, Francko potem pač dodamo, pripnemo pod Greto, pa je. Kako poiščemo Greto? Tako, kot pač iščemo v drevesu. Iskali bomo Francko in ko bomo prišli do konca, jo bomo dodali. Če slučajno najdemo Francko, pa je ne bomo dodajali, ker je že v drevesu.
Zdaj pa držimo pesti, da uspe.
Prvi poskus¶
(Naslov že ne zveni obetavno.)
Napisali bomo metodo insert, ki bo, recimo, rekurzivno, poiskala vozlišče, pod katerega je potrebno pripeti neko novo osebo. In jo pripela. Za začetek kar skopirajmo poisci, saj bo šlo za podobno reč.
class Drevo:
def __init__(self):
self.koren = None
def poisci(self, ime):
def poisci0(vozlisce):
if not vozlisce:
return None
if vozlisce.ime == ime:
return vozlisce
if vozlisce.ime > ime:
return poisci0(vozlisce.levi)
else:
return poisci0(vozlisce.desni)
return poisci0(self.koren)
def dodaj(self, oseba):
def dodaj0(vozlisce):
if not vozlisce:
return None # Tule bomo kasneje zamenjali `return None` z dodajanjem
if vozlisce.ime == oseba.ime:
return # Ne storimo ničesar, ker je oseba s tem imenom že v drevesu
if vozlisce.ime > oseba.ime: # Kam bomo dodali novo vozlišče?
dodaj0(vozlisce.levi) # ... v levo poddrevo
else:
dodaj0(vozlisce.desni) # ... v desno poddrevo
dodaj0(self.koren) # V drevo dodamo tako, da dodamo v drevo pod korenom
Rekurzija tule kar blesti: novo vozlišče dodamo v drevo tako, da ga dodamo v levo ali v desno poddrevo. Kaj hočeš preprostejšega? Stvar očitno naredi največ toliko korakov kot iskanje, torej je ima tudi dodajanje logaritemsko zahtevnost.
Rekurzija se konča, ko odkrijemo, da to osebo že imamo (tedaj rečemo return in nihče ne bo dodajal ničesar) ali ko pridemo do konca drevesa zdaj vemo, kam jo moramo dodati.
Ups. Res vemo? Kam? Prišli smo do konca. Recimo, da vstavljamo Francko. Pri Helgi smo zavili levo, pri Dani in Fanči na desno, pri Greti levo ... in padli na None. Drevesa je konec - tako, kot je bilo prejšnji teden konec seznama, ko smo prišli do None. Francko je potrebno dodati ... v enem koraku prej. Ko pridemo do None, smo se v bistvu izgubili.
Mah ne. Smo spet prišli v slepo ulico? Nam spet ne bo uspelo?
Tokrat je problem le programerski. Rešimo ga lahko na različne načine. Eden bi bil ta, da bi vsako vozlišče poleg tega, kdo so njegovi otroci, vedelo tudi, kdo je njegov oče. Poleg oseba.levi in oseba.desni bi torej imel še oseba.oce. Na kratki rok je to solidna rešitev, kasneje pa bi nas tepla, zato bomo naredili nekoliko drugače.
Funkciji dodaj0 bomo dodali še en argument, oce, ki bo vseboval očeta vozlišča vozlisce. Tako bomo, ko bomo prišli do konca, vedeli, kdo je "oče tega Nonea", do katerega nas je pripeljalo iskanje mesta za dodajanje.
Ko bomo funkcijo dodaj0 poklicali od zunaj, bomo kot argument podali koren, tako kot prej, poleg tega pa None, ker koren nima očeta. V rekurzivnih klicih bomo poleg sina podali še vozlišče; tako bomo recimo, klic dodaj0(vozlisce.levi) spremenili v dodaj0(vozlisce.levi, vozlisce), kar preberemo kot "dodaj osebo v poddrevo vozlisce.levi in oče tega vozlišča je vozlisce.
Dodajanje bo videti takole:
if not oce:
self.koren = oseba
elif oce.ime > oseba.ime:
oce.levi = oseba
else:
oce.desni = oseba
Če smo prišli do None, potem najprej pogledamo, ali ta None, v katerega dodajamo, ima očeta. Če ga nima, to pomeni, da dodajamo prvo vozlišče v prazno drevo; self.koren = oseba. Sicer pa pogledamo, na katero stran očeta je potrebno dodati novo vozlišče, in ga dodamo.
Zaradi kasnejših potreb tole dodajanje spogramirajmo kot ločeno metodo pripni.
class Drevo:
def __init__(self):
self.koren = None
def poisci(self, ime):
def poisci0(vozlisce):
if not vozlisce:
return None
if vozlisce.ime == ime:
return vozlisce
if vozlisce.ime > ime:
return poisci0(vozlisce.levi)
else:
return poisci0(vozlisce.desni)
return poisci0(self.koren)
def izpisi(self):
def izpisi0(vozlisce, s):
if not vozlisce:
return
izpisi0(vozlisce.desni, s + " ")
print(s, vozlisce.ime)
izpisi0(vozlisce.levi, s + " ")
izpisi0(self.koren, "")
def pripni(self, koga, kam):
if not kam:
self.koren = koga
elif kam.ime > koga.ime:
kam.levi = koga
else:
kam.desni = koga
def dodaj(self, oseba):
def dodaj0(vozlisce, oce):
if not vozlisce:
self.pripni(oseba, oce)
return
if vozlisce.ime == oseba.ime:
return
if vozlisce.ime > oseba.ime:
dodaj0(vozlisce.levi, vozlisce)
else:
dodaj0(vozlisce.desni, vozlisce)
dodaj0(self.koren, None) # Oče korena je None
t = Drevo()
t.koren = koren
t.dodaj(Oseba("Francka", 123))
t.izpisi()
ZMAGA! Francka je tam, kjer mora biti in čas, ki smo ga porabili za njeno dodajanje je logaritemski.
Izumili smo torej podatkovno strukturo, ki ima logaritemski čas za iskanje in dodajanje.
Slabe novice¶
Vzemimo seznam oseb in jih eno za drugo dodajmo v drevo.
t = Drevo()
osebe = [("Ana", 356), ("Berta", 374), ("Cilka", 698), ("Dani", 781),
("Ema", 972), ("Fanči", 941), ("Greta", 613), ("Helga", 197),
("Iva", 919), ("Jana", 591), ("Klara", 62), ("Liza", 196),
("Micka", 718), ("Nina", 417), ("Olga", 682)]
for ime, stevilka in osebe:
t.dodaj(Oseba(ime, stevilka))
t.izpisi()
Tole je pa uničujoče. Najprej smo dodali Ano. Nato smo dodali Berto in ta je bila Anin desni otrok. Cilka je bila Bertin desni otrok. Dani Cilkin. Ema Danijin...
Kaj smo dobili? Zanič drevo. Drevo, ki je v resnici seznam. Navaden ušiv urejen seznam, kakršne ste delali prejšnji teden na vajah. Seznam, ki ni dober čisto za nič.
Kje smo se ušteli?
Časovna zahtevnost je enaka višini drevesa. Izračunali smo višino polnega dvojiškega drevesa in se veselili. Pozabili pa smo, da niso vsa dvojiška drevesa tudi polna drevesa.
Uravnotežena drevesa¶
Na Aljaski, južno od Anchoragea, je zaliv z imenom Turnagain Arm. Ime je dobil, ko so mornarji v času pred Google Earthom iskali "severni prehod", ki bi vodil iz Pacifika v Atlantik severno od Amerike. Našli so obetaven zaliv, na koncu katerega pa spet ni bilo ničesar, zato so se morali lepo spet obrniti (turn again) in iskati naprej.
Mi pa bomo šli tokrat naprej po kopnem. Drevesa izgledajo preobetavno, da bi tako hitro obupali.
Naša težava je vstavljanje. Če uspemo nekako zagotoviti, da bo drevo po sestavljanju polno, smo zmagali. To sicer zveni podobno kot pri bisekciji, kjer smo si želeli, da bi bili seznami po vstavljanju urejeni, kar se je izkazalo za neizvedljivo, ker bi zahtevalo linearen čas. Tu pa ne bo tako hudo. Le pogum.
En način, da pridemo do takšnega drevesa je, da najprej vstavimo Helgo, nato Dani, Lizo, Berto ... Pozabi. Nad vrstnim redom vstavljanja nimamo nadzora, sploh pa - kaj, če nam kasneje, ko bo drevo že sestavljeno, prikaplja kup oseb z imeni na črko A, in se izkaže, da Helga ni več dober koren?
En način je ... da se izgovarjamo. Češ, ja, imamo pač strašno smolo, da so prišle osebe ravno po abecedi. Če hodijo v naključnem vrstnem redu, dobimo lepše drevo. Morda ne čisto polno, ampak ... Da to drži. Pri naključnem vrstnem redu so drevesa tipično majhna. Kako velika, še se prav spomnim, še ni rešen problem, a če ne drugače, se da s simulacijo prepričati, da ta izgovor ni zvit iz trte (karkoli že pomeni ta metafora).
Tule pa bomo vseeno naredili rešitev, ki bo zagotovo dobra.
Najprej: polna dvojiška drevesa so draga. Niso neizvedljiva, vendar se tega ne bomo šli. Pač pa se bomo zadovoljili z nečim drugim, kar je skoraj tako dobro. Z uravnoteženimi drevesi (balanced tree).
Pravila igre so takšna: definirali bomo, kaj mislimo, ko rečemo, da je drevo uravnoteženo. Definicij je več, vse smiselne definicije pa morajo imeti logaritemski čas iskanja (vsaj v poprečju, če že ne tudi v najslabšem primeru) in logaritemski čas vstavljanja. Ker se nam lahko očitno zgodi kakšna taka grdobija kot zgoraj, si bomo pri uravnoteženih drevesih zmišljevali takšne načine vstavljanja, ki bodo popravljala uravnoteženost. V gornjem primeru bi, recimo, takrat, ko smo dodali Cilko, po vstavljanju nekako preuredili drevo tako, da koren ne bi bila več Ana, temveč Berta.
Takšnim preurejanjem navadno rečemo vrtenje (rotation). Različni kriteriji uravnoteženosti dajejo različna drevesa in različne algoritme za vstavljanje novih vozlišč.
Pri predmetih APS študenti navadno spoznajo celo drevesnico: AVL drevesa, rdeče-črna drevesa, 2-3 drevesa in še kakšno zraven. Ker pa tule ne učimo profesionalnih programerjev, temveč učitelje računalništva, ki morajo vedeti malo več, kot če ne bi bili učitelji računalništva, ne pa vsega, se bomo omejili na AVL drevesa. Ogledali si jih bomo, da vidimo primer definicije uravnoteženosti, primer vrtenj in primer, kako se to sprogramira.
AVL drevesa¶
Drevo je uravnoteženo, če za vsako (notranje) vozlišče velja, da je razlika med višinama levega in desnega drevesa največ 1.
To zveni tako smiselno, da si človek skoraj težko predstavlja kakšno drugačno definicijo uravnoteženosti. Vendar obstajajo. Ta definicija je le ena od njih in na njej temeljijo drevesa, ki sta si jih izmislila Georgi Maksimovič Adelson-Velski in Evgenij Mihajlović Landis. Ker sta bila Rusa (prvi židovskega rodu) in imata temu primerno dolga imena, ju imenujejo po njima tako, da so iz njunih priimkov sestavili kratico: AVL drevesa. Iznašla sta jih daljnega 1962 in so prva tovrstna podatkovna struktura.
Sprogramirali jih bomo nekoliko drugače, kot so jih včasih. Malo zaradi drugačnega jezika, predvsem pa zato, ker nam danes ni potrebno gledati na vsak bit pomnilnika, tako kot so včasih.
Razredu Oseba dodajmo atribut visina, ki bo povedal, kako visoko je poddrevo, ki visi pod to osebo. Da bo lažje gledati, bomo rekli, da je drevo, ki ima samo koren, visoko 1 (in ne 0, kot smo rekli prej).
Ker se bo poddrevo spreminjalo, bomo dodali osebi tudi metodo preracunaj_visino, ki bo naredila, kar pravi njeno ime.
class TipNikamor:
visina = 0
def __bool__(self):
return False
Nikamor = TipNikamor()
class Oseba:
def __init__(self, ime, stevilka):
self.ime = ime
self.stevilka = stevilka
self.levi = self.desni = Nikamor
self.visina = 1
def preracunaj_visino(self):
self.visina = 1 + max(self.levi.visina, self.desni.visina)
Da stvari lepše tečejo - predvsem pa, da bodo lepše tekle v prihodnje - smo spremenili še nekaj: listi ne kažejo več na None temveč na našo spremenljivko Nikamor. Nikamor je spremenljivka tipa NikamorTip, ki je malo podobna vozlišču drevesa. Predstavlja vozlišče, ki ga ni ali, če hočete, drevo, ki ga ni. Njegova visina je 0. Poleg tega smo rekli, da je Nikamor neresničen (to je tista čudna metoda z imenom __bool__). Če bomo kje napisali if Nikamor ali, kar bomo v resnici pisali if vozlisce.levo, leva veja pa bo šla Nikamor, bo pogoj neresničen.
Naš Nikamor nam pride prav že pri preračunavanju višine: višina drevesa, ki visi pod nekim vozliščem, je za 1 večja od višine večjega od poddreves pod njim. Če je vozlišče list, sta self.levi in self.desni enaka Nikamor, višina Nikamorja je 0, max(0, 0) je 0 in 1 + max(self.levi.visina, self.desni.visina) bo 1, kakor mora biti.
Zdaj dopolnimo še razred Oseba. Metoda dodaj naj vsakič, ko doda vozlišče, še preračuna višino vseh poddreves. Mimogrede spremenimo še izpisi tako, da izpiše poleg imena še višino.
class Drevo:
def __init__(self):
self.koren = None
def poisci(self, ime):
def poisci0(vozlisce):
if not vozlisce:
return None
if vozlisce.ime == ime:
return vozlisce
if vozlisce.ime > ime:
return poisci0(vozlisce.levi)
else:
return poisci0(vozlisce.desni)
return poisci0(self.koren)
def izpisi(self):
def izpisi0(vozlisce, s):
if not vozlisce:
return
izpisi0(vozlisce.desni, s + " ")
print(s + "{} ({})".format(vozlisce.ime, vozlisce.visina))
izpisi0(vozlisce.levi, s + " ")
izpisi0(self.koren, "")
def pripni(self, koga, kam):
if not kam:
self.koren = koga
else:
if kam.ime > koga.ime:
kam.levi = koga
else:
kam.desni = koga
kam.preracunaj_visino()
def dodaj(self, nova_oseba):
def dodaj0(vozlisce, oce):
if vozlisce.ime == nova_oseba.ime:
return
if vozlisce.ime > nova_oseba.ime:
if vozlisce.levi:
dodaj0(vozlisce.levi, vozlisce)
else:
vozlisce.levi = nova_oseba
else:
if vozlisce.desni:
dodaj0(vozlisce.desni, vozlisce)
else:
vozlisce.desni = nova_oseba
vozlisce.preracunaj_visino()
if not self.koren:
self.koren = nova_oseba
else:
dodaj0(self.koren, None)
Poglejmo, kaj se zgodi, če vstavimo nekaj oseb.
imena = ["Dani", "Ema", "Greta", "Berta", "Ana", "Cilka", "Fanči"]
t = Drevo()
for ime in imena:
t.dodaj(Oseba(ime, 0))
t.izpisi()
print("\n" + "-" * 20 + "\n")
Vrstni red vstavljanja oseb ni naključen, temveč prav premeteno hudoben. (Prepisan je iz knjige Niklausa Wirtha Algorithms + Data Structures = Programs, ki jo imamo v slovenščini kot "ta plavo knjigico" Računalniško programiranje. Wirth je avtor jezika Pascal in kopice drugih vplivnih jezikov, ki pa so danes bolj ali manj iz mode.) Čeprav na koncu dobimo še kar lepo drevo, je vrstni red sestavljen tako, da gre vmes narobe vse, kar lahko gre narobe. Boste videli, zakaj.
Mimogrede opazimo, da so osebe izpisane po abecedi, kar je dobro, saj pomeni, da je drevo pravilno sestavljeno.
Zdaj pa poglejmo prvo težavo: po tretjem koraku, ko vstavimo Greto, drevo ni več uravnoteženo, ker ima Dani na desni strani poddrevo višine 2, na levi pa ničesar.
Obrati¶
Doslej nismo naredili nič drugega, kot da smo dodali spremljanje višine dreves. Po vstavljanju lahko vidimo, ali je šlo kaj narobe in lahko to popravimo.
Razmišljali bomo le o vstavljanju na levo stran. Desna stran je simetrična; ko bo sprogramirana leva, bomo vse skupaj le preplonkali z zamenjanima stranema.
AVL drevesa so simpatična, ker lahko gredo stvari narobe le na dva načina in oba je preprosto popraviti.
Prvi scenarij: levo-levi¶
Vstavljali smo na levo stran - rekli smo, da bomo spremljali le vstavljanje na levo - in pri tem se je v vozlišču porušilo ravnotežje. To se lahko zgodi, ker se je povečal levi ali pa desni vnuk. Začnimo z levim; to je namreč preprostejše rešiti.
Preden nadaljujemo, pojasnimo nekaj pomembnega: ravnotežje se ne poruši nujno v vozlišču, na katerega smo pripeli nov list (še več, prav tam se ne more porušiti!). Zaradi dodanega lista se lahko poruši ravnotežje kjerkoli višje v drevesu. Lahko imamo drevo višine 10 in ko nekje čisto spodaj dodamo list, ostane znotraj drevesa vse v redu, ravnotežje v korenu pa se poruši. (Tak primer si je pravzaprav preprosto zamisliti: recimo, da je na levi strani korena čisto polno poddrevo višine 9, na levi pa čisto polno poddrevo višine 8. Če dodamo na levi strani nov list, je levo poddrevo še vedno super - ostalo je polno, čeprav ne čisto polno. Desno poddrevo je ostalo čisto polno in popolno. Porušilo pa se je ravnotežje v korenu, saj ima na levi drevo višine 10, na desni pa drevo višine 8, kar je pri AVL drevesih prepovedano.)
Vozlišča smo označili z vozlisce - to je vozlišče, pri katerem je prišlo do pretiranega visenja v levo, oče - oče tega vozlišča (s tem, da je to vozlišče, kjer imamo neravnovesje, lahko levi ali pa desni otrok tega očeta) in otrok - tisti, ki je vsega skupaj kriv, ker se je povečalo njegovo poddrevo na levi (s tem, kako ukrepati, če se poveča njegovo poddrevo na desni, se bomo ukvarjali kasneje, to je drugi scenarij). Na desni visi še njegov nepomembni brat, ki je premalo visok. Brata smo narisali, kot da je neuravnotežen; to ni čisto nujno, morda sta obe njegovi poddrevesi enako visoki. Vsekakor pa je večje od njiju za 2 manjše od levega otrokovega - odtod neuravnoteženost.
Pravokotniki predstavljajo drevesa, ki visijo pod otrokom in pod bratom. Rdeči pravokotnik predstavlja dodano vozlišče.
Drevo bomo popravili tako, da bomo dvignili otroka in spustili vozlisce, kot kaže slika. Otrok bo postal levi otrok očeta, vozlišče pa desni otrok otroka. Bivši desni otrok otroka (B) bo po novem levi otrok vozlišča, brat pa bo ostal, kjer je bil - vendar bo šel en nivo nižje zato, ker je šlo en nivo nižje vozlišče.
Poddreves, označenih s pravokotniki A, B, C in D nismo spreminjali, pa tudi brata ne. Premetali smo le vozlišče in otroka.
Bratova uravnoteženost se s tem ni spremenila. Vidimo pa, da to zagotovo uravnoteži otroka in vozlišče. Višina celotnega poddrevesa se zaradi tega vstavljanja ni spremenila.
Je drevo še vedno pravilno urejeno? Je. A je še vedno levo od otroka. B je po vrstnem redu med sinom in vozliščem. Prej je bil desno od sina (ki je bil levo od vozlišča), zdaj pa je levo od vozlišča (ki je desno od sina). Brat s svojima poddrevesoma je bil prej desno od vozlišča in zdaj je še vedno tam.
Zamenjava vozlišča in otroka je torej uravnotežila drevo, ne da bi pokvarila vrstni red. Še več: celotno poddrevo je ostalo enako visoko kot prej: v poddrevo A smo dodali novo vozlišče, vendar smo celotno poddrevo potem dvignili za en nivo, tako da je celotno drevo ostalo tako visoko, kot je bilo prej.
Obrat sprogramiramo tako:
otrok = vozlisce.levi
if otrok.levi.visina > otrok.desni.visina:
vozlisce.levi = otrok.desni
otrok.desni = vozlisce
self.pripni(otrok, oce)
vozlisce.preracunaj_visino()Vozlišču vozlisce po tem preobratu preračunamo višino (pravzaprav to niti ni potrebno; napisali bi lahko vozlisce.visina -= 1, saj je iz slike očitno, da je višina po obratu za 1 manjša kot prej).
Vozlišču otrok višine ne bomo niti preračunavali, saj je iz slike jasno, da se ni spremenila.
Isto ponovimo na desni strani in dodamo pogoje, ki ta obrat izvedejo, ko je to potrebno.
class Drevo:
def __init__(self):
self.koren = None
def poisci(self, ime):
def poisci0(vozlisce):
if not vozlisce:
return None
if vozlisce.ime == ime:
return vozlisce
if vozlisce.ime > ime:
return poisci0(vozlisce.levi)
else:
return poisci0(vozlisce.desni)
return poisci0(self.koren)
def izpisi(self):
def izpisi0(vozlisce, s):
if not vozlisce:
return
izpisi0(vozlisce.desni, s + " ")
print(s + "{} ({})".format(vozlisce.ime, vozlisce.visina))
izpisi0(vozlisce.levi, s + " ")
izpisi0(self.koren, "")
def pripni(self, koga, kam):
if not kam:
self.koren = koga
else:
if kam.ime > koga.ime:
kam.levi = koga
else:
kam.desni = koga
kam.preracunaj_visino()
def dodaj(self, nova_oseba):
def dodaj0(vozlisce, oce):
if vozlisce.ime == nova_oseba.ime:
return
if vozlisce.ime > nova_oseba.ime:
if vozlisce.levi:
dodaj0(vozlisce.levi, vozlisce)
else:
vozlisce.levi = nova_oseba
else:
if vozlisce.desni:
dodaj0(vozlisce.desni, vozlisce)
else:
vozlisce.desni = nova_oseba
vozlisce.preracunaj_visino()
if vozlisce.levi.visina > vozlisce.desni.visina + 1:
otrok = vozlisce.levi
if otrok.levi.visina > otrok.desni.visina:
vozlisce.levi = otrok.desni
otrok.desni = vozlisce
self.pripni(otrok, oce)
vozlisce.preracunaj_visino()
elif vozlisce.desni.visina > vozlisce.levi.visina + 1:
otrok = vozlisce.desni
if otrok.desni.visina > otrok.levi.visina:
vozlisce.desni = otrok.levi
otrok.levi = vozlisce
self.pripni(otrok, oce)
vozlisce.preracunaj_visino()
if not self.koren:
self.koren = nova_oseba
else:
dodaj0(self.koren, None)
Pogoji pravijo: če je drevo na levi za več kot 1 večje od desnega, preveri, ali je kriv levi vnuk (kriv je pač tisti, ki je višji, drugače ne more biti). V tem primeru izvedi obrat, ki smo ga opisali zgoraj.
Nato se vse skupaj ponovi z zamenjanima smerema.
Poglejmo, kaj to pomeni za naše vstavljanje oseb.
imena = ["Dani", "Ema", "Greta", "Berta", "Ana", "Cilka", "Fanči"]
t = Drevo()
for ime in imena:
t.dodaj(Oseba(ime, 0))
t.izpisi()
print("\n" + "-" * 20 + "\n")
Pri sestavljanju tega drevesa se že uporabita oba obrata, v levo in v desno. Ko dodamo Dani, Emo in Greto, dobimo drevo, ki visi v desno.
Greta (1)
Ema (2)
Dani (3)Razlog, da nikoli nismo videli te slike, je v tem, da se tule sproži obračanje (spodnja koda, ko je previsoko desno drevo), ki postavi Emo v koren.
Greta (1)
Ema (2)
Dani (1)Berto dodamo brez incidentov. Ko pride še Ana, drevo pod Dani visi v levo.
Greta (1)
Ema (3)
Dani (3)
Berta (2)
Ana (1)Sproži se torej uravnotežanje pod Dani (vozlisce je Dani, otrok je Berta), ki postavi Berto v koren tega poddrevesa.
Nato dodamo Cilko. Gre levo od Eme, desno od Berte, levo od Dani.
Zdaj je drevo neuravnoteženo pri Emi. Na njeni levi (spodnji) strani je drevo višine 3, na levi pa le Greta. Tega vrtenja pa še nimamo.
Drugi scenarij: levo-desni¶
Čeprav bi moralo biti na prvi pogled podobno, je tole bolj zoprno.
Problem je, tako kot prej, v vozlišču vozlisce, le da je zdaj preveliko drevo B. Ker je B za več kot za dva večje od C (in D - pri čemer sta C in D mora enaka, morda pa je eno še za 1 manjše), je poddrevo levo od vozlisce za več kot dva višje od poddrevesa desno od vozlisce.
Prej smo reč uredili tako, da smo otroka potegnili gor, preveliko drevo je bilo takoj pod otrokom (tako da je bilo en nivo višji), nižja drevesa pa so se zvrstila desno od otroka.
Tule pa ta trik ne bo vžgal. Če potegnemo otroka gor, bi radi obdržali na višjem nivoju njegovega desnega otroka. To pa ne bo šlo, ker mora biti desno od otroka vozlisce.
Da uredimo tale drevesa, bo potrebno pogledati vnuka in razmišljati o njegovih poddrevesih. Obrat je takšen.
Razlog, da temu sploh rečejo obrat (kaj okrog česa?) je, v tem, da se da to izvesti kot kombinacijo enega desnega obrata, ki prevede položaj na to, kar imamo zgoraj, in nato enega levega, kakršen je zgornji. Vendar ne bomo po nepotrebnem zapletali in gledali na vse skupaj v enem zamahu. Najprej se prepričajmo, da vse skupaj deluje, nato razmislimo, kako.
Slika je malenkost zavajajoča. V resnici ne vemo, katero poddrevo je zaradi dodajanja novega elementa postalo preveliko, B1 ali B2. To tudi ni pomembno. Vemo tudi, recimo, da je preveliko le eno od njiju. A tudi to ni pomembno.
Najprej preverimo, ali je drevo še vedno urejeno. Vozlišča, ki smo jih poimenovali, so urejena pravilno - otrok je levo od vnuka, vnuk levo od vozlisce, vozlisce levo od brat. Ureditev je na obeh straneh enaka. Nekateri to opišejo tako, da rečejo, da vozlišče premikamo le vertikalno in ne horizontalno.
Prav tako vertikalno premikamo poddrevesa. So v enakem vrstnem redu kot prej, pa tudi njihov položaj glede na poimenovana vozlišča je enak kot prej. Drevo A je bilo in ostaja skrajno levo. B1 je med otrok in vnuk - tam je bilo in tam ostaja. B2 je posebej zvit: prej je bil desno od vnuka in levo od vozlišča. Tudi po obratu je desno od vnuka in levo od vozlišča. Brat s svojimi drevesi je bil in ostaja čisto na desni.
Z obratom torej nismo porušili vrstnega reda. Smo uravnotežili drevo?
Obe drevesi, B1 in B2 smo prestavili en nivo višje, brata pa en nivo nižje. Predpostavimo, da je bilo v resnici previsoko B1, kot kaže slika. B1 je bilo pred dodajanjem novega elementa poravnano z A (če ne bi bilo tako, bi bilo drevo A že pred dodajanjem novega elementa previsoko!). Ker je šlo z obratom B1 za en nivo višje, sta zdaj spet poravnana. Vozlišče otrok je torej zdaj popolnoma poravnano.
Pač pa, kot kaže slika, vozlisce zdaj visi v desno, ker B2 ni poravnan z drevesoma pod bratom (s C ali D ali obema). A nič ne de; razlika je le 1, torej je drevo, glede na kriterij AVL, uravnoteženo.
Če pa smo neuravnoteženost dobili zaradi dodatnega elementa v B2 in ne B1 (tega slika ne kaže), je zdaj poravnano vozlisce, otrok pa visi v levo.
Te, zadnje opazke, lahko sicer izkoristimo pri programiranju - a jih ne bomo. Po obratu bomo vsem udeleženim vozliščem preprosto rekli, naj ponovno izračunajo svoje višine.
Celoten obrat sprogramiramo takole:
vnuk = otrok.desni
otrok.desni, vozlisce.levi = vnuk.levi, vnuk.desni
vnuk.levi, vnuk.desni = otrok, vozlisce
self.pripni(vnuk, oce)
otrok.preracunaj_visino()
vozlisce.preracunaj_visino()
vnuk.preracunaj_visino()Prirejanja so očitna - pač takšna kot na sliki - le na vrstni red moramo paziti, da ne izgubimo kakega vozlišča. Nato pripnemo vnuka pod očeta. Na koncu preračunamo višine; najprej otrok in vozlisce, ki sta spodaj, in šele nato vnuk. Takšen vrstni red je potreben zato, ker vnuk svojo višino izračuna na podlagi višin otroka in vozlišča.
Celoten razred je zdaj takšen.
class Drevo:
def __init__(self):
self.koren = None
def poisci(self, ime):
def poisci0(vozlisce):
if not vozlisce:
return None
if vozlisce.ime == ime:
return vozlisce
if vozlisce.ime > ime:
return poisci0(vozlisce.levi)
else:
return poisci0(vozlisce.desni)
return poisci0(self.koren)
def izpisi(self):
def izpisi0(vozlisce, s):
if not vozlisce:
return
izpisi0(vozlisce.desni, s + " ")
print(s + "{} ({})".format(vozlisce.ime, vozlisce.visina))
izpisi0(vozlisce.levi, s + " ")
izpisi0(self.koren, "")
def pripni(self, koga, kam):
if not kam:
self.koren = koga
else:
if kam.ime > koga.ime:
kam.levi = koga
else:
kam.desni = koga
kam.preracunaj_visino()
def dodaj(self, nova_oseba):
def dodaj0(vozlisce, oce):
if vozlisce.ime == nova_oseba.ime:
return
if vozlisce.ime > nova_oseba.ime:
if vozlisce.levi:
dodaj0(vozlisce.levi, vozlisce)
else:
vozlisce.levi = nova_oseba
else:
if vozlisce.desni:
dodaj0(vozlisce.desni, vozlisce)
else:
vozlisce.desni = nova_oseba
vozlisce.preracunaj_visino()
if vozlisce.levi.visina > vozlisce.desni.visina + 1:
otrok = vozlisce.levi
if otrok.levi.visina > otrok.desni.visina:
vozlisce.levi = otrok.desni
otrok.desni = vozlisce
self.pripni(otrok, oce)
vozlisce.preracunaj_visino()
else:
vnuk = otrok.desni
otrok.desni, vozlisce.levi = vnuk.levi, vnuk.desni
vnuk.levi, vnuk.desni = otrok, vozlisce
self.pripni(vnuk, oce)
otrok.preracunaj_visino()
vozlisce.preracunaj_visino()
vnuk.preracunaj_visino()
elif vozlisce.desni.visina > vozlisce.levi.visina + 1:
otrok = vozlisce.desni
if otrok.desni.visina > otrok.levi.visina:
vozlisce.desni = otrok.levi
otrok.levi = vozlisce
self.pripni(otrok, oce)
vozlisce.preracunaj_visino()
else:
vnuk = otrok.levi
otrok.levi, vozlisce.desni = vnuk.desni, vnuk.levi
vnuk.desni, vnuk.levi = otrok, vozlisce
self.pripni(vnuk, oce)
otrok.preracunaj_visino()
vozlisce.preracunaj_visino()
vnuk.preracunaj_visino()
if not self.koren:
self.koren = nova_oseba
else:
dodaj0(self.koren, None)
imena = ["Dani", "Ema", "Greta", "Berta", "Ana", "Cilka", "Fanči"]
t = Drevo()
for ime in imena:
t.dodaj(Oseba(ime, 0))
t.izpisi()
print("\n" + "-" * 20 + "\n")
Zmaga¶
Zdaj pa res lahko razglasimo zmago.
Naše drevo ni popolnoma uravnoteženo, vendar je njegova velikost vedno manjša od $\log_\varphi(\sqrt 5 (n+2)) - 2 = { \log_2(\sqrt 5 (n+2)) \over \log_2(\varphi) } - 2 = \log_\varphi(2) \cdot \log_2(\sqrt 5 (n+2)) - 2 \approx 1.44\log_2(n+2) - 0.328$, kjer je $\phi$ zlato razmerje, $\frac{1 + \sqrt{5}}{2}$. (Odkod to, si približno predstavljam, vendar nisem še nikoli računal, vsaj ne da bi se spomnil. ;) Formulo sem skopiral z Wikipedije.)
Ker njegova velikost narašča z logaritmom števila vozlišč, je logaritemska tudi časovna zahtevnost iskanja.
Prav tako je logaritemska časovna zahtevnost vstavljanja. Za vstavljanje moramo najprej poiskati mesto, kamor bomo vstavljali (kar je enako hitro kot iskanje), potem pa moramo morda malo popraviti drevo. Vendar popravljamo največ toliko vozlišč, kolikor je drevo globoko. Število popravljanj je torej sorazmerno logaritmu višine, čas, ki ga potrebujemo za eno popravljanje, pa je neodvisen od velikosti drevesa. Skupen čas vstavljanja je torej spet sorazmeren logaritmu velikosti drevesa.
Brisanje¶
Drevesa morajo podpirati tudi brisanje vozlišč.
Pri vseh urejenimi drevesi - ne glede na to, ali so uravnotežena ali ne - za brisanje uporabimo isti trik. Če imamo to srečo, da je potrebno pobrisati list, ga pač pobrišemo. Če brišemo kakšno notranje vozlišče, pa poiščemo največji element v njegovem levem poddrevesu. Gremo torej v levo poddrevo in se peljemo po samih desnih vejah, dokler ne pridemo do vozlišča, ki nima več desne veje. To je največji element, ki je manjši od pobrisanega.
Ta element prestavimo na mesto v drevesu, kjer je bil pobrisani element. S tem drevesa nismo pokvarili: vsi v levem poddrevesu so manjši od tega, prestavljenega elementa, saj je bil to največji element levega poddrevesa. Po drugi strani so vsi elementi v desnem poddrevesu večji od njega, saj je ta, prestavljeni element, z levega poddrevesa in vsi v levem so manjši od vseh v desnem.
Kaj naredimo z otroki prestavljenega elementa? Imel je kvečjemu enega (če bi imel dva, bi to pomenilo, da nismo šli po desnih vejah do konca in torej obstaja v levem poddrevesu nek še večji element!). Tega, edinega otroka (in z njim pa vse poddrevo, ki je pod njim) pripnemo na mesto, kjer je bil prej prestavljeni element.
Nekako tako (na tem drevesu deluje, lahko pa sem se tudi kje zmotil).
def pobrisi(self, ime):
def pobrisi0(vozlisce, oce):
def najvecji(vozlisce, oce):
if vozlisce.desni:
return najvecji(vozlisce.desni, vozlisce)
else:
return vozlisce, oce
if not vozlisce:
return
if ime < vozlisce.ime:
pobrisi0(vozlisce.levi, vozlisce)
elif ime > vozlisce.ime:
pobrisi0(vozlisce.desni, vozlisce)
else: # brišemo TO vozlišče
if not vozlisce.levi and not vozlisce.desni:
if not oce:
self.root = None
elif ime < oce.ime:
oce.levi = Nikamor
else:
oce.desni = Nikamor
elif not vozlisce.levi:
self.pripni(oce, vozlisce.desni)
elif not vozlisce.levi.desni:
vozlisce.levi.desni = vozlisce.desni
self.pripni(vozlisce.levi, oce)
else:
najvecji, naj_oce = najvecji(vozlisce, oce)
naj_oce.desni = najvecji.levi
vozlisce.ime = najvecji.ime
vozlisce.stevilka = najvecji.stevilkaZdaj pa manjka še uravnoteževanje. To je odvisno od tega, s kakšnimi drevesi delamo. Pri AVL drevesih naredimo nekaj podobnega kot prej: za vsa drevesa nad tistim, ki smo ga prestavljali preverimo, ali se je ravnotežje porušilo in po potrebi naredimo obrate, kakršne smo opisali zgoraj.