Još jedna razlika između B-stabla i binarnog stabla je da B-stablo mora imati sve svoje dječje čvorove na istoj razini, dok binarno stablo nema takvo ograničenje. Binarno stablo može imati najviše 2 podstabla ili čvora, dok u B-stablu može imati M bez podstabala ili čvorova gdje je M red B-stabla.
Tablica usporedbe
| Osnova za usporedbu | B-stablo | Binarno stablo |
|---|---|---|
| Bitno ograničenje | Čvor može imati maksimalan M broj dječjih čvorova (gdje je M redoslijed stabla). | Čvor može imati najviše 2 podstabla. |
| koristi | Koristi se kada se podaci spremaju na disk. | Koristi se kada se zapisi i podaci pohranjuju u RAM. |
| Visina stabla | log M N (gdje je m redoslijed stabla M-puta) | log 2 N |
| primjena | Struktura podataka indeksiranja kodova u mnogim DBMS-ima. | Optimizacija koda, Huffmanovo kodiranje, itd. |
Definicija B-stabla
B-stablo je ujednačeno stablo M-puta i također je poznato kao balansirano stablo sortiranja. To je slično binarnom stablu pretraživanja u kojem su čvorovi organizirani na temelju obilaznice. Prostorna složenost B-stabla je O (n). Vrijeme složenosti umetanja i brisanja je O (log n).
Postoje određeni uvjeti koji moraju biti istiniti za B-stablo:
- Visina stabla mora biti što je moguće manja.
- Iznad lišća stabla ne smije biti nikakvih praznih podređa.
- Lišće stabla mora doći na istoj razini.
- Svi čvorovi trebaju imati najmanje djece, osim napustiti čvorove.
Svojstva B-stabla reda M
- Svaki čvor može imati maksimalan M broj djece i minimalni broj djece M / 2 ili bilo koji broj od 2 do maksimuma.
- Svaki čvor ima jedan ključ manje od djece s maksimalnim M-1 ključevima.
- Raspored ključeva je u određenom redoslijedu unutar čvorova. Svi ključevi u podstablu prisutnom na lijevoj strani ključa su prethodnici ključa, a oni koji se nalaze na desnoj strani ključa nazivaju se nasljednicima.
- U trenutku umetanja cijelog čvora, stablo se dijeli na dva dijela, a ključ s medijanskom vrijednošću se umeće u roditeljski čvor.
- Postupak spajanja odvija se kada su čvorovi izbrisani.
Definicija binarnog stabla
Binarno stablo je struktura stabla koja može imati najviše dva pokazivača za svoje dječje čvorove. To znači da najviši stupanj koji čvor može imati je 2, a može biti nula ili jedan stupanj.
Postoje određene varijante binarnog stabla poput strogo binarnog stabla, potpunog binarnog stabla, proširenog binarnog stabla itd.
- Strogo binarno stablo je stablo u kojemu svaki ne-terminalni čvor mora imati lijevo podstablo i desno podstablo.
- Stablo se naziva potpunim binarnim stablom kada zadovoljava uvjet da ima 2 i čvora na svakoj razini gdje je i razina.
- Navojni binarni je binarno stablo koje se sastoji od 0 nodova ili 2 broja čvorova.
Tehnike ukrštanja
Prelazak stabala je jedna od najčešćih operacija izvedenih na strukturi podataka o stablu u kojoj je svaki čvor posjetio točno jednom na sustavan način.
- Inorder- U ovom obilasku stabla lijevo podstablo se rekurzivno posjećuje, a korijenski čvor se posjećuje i u posljednjem desnom podstablo se posjećuje.
- Preorer- U ovom prelazu stabla korijenski čvor se prvo posjećuje, zatim lijevo podstablo i naposljetku desno podstablo.
- Postorder- Ova tehnika posjećuje lijevo podstablo, zatim desno podstablo i na kraju korijenski čvor.
Ključne razlike između B-stabla i binarnog stabla
- U stablu B, maksimalni broj dječjih čvorova koji može imati ne-terminalni čvor je M gdje je M red B-stabla. S druge strane, binarno stablo može imati najviše dva podstabla ili dječja čvora.
- B-stablo se koristi kada se podaci pohranjuju u disk, dok se binarno stablo koristi kada se podaci pohranjuju u brzu memoriju kao što je RAM.
- Drugo područje primjene za B-tree je struktura indeksiranja podataka kod DBMS-a, za razliku od toga, binarno stablo se koristi u optimizaciji koda, kodiranju huffman-a itd.
- Maksimalna visina B-stabla je log M N (M je redoslijed stabla). U suprotnosti, maksimalna visina binarnog stabla je log 2 N (N je broj čvorova, a baza je 2 jer je za binarno).
Zaključak
B-stablo se koristi preko binarnog i binarnog stabla pretraživanja, a glavni razlog za to je hijerarhija memorije u kojoj je CPU spojen na predmemoriju s kanalima visoke propusnosti, dok je CPU povezan s diskom putem kanala niske propusnosti. Binarno stablo se koristi kada su zapisi pohranjeni u RAM-u (mala i brza), a B-stablo se koristi kada se zapisi pohranjuju u disk (veliki i spori). Dakle, korištenje B-stabla umjesto binarnog stabla značajno smanjuje vrijeme pristupa zbog visokog faktora grananja i smanjene visine stabla.
