REŠENJE: Kako je zauzeto polje na poziciji 16 => mora biti zauzeto i polje na poziciji 8 za čuvanje oca čvora 16. Zato što po definiciji implicitne reprezentacije stabla preko niza, element A[16] odgovara čvoru čiji predak je čvor pridružen elementu A[8]. Sličnim rezonom, dolazi se do zaključka da moraju biti zauzete za pretke i pozicije 4, 2, 1. Dakle, minimalan broj elemenata je 5. ( log216 +1)
REŠENJE:
1. uklanja se proizvoljan element iz nekog hipa (npr. veći koren) i izvedu se popravke hipa na način koji je opisan u sekciji uklanjanja elementa iz hipa
2. izabrani element se umeće kao koren novog hipa, tako da njegovi sinovi budu koreni dva stara hipa
Popravka dobijenog hipa (stabla) uz eventualno premeštanje naniže elementa iz korena zahteva O( log(m+n)) koraka zbog dimenzije novog hipa.
REŠENJE: Broj rekurzivnih poziva jednak je broju čvorova stabla n, a trajanje svakog pozova je O(1), te je složenost algoritma O(n).
Željeni niz dobija se nadovezivanjem niza koji odgovara levom podstablu, ključa korena stabla i niza koji odgovara desnom podstablu.
III1. Odrediti najmanji i najveći broj čvorova koje može da ima AVL stablo visine h .
REŠENJE:
PRVI DEO ZADATKA je
određivanje najvećeg broja čvorova za AVL stablo visine h.
Neka je Gh oznaka za najveći broj čvorova stabla visine h.
Važi
G0=1 (samo koren čini AVL stablo visine 0),
Odavde sledi :
Gh+1 - Gh
= 2Gh + 1 - 2Gh-1 - 1
Dakle, važi:
Gh= C1 + C2* 2h
Rešenja ovog sistema su C1 = -1 i C2 = 2.
Formula za određivanje najvećeg broja cvorova koje
moze da ima AVL stablo visine h je:
Gh= -1 + 2h+1
G1=3 (koren i levo i desno dete čine AVL stablo visine 1),
G2=7 (koren, levo i desno dete, levi i desni unuk kao deca levog deteta, levi i desni unuk kao deca desnog deteta čine stablo visine 2) i:
Gh=Gh-1+Gh-1+1
Gh+1
- 3Gh+ 2Gh-1=0
Karakteristična jednacina ove rekurentne veze je:
t2-3t+2=0
odnosno (t-1)(t-2)=0
odakle sledi t1=1, t2=2.
Kako je:
1= C1 +C2
3= C1 +2* C2
Neka je Bh oznaka za AVL stablo visine h sa najmanjim brojem čvorova sa i neka je Nh oznaka za broj čvorova stabla Bh .
Nh=Nh-1+Nh-2+1
Nh+1=Nh+Nh-1+1
Nh+1- Nh =
Nh
+Nh-1+1- Nh-1- Nh-2-1
Nh+1 - 2Nh + Nh-2=0
Karakteristična jednačina ove rekurentne veze je
t3-2t2+1=0
odnosno (t-1)(t2-t-1)=0
odnosno njeni koreni su t1=1, t2= (1 +51/2)/2,
t3= (1 - 51/2)/2
Zato je opsti član niza Nh jednak
Nh
=
C1 + C2 * ((1 + 51/2)/2)h +
C3 * ((1 - 51/2)/2)h
Rešenja sistema su:
C1 = - 1
C2 = (51/2+2) /51/2
C3 = (51/2- 2) /51/2
III2. Elementi (međusobno različiti) nekog skupa S su smešteni u binarno stablo pretrage visine h. Konstruisati algoritam složenosti O(h) koji za dati element a skupa S određuje sledeći po veličini element skupa S.
Pretpostavimo da je stablo građeno tako da je informaciono polje (ključ) desnog sina veće ili jednako od informacionog polja (ključa) oca.
Sledbenik zadatog čvora je čvor sa najmanjim ključem koji je veći od ključa datog čvora.
Koji čvor nema sledbenika? Samo najdešnji čvor u stablu (koji nema desnog sina i koji je desni sin svog oca), jer je on čvor sa maksimalnom vrednošću ključa. (Na primer a=12)
Karakteristični slučajevi za čvor v čije informaciono polje (ključ) ima vrednost elementa a iz skupa S su:
Na primer: a=8 ili a=5 ili a=11
Ova operacija se najefikasnije izvodi ako se za svaki čvor čuva i polje otac sa pokazivačem na oca čvora. Tako se ide od čvora v prema korenu sve dok se ne nađe čvor w koji je levi sin svog oca. U slučaju da nema takvog pretka w, onda je a najveći element skupa i nema svog sledbenika.
Na primer: a=12 ili a=3
Sledi algoritam za nalaženje sledbenika za zadatu vrednost ključa čvora ukazanog sa v koji vraća adresu sledbenika ili NULL. Koristi se i poziv algoritma BST_MIN koji u BST (stablu binarnog pretraživanja) traži ključ sa minimalnom vrednošću.
Algoritam BST_MIN za BST čiji je koren ukazan argumentom node ide po lancu levih pokazivača sve dok ne dođe do čvora koji nema levog sina.
Algoritam BST_MIN pokriva 1. situaciju kada je potrebno pronači ključ sa minimalnom vrednošću u desnom podstablu čvora v.
Algoritam BST_SLEDBENIK (v) ulaz: v izlaz: q /* bilo da je NULL ili nije */ { pom=v if (right(pom) != NULL) return BST_MIN(right(pom)) /*1. situacija*/ else /* 2. situacija*/ { q=otac(pom) while (q != NULL ) and (pom == right(q)) do { pom=q q=otac(pom) } return q } } Algoritam BST_MIN(node) ulaz: node /*koren stabla ciji minimalni kljuc se trazi */ izlaz: p { p=node while (left(p) != NULL) do p=left(p) return p } Napomena: x=right(y) <= > x=y- > right . . .
Operacije nalaženja minimalnog ključa, sledbenika imaju vreme izvršavanja srazmerno visini stabla h, tj. O(h), jer u svakoj od situacija prate putanju kroz stablo samo u jednom smeru.
III3. Opisati realizaciju apstraktnog tipa podataka koji podržava sledeće operacije:
Umetni (x) | umetanje ključa x u strukturu podataka (ako već ne postoji) |
---|---|
Obrisi (x) | brisanje ključa x iz strukture podataka (ako postoji u strukturi) |
Naredni (x) | pronalaženje najamanjeg ključa u strukturi podataka koji je veći od x |
Izvršavanje svake od ovih operacija treba da ima vremensku složenost O(log n) u najgorem slučaju, gde je n broj elemenata u strukturi podataka.
Rešenje:
Za realizaciju navedenih operacija, pogodna struktura podataka je AVL stablo u kome se umetanje i brisanje izvršava za O(log n) koraka.
Za izvođenje operacije Naredni (x) koristi se
III4. Konstruisati algoritam koji proverava da li su jednaka dva zadata binarna stabla.
Resenje: Problem se moze resavati rekurzivnim algoritmom.
Testira se da li su dva
zadata binarna stabla neprazna:
III5. Konstruisati algoritam čija vremenska složenost je linearna po broju čvorova binarnog stabla i koji u stablu markira (označava) sve S-AVL čvorove čiji niti jedan potomak nije S-AVL čvor. Smatrati da čvor binarnog stabla je S-AVL čvor ako nije list i ako razlika visina njegovog levog i desnog podstabla je jednaka 0.
Algoritam SAVL (stablo x)
ulaz: stablo x
izlaz: dubina stabla kao oznacen broj
/* CILJ: ako algoritam vrati dubinu <0, to znači da se u stablu kao potomak pojavljuje SAVL cvor
ako algoritam vrati dubinu 0, to znači da stablo je list
algoritam vrati dubinu >0, to znači da SAVL čvor jos nije nađen
IDEJA:
1. Ako su dubine levog i desnog podstabla jednake i ako ni u levom ni u desnom podstablu se ne nalazi SAVL čvor (jer je vracena dubina >0),
tada se taj čvor markira, jer je SAVL čvor (npr. sa x->oznaka=1;). U tom slucaju vraća se negativna dubina stabla.
2. Ako nisu dubine levog i desnog podstabla jednake ili ako se u levom ili u desnom podstablu nalazi neki SAVL čvor (jer je vracena dubina <0),
tada se vraća dubina drveta sa predznakom, zavisno od toga da li je nađen SAVL čvor ili ne.
{
if (x==NULL) return 0;
else
{
levo=SAVL(x->levo);
desno=SAVL(x->desno);
if (levo >0 && desno >0)
if (levo==desno) /*situacija 1*/
{ x->oznaka=1; return -(levo+1);}
else
return max(levo, desno) +1;
else return -( 1+ max (abs(levo),
max(abs(desno));
}
Složenost algoritma
za n=1, T(n) =c1 (const za obradu stabla sa jednim cvorom)
za n>1, T(n)=n*c1*c2 (c2 je cena vremena koje obuhvata rekurzivni poziv SAVL algoritma i povratka) => T(n)=O(n) q.e.d.
III6. Konkatenacije je operacija nad dva skupa koja zadovoljavaju uslov da su svi ključevi u jednom skupu manji od svih ključeva u drugom skupu. Rezultat konkatenacije je unija skupova. Konstruisati algoritam za konkatenaciju dva binarna stabla pretrage u jedno stablo. Vremenska složenost algoritma mora biti O(h) u najgorem slučaju, gde h je veća od visina dva stabla.
REŠENJE:
Neka su zadata dva BSP stabla T, G, tako da svi ključevi stabla G su veći od svih ključeva stabla T.
Neka je bez smanjenja opštosti visina h stabla G veća od visine stabla T.
1. Pronaći u stablu G čvor v sa najmanjim ključem (npr, sve dok je moguće spuštati se niz stablo polazeći od korena ulevo i to se može obaviti za O(h) vremena)
2. Ukloniti čvor v iz stabla G (O(h) vremena)
3. Formirati za O(h) vremena novo stablo sa korenom v čija podstabla su stabla T (levo) i stablo G bez čvora v (desno) ). Novoformirano stablo ostaje binarno stablo pretrage, jer koren, tj. čvor v je sa najmanjim ključem u G, tako da desno podstablo može biti G. S druge strane, po uslovu s početka, svi ključevi stabla G (pa i v) su veći od svih ključeva stabla T, te T može biti levo podstablo.
III7. Isto to, ali za AVL stabla, tj. neka stabla T i G iz rešenja nisu samo BSP stabla, već AVL stabla.
REŠENJE:
Neka su zadata dva AVL stabla T, G, tako da svi ključevi stabla G su veći od svih ključeva stabla T.
Uz čvorove stabla T i G čuvaće se i informacija o visini, jer je to svojstvo značajano za AVL stabla, kao tip balansiranih stabala i neka je,
na primer, visina h2 stabla G sada manja ili jednaka od visine h1 stabla T. Drugi slučaj rešava se analogno.
1. Ukloniti najveći čvor iz stabla T, na primer čvor r i on će kao u prethodnom zadatku biti koren stabla preko kog se stablo G privezuje za T. Evo kako.
2. Spuštajući se u stablu T desnim granama, naći čvor v visine h2 ili h2-1 (a to je moguće jer h1>=h2). Neka otac čvora v jeste čvor p.
3. Postaviti da desni sin čvora p ne bude cvor v, vec čvor r iz koraka 1. (što je održava poredak, jer čvor r je sa najvećim ključem, te može biti desni sin čvora p)
4. Postaviti da levi sin čvora r bude cvor v sa podstablom T, a desni sin koren G. To je u redu sa stanovista BSP svojstva, jer r je najveci čvor u T. te je ključ čvora v ne veći od njega i može biti levi sin, a kako svaki čvor stabla G, te i koren je veći od najvećeg ključa iz T, onda koren iz G može biti desni sin sa ciljem da i novoformirano stablo bude binarno stablo pretrage (BSP).
5. U koracima 3 i 4 formirano je stablo koje ima BSP svojstva, ali možda nije uravnoteženo, tj. visina čvora r može da postane veća za 1 od visine čvora v koji je bio na tom mestu, te je nuzno obaviti eventualno uravnotezenje pomocu rotacije.
Sve operacije traju <=O(h1) koraka zbog svojstva AVL stabla.
III8.
AVL stablo visine h ima bar Fh+3 - 1 čvorova, gde Fi je i -ti Fibonačijev broj (h>=0).
Dokaz:
Neka Th je ukupan broj čvorova (dakle, ne ukupan broj unutrašnjih čvorova) u AVL stablu Dh visine h sa najmanjim mogućim brojem čvorova.
Jasno da je
T0=1
T1=2
Takođe
T0 = F3 -1 = 2- 1 =1
T1 = F4 -1 = 3- 1 =2
Kako Dh je AVL stablo visine h sa najmanjim mogućim brojem čvorova, to ono mora imati podstabla visine h-1 i h-2 (zato što bar jedno podstablo mora biti visine h-1, dok zbog uslova balansiranosti visina podstabala se mora razlikovati najviše za jedan). Takodje, ta podstabla moraju biti stabla visine h-1, odnosno h-2, sa najmanjim mogućim brojem čvorova.
Otuda važi relacija:
Th=Th-1+Th-2+1
< = > Th+1 = (Th-1+1) + (Th-2+1)
Za vrednosti Th+1 važi ista diferencna j-na kao i za Fibonačijeve brojeve Fh:
F1 = F2
Fh + 2 = Fh + 1 + Fh , h >= 2
Dokaz se, dalje, kompletira korišćenjem indukcije.
Teorijska osnova: Liste povezanosti
IV1.Neka je G=(V,E) stablo sa n čvorova. Cilj je formirati simetričnu kvadratnu matricu reda n, čiji elemenat (i,j) je jednak rastojanju između čvorova vi i vj. Konstruisati algoritam složenosti O (n 2) koji rešava ovaj problem ako je stablo zadato listom povezanosti.
matrica rastojanja A | ... | i | ... | n |
... | ||||
j | dS (vi,vj) | |||
... | ||||
n |
POLAZNE PRETPOSTAVKE I OZNAKE:
Neka je dato stablo S sa n čvorova i
neka v je list tog stabla i
neka w je jedini čvor susedan sa v (po definiciji lista u binarnom stablu, jasna je njegova egzistencija i jedinstvenost).
POSTUPAK
Uklanjanjem lista v iz
S dobija se stablo S' sa n-1
čvorova, za koje se
u O (n 2) koraka može izračunati matrica svih rastojanja (sledi iz induktivne hipoteze).
Vreme izvršavanja opisanog algoritma za problem dimenzije n je T(n), tj.
T(n)=T(n-1) + (2n-1)*c1 + c ,
jer iz matrice stabla sa n-1 čvorom se za dodatnih (2n-1)*c1
koraka dolazi do matrice stabla sa n čvorova,
gde vrednosti matrice za k-tu vrstu i k-tu kolonu se računaju za const*(2n-1) koraka (matrica A je dimenzije n*n)
dok je c-const vreme potrebno da se nađe čvor w za čvor v
Dakle, T(n)=T(n-1) + (2n-1)*c1 + c=...= T(1) + c2*[2n+2(n-1)+ ... +1] - n*(1+c)=n(n+1)*c2 + n*c3=O (n 2)
Hip se može realizovati kao kompletno stablo u kome svaki čvor i njegov naslednik su u relaciji poretka R, gde R može biti relacija <, >,...
Na primer, binarno stablo je kompletno popunjeno ako ima visinu h i 2h+1-1 cvorova.
Binarno stablo visine h je kompletno ako i samo ako je
Kompletno stablo se popunjava sa leve strane:
Primer: Neka R je relacija ‘>’ i drvo ima stepen 2. Dakle, heap nije BSP koje ste izučavali ranije, jer svako dete mora u heap-u biti manje od oca. Ne može kao u BSP, da npr. desno dete bude veće.
Hip | Nije hip |
Lista sa prioritetom:
dinamički skup čiji elementi se uklanjaju po redosledu veličina, počev od
najvećeg. Na primer, objekat sa najvećim
prioritetom se nalazi u korenu heap-a i trivijalno se uzima iz strukture. Ali ako
se ukloni koren, tada ostaju dva podstabla i moraju se efikasno spojiti u
jedno stablo koje će ponovo imati heap svojstvo.
Korist od upotrebe heap strukture zasniva se na svojstvu da se moze
izvaditi objekat
najviseg prioriteta i ubaciti za O(logn) vremena.
Heap Sort: od kolekcije elemenata kreira se heap za (O(n)) vremena i potom se uklanjaju elementi iz heap-a, a svako uklanjanje ima složenost proporcionalnu visini heap-a, tj. (O(log n)), te ukupna složenost je (O(n log n)) (donja granica).
1. eksplicitno zadatim stablom
2. vektor, tj. implicitno zadato stablo sa pozicijama 1..n. Koren je na poziciji 1. Na poziciji i > 1 je dete sa pozicije i/2.Na primer, ako niz A je implicitno zadato stablo, onda element A[16] odgovara čvoru čiji predak je čvor pridružen elementu A[8].
Svojstva kompletnog stabla vode do veoma efikasnog mehanizma za memorijsko predstavljanje koristeci n uzastopnih pozicija u nizu, tj. vektoru..
Ako su čvorovi numerisani počev
od 1 u korenu i ako je:
tada osobina 'popunjenosti s leve strane' kompletnog stabla obezbeđuje da heap može da se smesti u uzastopnim pozicijama u vektoru. |
Posmatran kao niz, vidi se da se n-ti čvor nalazi na n-tom mestu u nizu. |
novi element | 4 | 7 | 9 |
---|---|---|---|
ažurirano stablo |
Ponovo, za ovu proceduru je potrebno O(h), odnosno O(logn) zamena.
pre | posle |
O(0 * (n/2) + 1 * (n/4) + 2 * (n/8) + + (log n) * 1) = O(n(0 2-1 + 1 2-2 + 2 2-3 + + (log n) 2- log n)) = O(n)
znajući da izraz u zagradi u stvari ima vrednost
k = 1(k - 1)2-k =2[ k = 1(k - 1)2-k] - [ k = 1(k - 1)2-k] =[ k = 1k2-k] - [ k = 1(k - 1)2-k] = k = 1[k - (k - 1)]2-k
= k = 12-k =1
Savki čvor binarnog stabla ima ne više od dva sina, te je moguće uvesti preslikavanje skupa njegovih sinova u skup {levi, desni}. U BSP ključ svakog čvora veći je od od ključeva svih čvorova levog podstabla, a manji ili jednak je od ključeva svih čvorova desnog podstabla. BSP omogućava efikasno izvršavanje opracija pretrage, umetanja i uklanjanja elementa.
BSPpretraga ( drvo, ključ ) IF prazno drvo return nije_nadjen IF ključ == ključ korena return nadjen IF ključ > ključ korena BSPpretraga (levo poddrvo, ključ) BSPpretraga (desno poddrvo, ključ)
Vremenska složenost: O(h), h-visina stabla
ubaci 6 | ubaci 10 | |
Zameniti čvor koji sadrži obrisani ključ ili sa čvorom koji poseduje najveći ključ u levom podstablu ili sa čvorom koji ima najmanji ključ u desnom podstablu.
Definicija: AVL stablo je binarno stablo pretrage kod koga je za svaki čvor apsolutna vrednost razlike visina levog i desnog stabla manja ili jednaka od jedan.
Visina stabla je visina njegovog korena, tj. maksimalno rastojanje od korena do nekog čvora..
Visina čvora x je rastojanje od x do najdaljeg potomka.
Operacije pretrage, umetanja, brisanja nekog elementa obavljaju se za O(log n) vremena, kao kontrast sličnim operacijama u nebalansiranim stablima, kada stablo može da se degeneriše i u sortirani niz.
Stav: AVL stabla su balansirana, tj. visina im je O(log n).
Dokaz. Neka Nh označava broj čvorova AVL stabla visine h
Nh | > Nh-1 + Nh-2 + 1 (relacija balansiranog stabla, +1 za koren) |
> 2Nh-2 + 1 (jer Nh su nenegativni) | |
> 1 + 2(1 + 2Nh-4) | |
= 1 + 2 + 22N h-4 | |
> 1 + 2 + 22 + 23N h-6 | |
... | |
> 1 + 2 + 22 + 23 + ... + 2h/2 | |
= 2h/2 - 1 | |
Dakle, ako n je broj čvorova, dobili smo da
2h/2 - 1 | < n Logaritmovanjem dobija se |
h/2 | < log 2(n + 1) |
h | < 2 log 2(n + 1) |
Preciznija analiza, zasnovana na Fibonačijevm brojevima (data u knjizi), ukazuje da gornja granica za h je 1.44 log 2(n + 2), tj. visina AVL stabla je
O(log n).
Pri umetanju čvorova u AVL stablo, najpre se pronalazi mesto čvoru tako da bude očuvano svojstvo stabala binarne pretrage o uređenosti ključeva, a potom se u stablo dodaje novi list sa ključem jednakim ključu novog čvora. Pri tom može da se desi da stablo postane neuravnoteženo, te se primenjuje rotacija.
Razlikuju se
1. 1-struka rotacija (npr. koren levog podstabla podiže se i postaje koren novog stabla, a ostatak stabla se preuređuje tako da stablo ostane BSP stablo, npr. slika LL)
2. 2-struka rotacija i Leva(L) i Desna(R)
LL | ||
RR | ||
LR | ||
RL | ||
LL & LR LL |
Uklanjanje elementa iz AVL stabla je komplikovanije neko kod običnog BSP stabla, jer je potrebno više rotacija. Na primer, da bi se uravnotežilo Fibonačijevo (potpuno) AVL stablo posle uklanjanja "pogodno" izabranog čvora, nužno je izvršiti h-2 rotacije, gde h je visina stabla.
Ukloni 4 | |
debalans sa 3, LL rotacija sa ‘2’ | |
deabalans sa 5, RR rotacija sa ‘8’. |
Ako ne važi ograničenja da svaki čvor stabla može da ima samo jedan ključ, tada se može smanjiti ukupna visina stabla, što je značajno pri pretrazi.
m-arno stablo pretrazivanja
|
Ili jednostavnije ..
|
Visina kompletnog m-arnog stabla sa n cvorova je [logmn].
B-stablo reda m je m-arno stablo u kome su
Varijacija B-stabla, poznata kao B+-stablo posmatra sve ključeve u čvorovima koji nisu listovi kao lažne. Svi ključevi su duplirani u listovima, što ima za prednost da ako se svi listovi povežu sekvencijalno, tada se celo stablo može pročitati bez posećivanja čvorova na višim nivoima.
B-stabla su 1972. predložili Bayer i McCreight. Od tada ova stabla su se razvila u više varijanti (B*, B+) i postala jedna od najpopularnijih tehnika za organizaciju indeksnih struktura u datotekama. B-stablo reda m definiše se kao stablo m-arnog pretraživanja sa sledećim svojstvima:
Drugo svojstvo garantuje da je svaki čvor sem korena barem polupopunjen. Time se poboljšava iskorišćenje prostora kao nedostatak stabla m-arnog pretraživanja. Isto svojstvo forsira i grananje sa ciljem da broj nivoa bude što manji.
Četvrto svojstvo obezbeđuje balansiranost i garantovane performanse pretraživanja u najgorem slučaju.
B-stablo reda 3 | nije B-stablo, jer čvorovi 6, 22 su sa polupounjenosti mogli da imaju popunjenost |
dodati 19: Najpre se pokuša da se novi čvor umetne u list, a najčešće tamo i ostane Konkretno, za 19 se traži list i pozicija u njemu koja mu pripada. Kako u listu sa 20 ima mesta za umetanje, umeće se 19. |
|
dodati 21: Najpre se pokuša da se novi čvor umetne u list, a najčešće tamo i ostane Konkretno, za 21 se traži list i pozicija u njemu koja mu pripada. Kako u listu sa 20 nema mesta za umetanje, jer list u koji treba umetnuti več ima m-1 ključ, onda dolazi do preloma (split) lista..
|
|
Alocira se prostor za novi čvor 19, a potom 21 | |
Pravilo: Formira se rastuće sortiran niz od m=3 ključa,
tako što se ključevi od 1..m/2-1 zadrze u starom listu, kljuc sa
pozicije m/2 ide u roditeljski list, a kljucevi do Km idu u eventualno nov
list ili ako roditeljski cvor nije pun, onda prima srednji kljuc (ovde je to
22) sa donjeg nivoa.
|
|
Dakle, 19, 21 idu u naslednike cvora 20. | |
Cvor 22 se penje navise. |
ukloniti 26 | |
ukloniti 22 | |
ukloniti 18 | |
svaki čvor je crn ili crven
ako čvor je crven, oba njegova sina su crna
svaki prost put od korena do lista sadrži isti broj crnih čvorova
nijedna putanja od korena do lista nije više od dva puta duža od bilo koje druge
Treća osobina obezbeđuje relaksiranu balansiranost stabla i značajna je za logaritamske performanse stabla.
Četvrta osobina daje grantovane performanse stabla O(log n) u n ajgorem slučaju.
Crveno-crno stablo je binarno stablo pretrazivanja sa jos jednim dodatnom informacijom za svaki cvor: bojom, koja je ili crvena ili crna. Ta dodatn ainformacija se može kodirati sa 1 botom. Takodje je neophodno vodti racuna o roditelju svakog cvora, tako da bi struktura cvora crveno-crnog stabla mogla biti:
struct t_red_black_node { enum { red, black } colour; void *item; struct t_red_black_node *left, *right, *parent; }
Tokom ovog razmatranja, NULL cvorove koji zavrsavaju stablo smatracemo listovima i obojene u crno.
Crveno-crno stablo sa n unutrasnjih cvorova ima visinu najvise 2log(n+1).
Sada se vidi zasto je crveno-crno stablo dobro stablo za pretrazivanje: ono se uvek moze pretraziti u O(log n) koraka.
Kao i kod hipa, dodavanja i brisanja iz crveno-crnog stabla remete crveno-crne osobine, tako da ih je potrebno popravljati. Da bismo ovo uradili, neophodno je da pogledamo nekoliko operacija na crveno-crnim stablima.
Rotacija je lokalna operacija u stablu pretrazivanja koja očuvava
in-order poredak ključeva.
Primetimo da u oba stabla, in-order obilazak daje:
A x B y C |
Operacija leve rotacije može da se kodira na sledeći način:
left_rotate( Tree T, node x ) { node y; y = x->right; /* Pretvoriti levo podstablo cvora y u desno podstablo cvora x */ x->right = y->left; if ( y->left != NULL ) y->left->parent = x; /* Novi roditelj cvora y je bivsi roditelj cvora x */ y->parent = x->parent; /* Roditelj mora da pokazuje na cvor y umesto na cvor x */ /* Najpre proverimo da li se nalazimo u korenu - tada nema roditelja! */ if ( x->parent == NULL ) T->root = y; else if ( x == (x->parent)->left ) /* cvor x je bio sa leve strane svog roditelja */ x->parent->left = y; else /* inace je cvor x morao da bude sa desne strane */ x->parent->right = y; /* Konacno, stavimo cvor x sa leve strane cvora y */ y->left = x; x->parent = y; }
Dodavanje je relativno slozeno i ukljucuje veliki broj slucajeva. Primetimo da dodavanje novog cvora x u crveno-crno stablo pocinjemo na isti nacin kao sto bismo to uradili sa bilo kojim binarnim stablom, koristeci funkciju tree_insert. Taj postupak je opisan gore pri dodavanju čvora u binarno stablo pretrage.
Novi čvor se oboji u crvenu boju. Ali, to možda remeti crveno-crne osobine. Da bi se to otklonilo, vrše se izvesne izmene. Izmene se obavljaju u , glavnoj petlji kada se penjemo uz stablo ka korenu, dok ne oporavimo crveno-crne osobine. Pri penjanju se uvek nalazimo u crvenom čvoru, a postupak se prekida onog trenutka kada je roditelj crvenog čvora u kom se nalazimo, zapravo crn.
rb_insert( Tree T, node x ) { /* Dodavanje u stablo na uobicajen nacin */ tree_insert( T, x ); /* Sada oporavi crveno-crne osobine */ x->colour = red; while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* Ako je roditelj x sa leve strane, tada je y desni ujak cvora x */ y = x->parent->parent->right; if ( y->colour == red ) { /* slucaj 1 - promeni boje */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Pomeri x nagore kroz stablo */ x = x->parent->parent; } else { /* y je crni cvor */ if ( x == x->parent->right ) { /* a x je sa desne strane */ /* slucaj 2 - pomeri x nagore i rotiraj */ x = x->parent; left_rotate( T, x ); } /* slucaj 3 */ x->parent->colour = black; x->parent->parent->colour = red; right_rotate( T, x->parent->parent ); } } else { /* ponoviti "if" deo sa izmenjenim "right" i "left" */ } /* Oboji koren u crno */ T->root->colour = black; }
LLr, leva rotacija, jer naslednici levog čvora B nisu
oba crna, tj. nije levi naslednik. Iz B se penjemo ka korenu sve dok smo u crvenom čvoru. Stajemo kod A i on se proglasi za crveni, a njegovi sinovi za crni. |
|
|
LRr,
LLr, levodesna rotacija, jer naslednici levog čvora B nisu oba crna, tj. nije desni naslednik C. Iz B se penjemo ka korenu sve dok smo u crvenom čvoru. Stajemo kod A i on se proglasi za crveni, a njegovi sinovi za crni.
|
Formiranje crveno-crnog stabla
Dodavanje novog čvora x u crveno-crno stablo počinjemo na isti nacin kao sto bismo to uradili sa bilo kojim binarnim stablom, koristeci funkciju tree_insert. Taj postupak je opisan gore pri dodavanju čvora u binarno stablo pretrage.
Novi čvor se oboji u crvenu boju. Ali, to možda remeti crveno-crne osobine. Da bi se to otklonilo, vrše se izvesne izmene. Izmene se obavljaju u , glavnoj petlji kada se penjemo uz stablo ka korenu, dok ne oporavimo crveno-crne osobine. Pri penjanju se uvek nalazimo u crvenom čvoru, a postupak se prekida onog trenutka kada je roditelj crvenog čvora u kom se nalazimo, zapravo crn.
dodati 1 | |||
dodati 2 | |||
dodati 3 |
RR rotacija zbog balansiranosti, oko desnog poddrveta 2-3 |
||
dodati 4 |
kod čvora 3 narušeno boja zbog naslednika |
||
dodati 5 |
RR rotacija zbog balansiranosti oko desnog poddrveta 3-4-5 |
nužno je bojenje desnog poddrveta |
Rešenje:
Graf G=(V,E) sastoji se od skupa čvorova V i skupa grana E, pri čemu grane predstavljaju relacije između čvorova.
Specijalan primer grafa jeste stablo koje predstavlja povezan graf bez ciklusa, tj. svi čvorovi su povezani među sobom i nema cikličnih puteva kroz stablo. Ako je na stablu potrebno definisati hijerarhiju, onda se sve grane mogu usmeriti od "korena". Takva stabla se nazivaju korenska stabla. Koren je poseban izdvojen čvor stabla, a listovi stabla su čvorovi koji nemaju naslednike.
Uobičajena su dva načina predstavljanja stabla:
matricom povezanosti
listom povezanosti.
Matrica povezanosti grafa G je kvadratna matrica A reda n (gde |V|=n), gde A[i,j]=1 ako postoji grana od čvora vi do čvora vj. Ostali elementu su nule. Ako graf G je neusmeren, matrica je simetrična. Ako je broj grana u G mali, onda većina elemenata matrice će biti nula, ali će ona i dalje zauzimati prostor veličine n*n, sto je nedostatak ovog tipa reprezentacije ako se koristi za retke grafove.
Lista povezanosti pak omogućuje da se ne vrši eksplicitno predstavljanje nepostojećih grana. Svakom čvoru pridružuje se povezana lista koja sadrži sve grane ka susednim čvorovima. Svaki element liste (tj. jednodimenzionog niza) sadrži indeks čvora grafa G i pokazivač na njegovu listu čvorova. Ako G je statički graf (tj. ne vrše se umetanja, brisanja), onda se za realizaciju liste povezanosti koristi niz dužine |V|+|E|, gde prvih |V| elemenata su pridruzeni cvorovima grafa, a vrednost na poziciji j pridruzena cvoru vj sadrzi indeks pocetka spiska čvorova susednih čvoru vj.
|
|||||||||||||||||||||||
1. član liste je 7, te na 7. poziciji je početak čvorova koji su vezani sa čvorom 1, tj. korenom. | |||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
2. član liste je 9, te na 9. poziciji je početak čvorova koji su vezani sa čvorom 2. |
Hash tabele
Neka u skupu od n elemenata, ključevi članova skupa jesu jedinstveni celi
brojevi u intervalu (1,m), gde je m >= n. Tada se
elementi mogu smestiti u tabelu sa direktnim adresiranjem T[m],
gde je Ti ili prazno polje ili sadrži jedan element iz
polaznog skupa.
Pretrazivanje tabele sa direktnim adresiranjem je O(1) operacija, jer za ključ k pristupa se polju Tk,
Ovde postoje dva ograničenja:
|
Ukoliko ključevi nisu jedinstveni, tada se može kreirati
skup od m povezanih listi tako da u polja tabele direktnog adresiranja
budu
smeštene adrese glava ovih listi. Vreme za nalaženje elementa koji odgovara
ulaznom kljuću je i dalje O(1) - to je element sadržan u glavi
odgovarajuće liste.
Medjutim, ako elementi skupa imaju još neku osobinu po kojoj se razlikuju (sem ključa), i ako je maksimalan broj duplih ključeva ndupmax, tada traženje određenog elementa traje O(ndupmax) koraka. Ako su duplikati retki, tada je ndupmax mnogo manje od n i tabela sa direktnim adresiranjem će dati dobre performanse. Ali ako je ndupmax istog reda veličine kao i n, tada traženje određenog elementa traje O(n) koraka i korišćenje strukture stabla bi bilo mnogo efikasnije. |
Opseg ključeva određuje veličinu tabele direktnog adresiranja, koja može da bude suviše velika da bi bila praktična. Na primer, malo je verovatno da cete u sledecih par godina moci da koristite tabelu direktnog adresiranja za smestanje elemenata koji kao kljuceve imaju proizvoljne 32-bitne cele brojeve!
Direktno adresiranje se lako uopstava na slucaj kada postoji funkcija
h(k) => (1,m)
koja svaku vrednost kljuca k preslikava u interval (1,m). U ovom slucaju, element sa kljucem k smestamo u T[h(k)] (umesto u T[k]) i jos uvek mozemo da pretrazujemo u O(1) koraka kao i ranije.
Pristup sa direktnim adresiranjem zahteva da je funkcija h(k) 1-1 preslikavanje iz skupa kljuceva u interval (1,m). Takva funkcija se naziva savrsena hash funkcija: ona preslikava svaki kljuc u razlicit ceo broj unutar nekog razumljivog opsega i omogucava nam da trivijalno napravimo tabelu sa O(1) vremenom pretrazivanja.
Na zalost, nalazenje savrsene hash funkcije nije uvek moguce. Recimo da mozemo da nadjemo hash funkciju h(k), koja preslikava vecinu kljuceva u jedinstvene brojeve, ali da manji broj kljuceva preslikava u isti broj. Ako je broj sudara (slucajeva kada se vise kljuceva preslikava u isti broj) dovoljno mali, tada hash tabele rade veoma dobro i daju O(1) vreme pretrazivanja.
U malom broju slucajeva, kada se vise kljuceva preslikava u isti broj, elementi sa razlicitim kljucevima se mogu smestiti u isto polje hash tabele. Jasno je da je, u slucaju kada se hash funkcija koristi za lociranje elementa koji se trazi, neophodno poredjenje kljuca elementa sa datim kljucem. Medjutim, u istom polju tabele se sada moze naci vise od jednog elementa sa razlicitim kljucevima! Za resavanje ovog problema koriste se razlicite tehnike:
Jedan jednostavan princip je da se svi sudari povezu u listu koja se prikaci na odgovarajuce polje. Ovako se moze rukovati neogranicenim brojem sudara i ne zahteva se unapred podatak o tome koliko elemenata se nalazi u skupu. Nedostatak je isti kao i kod implementacije skupa pomocu povezanih listi, umesto pomocu nizova: povezane liste traze vise prostora i, u manjem stepenu, vremena.
Princip re-hashiranja koristi jos jednu hash funkciju kada dodje do
sudara. Ako ponovo nastane sudar adresa, onda re-hashiramo dok se ne
nadje prazno polje u tabeli.
Re-hash funkcija moze da bude ili sasvim nova funkcija ili ponovna primena originalne funkcije. Sve dok se funkcije primenjuju na kljuc u istom poretku, trazeni kljuc ce uvek moci da se nadje. Linearni preskokJedna od najjednostavnijih re-hash funkcija je +1 (ili -1), tj. kad nastane sudar, pogledaj u susedno polje tabele. Nova adresa se racuna ekstremno brzo i moze biti ekstremno efikasna na modernim procesorima zahvaljujuci efikasnoj upotrebi kes memorije ().
|
h(j)=h(k), pa se koristi sledeca hash funkcija h1. Nastaje i drugi sudar, pa se koristi sledeca hash funkcija h2. |
Linearni preskok je sklon fenomenu nagomilavanja. Re-hashirani elementi iz jednog polja zauzimaju blok polja u tabeli koji "raste" prema poljima koja zauzimaju drugi kljucevi. Ovo pogorsava problem sudara i broj re-hashiranih elemenata moze da postane veliki.
Bolje ponasanje se obicno dobija sa kvadratnim preskokom, gde sekundarna hash funkcija zavisi od re-hash indeksa:
adresa = h(key) + c i2
kod i-tog re-hashiranja. (Slozenija funkcija od i se takodje moze koristiti.) Posto kljucevi, koji se preslikavaju u istu vrednost, slede isti niz adresa, kvadratni preskok pokazuje sekundarno nagomilavanje. Medjutim, sekundarno nagomilavanje je mnogo manje ozbiljno od nagomilavanja prouzrokovanog linearnim preskokom.
Re-hashing principi koriste originalno alociran prostor za tabele i stoga izbegavaju nedostatke povezanih listi, ali zahtevaju da se broj elemenata koje treba smestiti zna unapred.
Ipak, sudareni elementi se smestaju u polja u koja se drugi elementi preslikavaju direktno, tako da se potencijal za visestruke sudare povecava kako se tabela popunjava.
Ovaj princip deli pre-alociranu tabelu u dve oblasti: primarnu oblast u koju se preslikavaju kljucevi i oblast za sudare, koja se obicno zove oblast prelivanja.
Kada dodje do sudara, za novi element se koristi polje u oblasti prelivanja, a u primarnom polju se napravi pointer kao u povezanoj listi. Ovo je u sustini isto kao ulancavanje, osim sto je oblast prelivanja pre-alocirana i stoga moguce brza za pristup. Kao i sa re-hashiranjem, maksimalan broj elemenat mora biti poznat unapred, ali u ovom slucaju, moraju se proceniti dva parametra: optimalna velicina primarne oblasti i oblasti prelivanja. |
Naravno, moguce je dizajnirati sisteme sa visestrukim oblastima prelivanja, ili sa mehanizmom za rukovanje sudarima u oblasti prelivanja, koja daju fleksibilnost bez gubitka prednosti oblasti prelivanja.
Organizacija | Prednosti | Nedostaci |
---|---|---|
Ulancavanje |
|
|
Re-hashiranje |
|
|
Oblast prelivanja |
|
|
Hash funkcije |
Izbor dobre hash funkcije h(k) je osnovni problem kod korišćenja hash tabela za pretraživanje. Funkcija h bi trebalo da raspodeli elemente našeg skupa što je moguće ravnomernije u polja hash tabele. Ključni kriterijum je da bi broj sudara trebalo da bude što manji.
Ako je P(k) verovatnoća da se ključ k pojavljuje u nasem skupu, tada bi, ako postoji m polja u nasoj hash tabeli, uniformna hash funkcija h(k) osigurala da:
Ponekad je ovo jednostavno obezbediti. Na primer, ako su kljucevi slucajno rasporedjeni u intervalu (0,r], tada funkcija
h(k) = floor((mk)/r)
obezbedjuje ravnomerno hashiranje.
Vecina hash funkcija ce najpre preslikati kljuceve u neki skup prirodnih brojeva, recimo (0,r]. Postoji mnogo nacina da se ovo uradi, na primer, ako je kljuc niz ASCII znakova, mozemo jednostavno da saberemo ASCII brojeve znakova po modulu 255 da bismo dobili broj u intervalu [0,255) - ili mozemo na njih da primenimo xor, ili ih mozemo sabirati u parovima po modulu 216-1, or ...
Posto smo preslikali kljuceve u skup prirodnih brojeva, imamo puno mogucnosti za hash funkciju.
h(k) = k mod m.
Pri koriscenju ovog metoda, izbegavaju se odredjene vrednosti m. Obicno se izbegavaju stepeni dvojke, jer k mod 2b jednostavno daje b najnizih bitova broja k. Osim u slucaju da znamo da su svih 2b mogucih vrednosti najnizih bitova podjednako verovatne, ovo ne bi bio dobar izbor, jer se neki bitovi kljuca ne koriste u hash funkciji.
U principu, prosti brojevi koji su bliski stepenima dvojke izgledaju kao povoljan izbor za m.
Na primer, ako imamo 4000 elemenata, i izabrali smo organizaciju sa oblascu prelivanja, ali zelimo da sto je vise moguce smanjimo verovatnocu sudara, tada bismo mogli da izaberemo m = 4093. (4093 je najveci ceo broj manji od 4096 = 212.)
Prema tome, hash funkcija je:
h(k) = floor(m * (kA - floor(kA)))
U ovom slucaju, vrednost m nije kriticna i obicno se bira stepen dvojke, tako da mozemo da dobijemo sledecu efikasnu proceduru na vecini racunara:
Stoga
A = (sqrt(5)-1)/2 = 0.6180339887
je veoma dobar izbor (prema Knuth, "Sorting and Searching", 3. tom u seriji "The Art of Computer Programming").
Oni skloni kontraprimerima bi uvek mogli da izabere kljuceve tako da se oni svi preslikavaju u isto polje hash tabele, prouzrokujuci prosecno O(n) vreme za pretrazivanje. Univerzalno hashiranje pokusava da izbegne ovu situaciju birajuci hash funkciju slucajno iz skupa hash funkcija. Ovo smanjuje verovatnocu da ce hash funkcija dati lose ponasanje i u proseku daje dobre performanse.
Ako se posmatra izraz zadat u infiksnoj notaciji, uočava se da se on može prirodno predstaviti binarnim stablom kod koga su čvorovima grananja pridruženi operatori, dok levo i desno podstablo predstavljaju složene operande (podizraze). Listovi stabla predstavljaju elementarn operande - promenljive i konstante. Obilaskom ovakvog stabla preorder/postorder obilasku dobija se prefiksna/postfiksna varijanta aritmetickog izraza.
Preko stabala se moze proveriti i slicnost struktura dva izraza. Proveri se slicnost strukture stabala, s tim sto čvorovi koji predstavljaju komutativne operatore (+,-,...) ne prave razliku između levogi desnog podstabla.
Sa izrazima se mogu vršiti i ostale korisne manipulacije. Diferenciranje izraza se obavlja pomoću obilaska stabla na postorder način. Najpre se difrenciraju prosti operandi, a potom izrazi po pravilima diferenciranja za odgovarajuće operande sve dok se ne obradi čitav izraz.
Pri rešavanju problema često se pojavljuju situacije u kojima treba na osnovu nekog uslova ili stanja doneti odluku u kom pravcu nastaviti rešavanje, čime se sužava broj mogućih ishoda. Ovakav način rešavanja se može pogodno modelirati stablom odlučivanja. Često se koristi kada treba izvesti što manji broj merenja da bi se detektovali defektni objekti u nekoj kolekciji (npr. lažne osobe, lakši novčići, teže kuglice,...). Grane i čvorovi predstavljaju uslove i akcije koje se obavljaju, pri čemu gornji deo stabla predstavljaju pravila koja odgovaraju if naredbama sa složenim uslovima, a listovi stabla sadrže rezultat radsa prostog pravila, tj. rezultat proste if naredbe.
Stabla se često koriste u realizaciji raznih igara koje se igraju na računaru kao što su šah, iks-oks,... U takvim igrama za tablom postoje dva igrača koji naizmenično povlače poteze, a stanje igre se predstavlja pozicijom na tabli. Neka postoji konačan broj ovakvih poteza. Za takvu igru se može konstruisati stablo igre gde svaki čvor predstavlja jednu poziciju na tabli. Koren predstavlja početnu poziciju, a listovi stabla predstavljaju završne pozicije: pobede, poraza, nerešenog ishoda. Parni nivoi stabla predstavljaju pozicije u kojima potez vuče prvi igrač, a neparni pozicije u kojima vuče drugi igrač. Izbor poteza u nekoj pozicviji zasniva se od pricene vrednosti pozicije. Pridruživanje vrednosti počinje od listova koje dobijaju vrednosti 1, 0, -1 ako završna pozicija završava, pobedom, nerešeno, porazom. Zatim se vrednosti propagiraju od listova ka korenu. Postoje i tehnike odsecanja koje omogućavaju da se veliki delovi stabla izbace iz razmatranja, jer ne mogu dati minimum ili maksimum na izvesnom nivou.
Jelena Grmuša | Primene računara |