Binarno stablo pretrage

Koliko brzo možemo pronaći ono što tražimo?

Računari, pod uslovom da za to imaju odgovarajući kapacitet, dozvoljavaju smeštaj i obradu velike količine podataka. Svrha računara je da naš život učine lepšim, boljim i lakšim, ali, u svemu tome, obaveza nas kao programera je da računarima omogućimo da svoj posao obavljaju na što jednostavniji način i što efikasnije.

Jasno je da je nekada moralo biti tako, jer su nekadašnji računari bili skromni po svojim mogućnostima, ali, zašto moramo toliko da se trudimo i dan danas? Zar nisu današnji računari "svemoćni" (zar im ne možeo dati bilo kakav program, koji će oni očas posla izvršiti)?! Odgovorićemo na to pitanje i ilustrovati sve navedeno na primeru pretrage nizova.

U računarskoj tehnici, niz možemo posmatrati kao skup elemenata u kome je svaki element povezan sa tačno dva susedna elementa: sa elementom koji mu prethodi i sa elementom koji dolazi posle njega (izuzetak su prvi i poslednji element, koji su povezani sa samo jednim susednim elementom).

Ukoliko je niz elemenata neuređen, na primer: 51, 9, 1, 12, 20, 31, 43, 98, 59, 63, 99, 84, 91, 71, 11, a naša je namera da ustanivimo da li se u datom nizu nalazi broj 71, moraćemo, krenuvši od početka, da ispitamo svaki element niza, dok ne pronađemo vrednost koju tražimo, ili dok ne ustanovimo da traženi broj ne postoji u datom nizu. U našem slučaju, broj 71 smo pronašli na pretposlednjem mestu, posle 14 pokušaja.

Vi ćete možda i dalje tvrditi da su današnji računari jako brzi i da će traženi broj biti pronađen u "deliću sekunde" (tako da nećemo ni primetiti da je ikakvo vreme utrošeno na tu radnju) .... što je tačno .... u ovom slučaju. Ukoliko uzmemo da je vreme potrebno za obradu jednog elementa niza jedan milioniti deo sekunde (1 mikrosekunda), vrednost 71 ćemo u takvim okolnostima pronaći za 14 mikrosekundi (za sada, sve i dalje deluje krajnje nezabrinjavajuće). Međutim, šta ako pretražujemo bazu podataka neke velike društvene mreže gde brojevi koje tražimo predstavljaju identifikacioni broj određene osobe (zapravo, čak i onda kada mi znamo da u bazi postoji osoba sa određenim identifikacionim brojem, računar mora utrošiti određeno vreme za pronalaženje podataka)?

Ako računamo da baza podataka ima podatke za 250 miliona osoba (velik, ali krajnje realističan broj u slučaju velikih, popularnih društvenih mreža) i da je za ispitivanje jednog sloga (ponovo) potreban jedan milioniti deo sekunde, neće nam biti teško da dođemo do zaključka da će računar (potencijalno, u najgorem slučaju) pretraživati ovakvu bazu 250 sekundi, odnosno preko četiri minuta, što nikako nije prihvatljivo!

U sledećem odeljku, pristupićemo pripremi strukture koja će nam omogućiti da pretražujemo početni skup podataka na efikasniji način, uz napomenu da je pravi postupak kreiranja tzv. Samobalansirajućeg (AVL) stabla znatno složeniji (Visinski balansirana (AVL) stabla - članak), pa ćemo stoga ovde primeniti jednostavniji postupak koji, je primeren našem slučaju i dovoljno dobro ilustruje strukturu stabla za potrebe ovog članka.

Ubrzanje (priprema strukture)

Pogledajmo jedno od mogućih rešenja u slučaju niza čiji je broj elemenata 2n-1. Ovakav niz lako se može pretvoriti u kompletno, balansirano binarno stablo pretrage, strukturu u kojoj je svaki čvor (podatak) povezan je sa 0 ili 2 susedna podatka (regularno binarno stablo (binarno stablo koje nije kompletno i balansirano) može imati i čvorove sa jedim potomkom).

Za početak, niz moramo urediti u rastući poredak, a potom ćemo za koren našeg stabla izabrati središnji element niza (što je, u našem slučaju, broj 51).

Priprema stabla - Korak 1
Slika 1. - Binarno satblo pretrage - priprema - korak 1.

Za svaki čvor važi pravilo da sve vrednosti koje se nalaze na podstablu sa leve strane datog čvora moraju biti manje od vrednosti koja je datom čvoru pripisana, dok se u desnom stablu mogu naći samo vrednosti koje su veće. Najlakši način da postignemo da taj uslov uvek bude zadovoljen u slučaju našeg niza elemenata, je da pronađemo vrednosti na sredini levog (12) i desnog odeljka (84) prvobitnog niza i da ih povežemo sa korenom stabla.

Priprema stabla - Korak 2
Slika 2. - Binarno satblo pretrage - priprema - korak 2.

Potom ćemo te dve vrednosti povezati sa četiri čvora koji predstavljaju sredine preostala četiri odeljka (9, 31, 63, 98).

Priprema stabla - Korak 3
Slika 3. - Binarno satblo pretrage - priprema - korak 3.

I na kraju ćemo preostale elemente (koji su, tehnički, takođe sredine preostalih "osmina" niza) povezati po navedenim pravilima.

Priprema stabla - Korak 4
Slika 4. - Binarno satblo pretrage - priprema - korak 4.

Pretraga binarnog stabla

Vratimo se na naš pređašnji primer (tražimo broj 71).

Pretraga stabla - Početak
Slika 5. - Pretraga binarnog stabla - Početna situacija.

Pristupićemo prvom elementu i proveriti da li se na datom mestu nalazi traženi broj.

Pretraga stabla - Korak 1
Slika 6. - Pretraga binarnog stabla - korak 1(a) - poređenje.

Budući da na datom mestu nismo pronašli traženu vrednost i da nismo došli do "listova" ovog stabla (elemenata koji nemaju svoje podstablo), pretraga se nastavlja. S obzirom na to da smo ustanovili da je broj koji je pripisan ispitivanom čvoru (51) manji od traženog broja (71) i da takođe znamo da su sve vrednosti na levom podstablu ispitivanog čvora manje, preći ćemo na prvi susedni desni čvor (ovim postupkom smo efektivno, u jednom koraku, isključili polovinu niza iz dalje pretrage).

Pretraga stabla - Korak 2
Slika 7. - Pretraga binarnog stabla - korak 1(b) - traženi element je veći - prelazimo desno.

Ponovo ispitujemo čvor ....

Pretraga stabla - Korak 3
Slika 8. - Pretraga binarnog stabla - korak 2(a) - poređenje.

.... i, budući da nismo pronašli traženi broj, prelazimo na levo podstablo, s obzirom na to da je tražena vrednost (71) manja od ispitivane vrednosti (84). I ovde smo takođe, efikasno, u jednom koraku, isključili iz dalje pretrage celo jedno podstablo ispitivanog čvora.

Pretraga stabla - Korak 4
Slika 9. - Pretraga binarnog stabla - korak 2(b) - traženi element je manji - prelazimo levo.

Poredimo brojeve ....

Pretraga stabla - Korak 5
Slika 10. - Pretraga binarnog stabla - korak 3(a) - poređenje.

.... i budući da je tražena vrednost (71) veća od ispitivane (63), prelazimo na desno podstablo i isključujemo levo iz dalje pretrage.

Pretraga stabla - Korak 6
Slika 11. - Pretraga binarnog stabla - korak 3(b) - traženi element je veći - prelazimo desno.

Još jedno poređenje (mi znamo da je poslednje, za računar je to samo jedno od poređenja).

Pretraga stabla - Korak 7
Slika 12. - Pretraga binarnog stabla - korak 4(a) - poređenje.

Pogodak! Traženi broj je pronađen.

Pretraga stabla - Korak 8
Slika 13. - Pretraga binarnog stabla - korak 4(b) - pogodak!

Traženu vrednost smo pronašli iz svega četiri pokušaja! Možemo reći da je broj četiri visina našeg stabla. Kada bi naši "listovi" (11, 11, 20, 43, 59, 71, 91, 99), postali čvorovi i povezali se sa po dva elementa, nastalo bi stablo visine pet koje bi se sastojalo iz 31 elementa. Kada bismo ovaj postupak nastavili, dobijali bismo redom stabla sledećih struktura: n = 63, h = 6; n = 127, h = 7; n = 255, h = 8 .... n = 67108863, h = 27; n = 134217727, h = 28; 268435455, h = 29.

Iako se broj elemenata (približno duplira) sa svakim novim nivoom, visina raste samo za jedan. Budući da broj koraka u pronalaženju nekog elementa zavisi isključivo od visine stabla, zaključujemo da je za pronalaženje elementa u stablu pretrage koje povezuje 250 miliona elemenata, potrebno svega 29 koraka. Ako se setimo našeg primera sa početka i ponovo uzmemo 1 mikrosekundu kao vreme potrebno da se pregleda jedan element stabla, zaključujemo da je za pronalaženje elemenata potrebno, u najgorem slučaju 29 mikroseknudi, što je ogromna razlika (i ušteda), u odnosu na > 4min (što je bio rezultat u slučaju linearne pretrage).

Pretraga stabla - Animacija
Slika 14. - Pretraga binarnog stabla - animacija.

Na kraju, ukoliko želite da se detaljnije upoznate sa visinski balansiranim (AVL) stablima, možete posetiti sledeći link (Visinski balansirana (AVL) stabla - članak).

Napomena: Tekstovi i slike na sajtu www.skola-programiranja.rs (osim u slučajevima pojedinih fotografija, gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.skola-programiranja.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo korišćenje u komercijalne svrhe, bez eksplicitnog odobrenja autora i Računarskog centra SystemPro. ©SystemPro d.o.o. novembar 2019.
Autor članka Nikola Vukićević Za web portal www.skola-programiranja.rs Preuzeto sa sajta www.codeblog.rs uz odobrenje autora
Podelite sa prijateljima: