Strukture podataka i algoritmi
8.4 Opsta m-arna stabla

Ako odustanemo od ogranicenja da svaki cvor moze da ima samo jedan kljuc, tada mozemo da smanjimo visinu stabla.
m-arno stablo pretrazivanja
  1. je prazno ili
  2. se sastoji od korena koji sadrzi j (1<=j<m) kljuceva kj i od skupa podstabala Ti, (i = 0..j), takvih da
    1. ako je k kljuc u T0, tada je k <= k1
    2. ako je k kljuc u Ti (0<i<j), tada je ki <= k <= ki+1
    3. ako je k kljuc u Tj, tada je k > kj i
    4. sva stabla Ti su neprazna m-arna stabla pretrazivanja ili su sva stabla Ti prazna.
Ili prosto ..
  1. Cvor u opstem slucaju ima m-1 kljuceva i m potomaka. Svaki cvor ima naizmenicno podstabla i kljuceve:
    podstablo | kljuc | podstablo | kljuc | ... | kljuc | podstablo

    1. Svi kljucevi u podstablu levo od datog kljuca su manji od njega.
    2. Svi kljucevi u cvoru izmedju dva kljuca su izmedju tih kljuceva.
    3. Svi kljucevi u podstablu desno od datog kljuca su veci od njega.
    4. Ovo je "standardni" deo rekurzivne definicije.

Visina kompletnog m-arnog stabla sa n cvorova je ceiling(logmn).

B-stablo reda m je m-arno stablo u kome su

  1. svi cvorovi na istom nivou i
  2. svi cvorovi, osim korena i listova, imaju bar m/2, a najvise m potomaka. Koren ima bar 2, a najvise m potomaka.
Varijacija B-stabla, poznata kao B+-stablo posmatra sve kljuceve u cvorovima koji nisu listovi kao lazne. Svi kljucevi su duplirani u listovima. Ovo ima tu prednost da ako se svi listovi povezu sekvencijalno, tada se celo stablo moze procitati bez posecivanja cvorova na visim nivoima.

Kljucni pojmovi

m-arna stabla
Stabla u kojima svaki cvor ima najvise m potomaka.
B-stablo
Balansirana varijanta m-arnog stabla.
B+-stablo
B-stablo u kome su svi listovi povezani kako bi se ubrzao obilazak stabla.

Dalje na Hash tabele
Nazad na Sadrzaj
© John Morris, 1998. Prevod sa engleskog, Dragan Stevanovic, 2002.