Tree
Iz E-študij, proste zakladnice študentskega znanja
Drevo(tree) sestavlja množica elementov – vozlišč. Vozlišča so povezana na podlagi relacije, ki določa hierarhično strukturo.
Drevesa v sistemu e-Študent rišemo s pomočjo dodatka Pomoč:Graphviz.
Vsebina |
Primer drevesa
Kazalo v knjigi (relacija: vsebovanost):
- kazalo vsebuje poglavja
- poglavje vsebuje podpoglavja
- podpoglavje vsebuje odstavke
- odstavki vsebujejo stavke
- itd...
- odstavki vsebujejo stavke
- podpoglavje vsebuje odstavke
- poglavje vsebuje podpoglavja
Vsako podpoglavje je samostojna drevesna struktura. Vsak odstavek je samostojna drevesna struktura - poddrevo.
Formalna definicija
Drevesna struktura z osnovnim tipom T je:
- prazna struktura
ali
- vozlišče tipa T, kateremu je prirejeno končno število tujih drevesnih struktur z osnovnim tipom T (poddreves)
Ponazoritev
Drevesa se ponazori z grafom.
Primeri grafov odločitvenega drevesa
- pet zlatnikov, eden je ponaredek (je lažji)
- iščemo ga s tehtanjem
Začnemo s tehtanjem 1,2 in 3,4 zlatnika, po dva skupaj na eni strani tehtnice.
Pojmi
- koren
- Koren je prvi element v grafu. Koren podgrafa je vozlišče, ki se nahaja na najvišji točki v podgrafu.
- vozlišče
- vsak krogec
- list
- vozlišče, ki nima nobenega naslednika - končni element
- poddrevo
- Poddrevo dobimo, če vzamemo eno samo vozlišče in ga "odklopimo" od vozlišča nad njim
- naddrevo
- Naddrevo je drevo katero vsebuje vozlišče, ki je koren trenutnega drevesa.
- naslednik
- Naslednik je vsak element nižje od vozlišča do katerega lahko pridemo po poti navzdol.
- prednik
- Prednik je vsak element višje od vozlišča do katerega lahko pridemo po poti navzgor.
- neposredni naslednik (sin)
- do njega pridemo po 1 poti navzdol
- neposredni predhodnik (oče)
- do njega pridemo po 1 poti navzgor
- notranji element
- elementi, ki niso listi
- nivo
- elementi, ki so oddaljeni enako število vozlišč, so na istem nivoju (višini)
- koren je na nivoju 0
- globina vozlišča
- število korakov od korena do vozlišča
- vsa vozlišča povezana neposredno na koren so v globini 1
- višina drevesa
- največja globina kateregakoli vozlišča (globina najnižjega lista)
- stopnja vozlišča
- število naslednikov vozlišča
- stopnja drevesa (dvojiška, trojiška drevesa)
- najvišja stopnja vozlišča dosežena znotraj drevesa
- dvojiško(binarno) drevo ima stopnjo 2 (npr primerjanje true/false)
- trojiško drevo ima stopnjo 3 (npr primerjanje večji/manjši/enak)
- pot do vozlišča
- pot od korena do vozlišča
- vključuje vsa vozlišča preko katerih pot prepotujemo
- dolžina poti vozlišča
- je enaka globini vozlišča
- število korakov potrebnih za dostop do vozlišča
- dolžina poti drevesa
Vrste dreves
- polna drevesa
- izravnana (uravnotežena) drevesa
- iskalna drevesa
- polnost
- polno drevo ima vsa vozlišča polna (glede na stopnjo drevesa)
- polna (full)
- izpolnjena (complete)
- teži k čimmanjši višini
- uravnoteženost
- obe strani uravnoteženega drevesa naj bi bili čimbolj enake dolžine
- popolnoma izravnano drevo
- teži k temu da se drevo ne izrodi - da ne postane 1 veja zelo dolga
- urejenost
- vsako vozlišče ima nek (enak) pomen
- npr: vsako levo vozlišče dvojiškega drevesa predstavlja manjše in vsako desno večje
- omogoča enostavno iskanje
- dvojiško iskalno drevo (BST - binary search tree)
- večstopenjsko iskalno drevo (B drevo)
- AVL drevo (iskalno drevo, ki je hkrati uravnoteženo)
Lastnosti dreves
- Vsako vozlišče ima enolično pot do korena.
- Dolžina poti od korena do kateregakoli vozlišča <= višini drevesa
- Za polno drevo PD velja, da so stopnje vseh njegovih notranjih vozlišč enake (stopnji drevesa)
- PD (stopnja d, višina h) ima število vozlišč n: (dh+1–1)/(d–1)
- PD (stopnja d, število vozlišč n) ima višino h: logd(n*d-n+1)-1
Izpolnjeno drevo
Izpolnjeno drevo nima nujno vseh listov na istem nivoju, še vedno pa je polno drevo kjer so vsa vozlišča stopnje 0 (list) ali stopnje grafa.
Primer
- Polno dvojiško drevo (d=2)
- h=1: n= (22-1)/(2-1)=3
- h=2: n = 7
- h=10: n = 2047
- n=1000: h = log2(1001)-1=
- 9.97-1 = 9
- 106: h=19.93-1 = 19
Polno drevo
- Polno trojiško drevo (d=3)
- h=1: n=(31+1-1)/(3-1) = 4
- h=2: n = 13
- h=10: n = 88573
- n=1000: h=log3(2001)-1=6.92-1 = 6
- h=106: h=13.21-1 = 13
Vrste dreves
Popolnoma izravnano drevo
Za (popolnoma) izravnano (uravnoteženo) drevo velja, da se pri vsakem vozlišču število vozlišč njegovega levega in desnega poddrevesa razlikuje kvečjemu za 1.
Zgled: dvojiško popolnoma izravnano drevo z 1, 3, 4, 5, 6, 7, 8 vozlišči
7 | a | b | c | d | e | f | g
!!!
|
!!! !!!
- prvega damo v vozlišče
- polovico damo v eno poddrevo, drugo polovico v drugo
- ponavljamo rekurzivno
a | b | c | d | e | f | g | h | i | j | k !!!| | |!!!| | |!!!| | | |!!! |!!! | |!!! |!!!
Dvojiško iskalno drevo (Binary search tree)
Za vsako vozlišče iskalnega drevesa velja:
- (če je x vrednost trenutnega vozlišča)
- vrednost vsakega vozlišča v levem poddrevesu je manjša od x
- vrednost vsakega vozlišča v desnem poddrevesu je večja od x
- (vsaka vrednost se v drevesu nahaja samo v enem vozlišču)
Zgled: postopna izgradnja drevesa z vozlišči, ki imajo vrednosti:
{ 5, 2, 7, 1, 3, 4, 10, 8, 6, 5 }
5
5 2
7
postopno brisanje vozlišč z vrednostmi:
{5, 8, 3, 5, 3 }
Postopek:
- če elementa ni ne naredi nič
- če je index večji od 1, zmanjšaj index
- sicer
- če je element list, odstrani list
- sicer
- če ima najdeni element enega samega naslednika, izloči element
- sicer (ima 2 naslednika)
- nadomesti element z največjim elementom iz levega poddrevesa; izbriši ta element iz levega poddrevesa
Izločanje elementa 5
index se zmanjša
brisanje elementa 8
ker je 8 list se element izbriše
brisanje elementa 3
ker ima 3 enega naslednika se element izloči
brisanje 5:
uporabimo maksimalni element iz levega poddrevesa tako, da gremo:
- enkrat levo
- tolikokrat desno dokler se da
torej je pravi element za nadomeščanje: 4
brisanje 4:
enkrat levo gremo lahko, desno ne moremo več...
Obhod drevesa
- postopek, ki sistematično obišče vsa vozlišča drevesa (oziroma izvede
določeno operacijo na vseh vozliščih – tipično izpis)
Vrste obhodov
Uporabimo graf enačbe
( ( ( 5 - x ) * 2 - 4 ) / (8 + 4) ) + 6
Vrste obhodov:
- Obhod po nivojih (ang. breadth-first order http://en.wikipedia.org/wiki/Breadth-first_search)
- obhodimo vsak nivo posebej od najvišjega do najnižjega od leve proti desni
+ / 6 - + * 4 8 4 - 2 5 x
- Premi vrsti red (ang. pre-order)
- gledamo na drevo kot koren + levo poddrevo + desno poddrevo
- najprej izpiše koren, potem izpiše celotno levo poddrevo, potem celotno desno poddrevo
- operacija se ponavlja rekurzivno v vsakem korenu
+ / - * - 5 x 2 4 + 8 4 6
- Vmesni vrstni red (ang. inorder)
- izpiše v podobnem vrstnem redu kot premi
- najprej levo poddrevo, potem koren, potem desno poddrevo
- enako kot enačba brez oklepajev
5 - x * 2 - 4 / 8 + 4 + 6
- Obratni vrstni red (ang. post-order)
- najprej levo poddrevo, potem desno, potem koren
- postfiksni zapis (poljska notacija) matematičnega izraza
5 x - 2 * 4 - 8 4 + / 6 +
Tipična ponazoritev dreves v računalniku
- s pomočjo tabele, kjer vsak element tabele predstavlja eno vozlišče
(kot pri sortiranju s kopico)
- z (ustrezno) povezanimi objekti, ki predstavljajo posamezna vozlišča
Izvedba v Javi
razred BinaryTree ()
Povezave
- Tree Tutorial
- BinaryTreeSome applet (namenjen interaktivnemu učenju grajenja binarnih dreves in obhodov skozi njih)
