Algoritmid ja andmestruktuurid konspekt - puud (0)

Puu on rekursiivne, seega ka enamik algoritme, mis temaga rakendada, on rekursiivsed. Kuid iga 
rekursiivset algoritmi saab esitada ka iteratiiselt, nagu enne juttugi oli. Kui  juur välja jätta, siis 
kõigil teistel tipul on olemas ematipp ja ematippudel(parent) on omakorda tütartipud( child ). Sama 
emaga  tipud  on õed(siblings).
Kui meil on mitu puud, võime rääkida metsast( forest ). Luline on rääkida veel puu kõrgusest. Puu 
jaguneb nivoodeks. Nivoode hulk on puu kõrgus. Mõnes õpikus võib näha ka teistsugust 
definitsiooni puu kõrguse kohta.
Järjestatud puu, järjestamata puu. Kui on oluline, mis järjekorras mööda nivood vasakult paremale 
liikudes õed mis järjekorras paiknevad, siis järjestatud puu.
Ülespoole järjestatud puud veel jne.
Binary  search tree(kahendotsingu puu).  
Ehitamisel  - Kui järgmine kirje on väiksem, siis vasakule, kui suurem, siis paremale. Kui midagi 
ees pole, siis teeme uue kaare ja uue tipu. Jne. Kui on, siis mine mööda seda edasi, kuni enam pole.
Otsimisel - Igas  tipus  tuleb teha üks võrdlus, sõltuvalt sellest minna kas vasakule või paremale. Kui 
satume tühjale kohale, siis otsitavat kirjet ei olegi.
Kui 2 kirjet on võrdsete võtmetega, siis sellisel juhul on 2 lahendust . Primaarsed ja sekundaarsed 
võtmed. Need võtmed, mille järgi puud ehitame, on primaarsed. Kui primaarsed võtmed langevad 
kokku, siis hakatakse võrdlema sekundaarseid võtmeid ja väiksemaks loetakse see, mille puhul 
sekundaarne  võti on väiksem. Nt primaarne võti on inimese nimi ja sekundaarne on inimese vanus.
Teine võimalus on see, et  paneme  teise tipu juurde rohkem kui üks kirjet. See lahendus on halvem , 
teeb puud keerulisemaks.
Kolmas – väiksem-võrdne vasakule, suurem-võrdne paremale. 
Tõmbame joone ülalt alla...kõik nrid, mis joonest vasakul on väiksemad nendest  nr-test, mis on 
joonest paremal. Ükskõik, mis tipu jaoks tõmbame sellise joone, tulemus on ikka sarnane.
Kuidas leida kõige väiksema võtmega kirje. Hakata juurest minema ja  liikuda  kogu aeg aina 
vasakule. Kui enam vasakule minna ei saa, siis ongi leitud. Kõige suurema otsimise puhul paremale 
samamoodi.
Andmestruktuurina - Tipp võiks koosneda kolmest viidast...üks  viit  on kirjele, üks vasakpoolsele 
tütrele, teine parempoolsele tütrele.
Operatsioonid  – loo tühi puu(ühtki juurt ega tippu). Loo uus kirje puusse. Eemalda kirje ja koos 
temaga vastav tipp puust. Puu likvideerimine. Ümber midagi paigutada ei saa, järjekord on 
võtmetega täiesti üheselt määratud. Kahendotsingu puu on järjestatud puu, sest vasakpoolse tütre 
võti on igal juhul väiksem kui parempoolse.
Teine variant.  Left  ja right pole enam  viidad , vaid indeksid. 0 tähistab olukorda, kus tütartippe pole. 
Sügavat mõtet sellisel lahendusel pole. Tuleks kõne alla vaid sellise progemiskeele juures, kus 
viitasid ei tunta. Tänapäeval aga selliseid progemiskeeli ei ole.  Kaudselt  on kõigil olemas, neid 
lihtsalt ei nimetata nii. Nim  reference 'iks, mitte pointeriks ja viitade aritmeetikat seal teha ei saa (nt 
C#).
Kirje eemaldamine – kui ühtki tütartippu kirjel pole, siis peab lihtsalt tema ematipu right viida 0-ks 
viima. Kui tahan 32 eemaldada, siis 23 läheb minema ja 30 hakkab viitama  26-le. Kui tahan 30 
eemaldada, siis...
Iga puuharu võib vaadelda eraldi puuna, probleem tekib siis, kui tuleb eemaldada juur.
Kui 58 eemaldan, siis tekib 2 omavahel mitte seotud haru. Ühe juuresk 37, teise juureks 75. sinise 
haru kõik võtme don rohelise haru kõikidest võtmetest suuremad. Miinimumi leidmiseks liikuda 
pidevalt avsakule, järelikult sinise haru miinimumiks on 61. Ikkagi on ta suurem kui mistahes võti 
rohelisest harust. Seega võtan terve sinise haru ja terve rohelise haru ning tõmban 61-st kaare 37-
sse. Võttes aluseks parempoolne haru, tõmban kaare selle miinimumist vasakpoolse haru juurtipuu. 
Oleks võinud vütta aluseks ka vasakpoolse haru. Mõlemat pidi võib. Praegu lisame lihtsalt 61-le 
viide  37-le, kõik muu jääb paika. Väga lihtne. Füüsiliselt midagi ei  liiguta .
Mõningaid operatsioone puudel keeruline läbi viia, kuna viidad on alati vaid ühes suunas – ülalt 
alla. Viidad on ainult emadelt tütardele. On olemas ka teistsugune puu – läbiõmmeldud puu – kuid 
sellega töötamine on äärmiselt tülikas, kuna iga kord tuleb muuta mitte 1 viita , vaid mitut.
Probleem -  Mõnus andmestruktuur nt andmebaasi  esitamiseks , aga kui tahan saada mingeid 
andmeid  paberil , siis seda puud ikka trükkima ei hakka.
Puu läbi käimine - Me peame leidma  algoritmid , millega külastatakse puu iga tippu, ükski tipp ei 
jää vahele ja ühtki tippu ei külastata rohkem kui üks kord. Nt kui tahame puud nimekirja kujul 
saada.
4 strateegiat.
1) Nivooti – probleem selles, et väga raske läbi viia, kuna viidad on meil ainult ülalt alla, aga 
vasakult paremale puuduvad. Praktiliselt teostamatu.
2) Süviti – vasak-parem juur. Algul külastame kõiki vasaku haru  tippe , siis kõiki parema haru 
tippe ja viimasena juurt. Mõlemas harus rakendame jälle omakorda sama taktikat.
3) Sümmeetriliselt – vasak-juur-parem. Nii saab kronoloogilise tulemuse. Nt nimekirja 
tähestiku järjekorras.
4) Laiuti - juur-vasak-parem
2,3,4 kõik rekursiivsed.
Külastuse eesmärgiks külastatav tipp hävitada ja et üldse puu mälust likvideerida, kõik tipud vabaks 
lasta – sellisel juhul tuleb külastada süviti strateegia järgi.
Proge  – antakse sisse viit puu juurele.
Sorditud loendi moodustamine puu põhjal.
Puu läbikäik sümmeetriliselt, aga mitte rekursiivselt. Kasutatud on stacki. Puu läbikäik(3). - läbi 
vaadata see näide.
Kaval progeja kasutab rekursiooni ikka siis, kui ta leiab, et see talle midagi annab.
Mida teha siis, kui ei ole tegemist kahendpuuga, vaid tütarde arv ei ole piiratud. Viit vektorile ning 
see  viitab omakorda tütardele. Viidad tütardele on ühes vektoris, kui üks tütar tuleb juurde, siis tuleb 
seda vektorit pikendada. Ei ole kõige parem lahendus.
Parem lahendus. Teha tipp  selliselt , et seal on viit kirjele. Tütarde puhul on viit ainult kõige 
vasakpoolsemale tütrele ning temast vahetult paremale asuvale õele. Sellisel juhul on viitade arv 
tipus täpselt kolm ja see arv pole muutuv. Kui  joonistame  need viidad veidi teisiti, siis saame 
kahendpuu. Seega oleme teisendanud paljuharulise puu kahendpuuks. Selle vahega, et viidad on 
veidi erinevad.
Äkki paneks viidad hoopis tütrelt emale, mitte vastupidi? Palju vähem viitasid tuleks ju. A-l ei ole 
ematippu, seetõttu on indeks 0. Näites  vektor  indeksitega. Selline lahendus töötab ainult siis, kui 
tegemist on järjestamata  puuga , sets siit enam ei saa välja lugeda, mis järjekorras õed on.
Kui efektiivsed puud kui  struktuurid on? Mida madalam on puu, mida vähem on tal nivoosid, seda 
vähem tuleb otsimisel teha ka võrdusi. Millest puu nivoode arv sõltub? - kirjete  arvust ning mis 
järjekorras  kirjed tulevad. Mida vähe võrdusi teha saab, seda parem puu on. Kõige halvem olukord 
on see, kus puust on saanud lineaarne loeng. Sellisel juhul kehtivad tema puhul ka kõik järjestikuse 
otsimise  parameetrid .
Kui on kindel tippude arv n, siis mida tihedamad on harud(nagu ilusal jõulukuusel), seda paremini 
on üksikud kirjed ära pakitud ja seda madalam on puu tervikuna . Selle kohta öeldakse, et puu on 
rohkem tasakaalus, sellel puul pole üksikuid harusid, mis on teistest tunduvalt kõrgmad. Kõige 
parem oleks, kui kõik harud on ühekõrgused. Sel puhul on puu absoluutselt tasakaalus. See on 
võimalik üksnes siis, kui kirjete arv n on kaks astmes k miinus  üks, kus k on mingi täisarv. Võrduste 
arv ei saa olla suurem, kui on puu kõrgus – see on loogiline. Kõik oleneb palju sellest, mis 
järjekorras kirjed tulevad, et millise kujuga puu tuleb. Juhuslikult genereeritud puu on tulemuseks. 
Antud juhul minimaalne kõrgus on 4 ning maksimaalne on 15 – siis kui ta on loendiks taandunud.
Kahendpuust otsimine on logaritmiline protsess – see on iseenesest väga hea.
Igasugune keskväärtus omab mõtet vaid siis, kui kaldumised keskväärtusest ei ole liiga suured. 
Sellepärast on ka sellised mõisted nagu keskmine palk täiesti mõttetud, kuna see ei näita midagi, 
kuna kõrvalekaldumised on väga suured.
Puu modifitseerimisel  kipub  puu tasakaal kaduma, puu välja venima. Eriti eemaldamisega. Vt üht 
eelmist näidet.
Kuidasmoodi saavutada seda, et puu oleks rohkem tasakaalus? Sellisel juhul on võimalik võrduste 
arv ka ilmselt väiksem ja algoritmid muutuvad kiiremaks. 
AVL puu – peaaegu tasakaalus puu. Igale tipule leitakse nn tasakaalutegur – st mõõdetakse ta 
parempoolse haru kõrgus ning vasakpoolse haru kõrgus ning leitakse nende vahe. Võib olla 0, 
+1(parempoolne haru 1 võrra kõrgem kui vasak) või -1 AVL puu puhul. Näitel  rohelisega  kirjas 
tasakaalutegurid. AVL puud saab teha alati!
Hakkame puud ehitama, igal  sammul  arvutame välja kõikide tippude tasakaalutegurid. Seni, kuni 
need on on 0,-1 või +1, ei tee me midagi. Kui mõni läheb lubatud piiridest välja, siis hakkame 
midagi tegema, et tasakaalutegurid uuesti normi viia. Meetod, mida kasut. - puu pööramine ehk 
rotatsioon .
4 olukorda, kus puu ehitamisel enam pole AVL puu. 2 lihtsamad, 2 keerulised.
Lihtsad:  AVL puud(2) – iga pilt kujutab üht fragmenti. Harude kõrgused on „h“. 
U läheb ühe nivoo võrra allapoole, V tuleb ühe nivoo võrra ülespoole, A ja C jäävad oma kohtadele, 
B oli enne V vasakpoolne tütar, nüüd pn ta U parempoolne tütar. Tegemist on jällegi viitade 
ümbertõstmisega, midagi füüsiliselt ümber paigutama ei pea. Probleem tekib aga siis, kui U ei ole 
absoluutne juur, vaid tal on omakorda ematipp. Järelikult tuleb ematipu viitasid vahetada. Aga 
kuidas seda teha, meil pole ju alt üles näitavaid viitasid? Tegelt see lihtne, aga hiljem kunagi 
räägime sellest.