UVOD
U informatici, stablo binarnog istraživanja (SBI) je stablo binarne strukture podataka
koje ima sledeće osobine:
svaki čvor (deo stabla) ima jasnu vrednost;
i levo i desno podstablo moraju takođe biti stabla binarnog istraživanja;
levo podstablo čvora sadrži samo vrednosti manje od vrednosti čvora;
desno podstablo čvora sadrži samo vrednosti veće ili jednake vrednostima
čvora.
Najveća prednost stabla binarnog istraživanja nad drugim strukturama podataka je da
srodni uređeni algoritmi i algoritni istraživanja kao što je in-order traverzala mogu
biti veoma efikasni.
Stabla binarnog istraživanja mogu birati da dozvole ili ne dozvole dupliciranje
vrednosti, zavisno od implementacije.
Stabla binarnog istraživanja su osnova korišćena za konstrukciju više abstraktnih
struktura podataka kao što su setovi, multisetovi i asocijativni redovi.
Slika1- stabla po nivoima, gde nivo 0 predstavlja koren stabla
2
MINIMIZACIJA DUŽINE PUTA U BINARNOM STABLU
Za mnoge algoritme je veoma važno da stablo poseduje topologiju koja
omogućava smanjenje vremena njegovog izvršavanja.
Minimizacija interne dužine puta je važno za algoritam obilaska svih čvorova
ili za algoritam pretraživanja, na primer:
Najnepovoljniji slučaj je degenerisano maksimalne visine, kod ovakvog stabla
sa n čvorova interna dužina puta je:
Minimalna dužina puta za stablo sa n čvorova može da se predstavi kao suma
niza, kao što je: 0,1,1,2,2,2,3,3,3,3,3,4,4,4,4,4,4,4,..... što analitički izgleda
Binarno stablo
(engleski
binary tree
) je u informatici struktura namenjena
čuvanju podataka. Njene memorijske jedinice su organizovane po principu piramide.
Tačnije, svaka memorijska jedinica (
čvor
) binarnog stabla može da pokazuje na još
najviše dva elementa (njegova
deca
), dok stablo ima samo jedan elemenat na koga ne
pokazuje ni jedan drugi (
koren
). Od ovog elementa se može doći u bilo koji drugi
elemenat stabla. Svaki elemenat stabla može biti i svestan koji elemenat pokazuje na
njega (tj. ko mu je
roditelj
).
Slika 3
Elementi jednog stabla su:
Čvor stabla
je jedna memorijska ćelija stabla. Ona može imati nula, jedan ili
dva podčvora. Ista može da nosi dve različite vrednosti:
o
Ključ. Najčešće numerička vrednost, po kojoj se neki element
raspoređuje u binarnom stablu
4
o
Vrednost. podatak koji treba zapamtiti. Može se desiti da su vrednost i
ključ jedno te isto, tj. da se sortiranje binarnog stabla vrši po samoj
vrednosti.
Koren stabla
je čvor stabla koji nije podčvor nijednog drugog čvora u stablu.
List
je čvor stabla koji nema ni jedan podčvor
Roditelj
nekog čvora je čvor koji pokazuje na njega
Dete
nekog čvora je čvor na koji neki drugi čvor pokazuje
U vezi sa slikom gore: čvorovi stabla su elementi prikazani krugovima.
upisani brojevi su vrednosti ključeva po kojima se elementi sortiraju. Čvor sa ključem
8 je koren stabla. njegova deca su čvorovi sa ključevima 3 i 10. Roditelj čvorova sa
vrednošću ključeva 3 i 10 je čvor sa ključem 8. Listovi stabla su čvorovi sa
ključevima 1, 4, 7 i 13.
Podstablo ili podgrana
je skup svih čvorova stabla koji se nalaze levo ili
desno od nekog od čvorova stabla.
AVL-STABLA
AVL-stablo je struktura podataka koja se koristi u računarstvu. Radi se o
balansiranom binarnom stablu pretrage, koje garantuje da operacije umetanja traženja
i brisanja elemenata iz stabla i u najgorem slučaju mogu da se sprovedu u broju
koraka koji odgovara logaritmu broja elemenata u stablu, O(log n). Motiv za
korišćenje binarnih stabala upravo jeste brza pretraga stabla, ali kod uobičajenog,
nebalansiranog binarnog stabla može da dođe do debalansa (neka grana stabla se
značajnije izduži), i onda pretraga koja ide kroz tu granu nema logaritamsku, već
linearnu složenost.
AVL-stablo je binarno stablo pretrage kod koga apsolutna razlika
visina levog i desnog podstabla svakog elementa nije veća od jedan.
AVL-stablo je dobilo ime po izumiteljimа, Adelson-Velskom i Lendisu, koji
su opisali ovu strukturu 1962. u radu Algoritam za organizovanje podataka.
Balansiranost AVL-stabla se održava tako što se nakon svakog umetanja ili
brisanja proverava da li je došlo do gubitka balansiranosti na nekom delu stabla.
Ukoliko je došlo do debalansa, identifikuje se kritični čvor, to jest koren najmanjeg
podstabla koje ne zadovoljava definiciju AVL-stabla. Ovo podstablo se zatim
balansira vršenjem odgovarajućih rotacija elemenata, tako da se povrati balansiranost
podstabla.
B-STABLO
B-stablo
je struktura podataka u informatici. Karakteristike su mu potpuna
balansiranost, sortiranje podataka po vrednosti ključa i čuvanje određenog broja
elemenata u jednom čvoru stabla. Operacije nad podacima stabla se obavljaju u
amortizovano logaritamskom vremenu. B-stablo nalazi primenu u bazama podataka i
sistemima fajlova i direktorijuma na tvrdim (hard) diskovima.
5
