Operacije sa stablima binarnog pretraživanja

UVOD

Danas se računari koriste za apsolutno sve: pocevši od vojnih simulacija, preko fizikalnih i astronomskih simulacija pa sve do komunikacije, medija i astrologije. Pre svega nekoliko desetaka godina, takva široka upotreba računara bila je nezamisliva. Osim što danas svi imamo računare, bilo desktop bilo prenosive, oni su nam počeli preuzimati i džepove – moderni mobilni telefoni u biti su umanjeni računari koji se svojom snagom mogu meriti sa računarima iz prošlih decenija.
Prema Mooreovom se zakonu svake dve godine broj operacija koje računar može izvršiti u sekundi udvostruči. Zbog toga se programi koji već postoje izvršavaju sve brže i brže bez ikakve izmene njihovog koda. Ipak, ta ubrzanja su samo konstantna i odnose se na sve programe. Pretpostavimo da se bavimo programiranjem. Ako želimo da upravo naš program bude najbrži, nećemo se oslanjati na sirovu računarsku snagu nego ćemo koristiti brže algoritme i strukture podataka.
Važnost dobrog odabira algoritma opisaćemo na primeru sortiranja. Ako nekim jednostavnim algoritmom (recimo bubble sortom ili selection sortom) pokušamo sortirati veliku količinu podataka, recimo njih 10,000,000, program će se izvršavati otprilike 4.5 sata. Nasuprot tome, koristimo li nešto složeniji, ali brži algoritam (kao, na primer, quick sort ili merge sort), isti ulazni podaci biće sortirani za svega nekoliko sekundi!
Odabir odgovarajuće strukture podataka takođe je važan. Ako je bitno da možemo pristupiti bilo kom elementu polja, nećemo koristiti listu, nego obično polje, jer ćemo, u suprotnom, pristup elementima na kraju liste jako skupo plaćati. U bazama podataka strukture su takođe bitne. U manjim bazama podataka, za to se koriste binarna stabla. No, u najvećim bazama podataka, ne možemo učitati sve podatke, pa onda koristimo posebno dizajnirane strukture, takozvana B stabla.
Ipak, ponekad zaista nije potrebno mučiti se i kodirati najbolji mogući algoritam i najbolju strukturu podataka. Ono što je najbitnije u programiranju jeste sposobnost ocenjivanja potrebne efikasnosti. Ukoliko shvatimo da je dovoljna i jednostavna alternativa, čemu se mučiti i pisati nešto što jeste možda brže, ali i traži puno više vremena za samo pisanje i dizajniranje te je još podložnije greškama?
U ovom seminarskom radu govorićemo o strukturama podataka koje zovemo binarna stabla.