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 diskovima.
Definicija uredi
Svako b-stablo je određeno jednim parametrom k, koji može uzimati vrednosti prirodnih brojeva. Uslovi koje svako b-stablo treba da ispunjava su sledeći:
- Svi listovi drveta se nalaze na istoj visini u odnosu na koren stabla.
- Koren stabla može sadržati 1 do 2k elemenata. Svaki drugi čvor stabla sadrži od k do 2k elemenata.
- Svi elementi u jednom čvoru su sortirani po vrednosti ključa
- Čvor koji nije list i sadrži k' elemenata pokazuje na k'+1 dece. Pokazivači ka deci su tako raspoređeni da pokazuju na čvorove sa vrednostima ključeva između vrednosti ključeva svaka dva susedna elementa čvora, kao i na čvorove sa vrednostima ključevima manjim i većim od vrednosti svakog njegovog ključa.
Osobine uredi
Za b-stablo visine h, sa konstantom k i brojem čvorova n važe sledeći iskazi:
| Visina stabla | |
| Minimalan broj čvorova (h > 0) | |
| Minimalan broj elemenata (h > 0) | |
| Maksimalan broj čvorova | |
| Maksimalan broj elemenata |
Operacije uredi
Struktura b-stabla za isti skup podataka u principu nije jednoznačna. Na primer za k=1 i vrednosti ključeva 21,22,23,24 je za koren stabla moguće uzeti ključ 22 odnosno 23, pri čemu bi u prvom slučaju levi čvor preuzeo ključ 21 a desni 23 i 24. U drugom slučaju bi levi čvor preuzeo ključeve 21 i 22, a desni 24. Sa porastom konstante k i broja elemenata raste i broj mogućnosti njihovog raspoređivanja.
Pretraživanje stabla uredi
Pretraživanje, kao i kod drugih vrsta stabala, počinje od korena stabla i nastavlja se tako što se pri svakom koraku pretrage ustanovljava da li tražena vrednost ključa postoji u trenutno pretraživanom čvoru, u nekom od njegove dece ili ne postoji u stablu.
Dodavanje novog elementa uredi
Novi element se uvek dodaje na dno stabla, kao novi elemenat u nekom od listova. Ukoliko u nekom trenutku broj elemenata u nekom od čvorova pređe dozvoljenu vrednost od 2k, elemenat najbliži sredini niza elemenata biva izdvojen iz niza i dodat u roditelja čvora kome je pripadao, istovremeno postajući roditelj svih elemenata sa njegove leve odnosno desne strane.
Na datom primeru (slika desno) je broj k=1. Pri drugom koraku u postojeće stablo je dodat element sa ključem 80. Kako je time prekoračen broj (2k=2) dozvoljenih elemenata po čvoru, izabran je središlji elemenat problematičnog čvora sa ključem 50 i dodat u svoj roditeljski čvor koji u tom trenutku sadrži samo vrednost 42. Svi elementi sa njegove leve odnosno desne strane se dele u dva nova čvora čiji će roditelj on postati.
Da je prethodno opisanim operacijama dozvoljeni broj elemenata u roditeljskom čvoru bio narušen, proces bi bio ponovljen i za njega. Ukoliko do ovakve situacije dođe u korenu stabla, neminovno je povećanje visine stabla za jedan.
Brisanje elementa iz stabla uredi
Operacija Brisanja elementa može rezultovati gubljenjem osobina b-stabla. Pritom se isključivo radi o povredi pravila o minimalnom broju elemenata po čvoru. Pristup problemu se sastoji u tome da se u čvor koji nakon brisanja poseduje k-1 elemenata ubaci element iz roditeljskog čvora. Ovaj proces se može ponavljati rekurzivno, od dna stabla prema vrhu.
Pritom se izdvaja slučaj kada stablo iz koga se briše jedan element ima minimalan broj elemenata u svakom čvoru. Ovo znači da će na kraju procesa koren stabla koga čini samo jedan element biti utopljen u jedno od svoje dece a pritom će svako od njih imati tačno po k elemenata. U ovom slučaju završni korak je stapanje to dvoje dece u novi čvor koji će postati koren stabla. Jedna od posledica brisanja u ovom slučaju je smanjenje visine stabla h za jedan.
Izvori uredi
- Skripta za predmet „Informatika 2“ sa Univerziteta Karlsrue, Nemačka.
