Razlika između B-stabla i Binarnog stabla
Sadržaj
- Usporedni grafikon
- Definicija B-stabla
- Svojstva B-stabla reda M
- Definicija binarnog stabla
- Tehnike prelaska
- Zaključak
B-stablo i Binarno stablo su vrste nelinearne strukture podataka. Iako su pojmovi slični, ali su različiti u svim aspektima. Binarno stablo koristi se kada su zapisi ili podaci pohranjeni u RAM-u umjesto na disku jer je brzina pristupa RAM-u mnogo veća od diska. S druge strane, B-stablo se koristi kada se podaci pohranjuju na disk, smanjuje vrijeme pristupa smanjujući visinu stabla i povećavajući grane u čvoru.
Još jedna razlika između B-stabla i binarnog stabla je ta što B-stablo mora imati sve svoje podređene čvorove na istoj razini dok binarno stablo nema takvo ograničenje. Binarno stablo može imati najviše 2 podreza ili čvorova dok u B-stablu može biti M nema potkoljenica ili čvorova gdje je M redoslijed B stabla.
- Usporedni grafikon
- definicija
- Ključne razlike
- Zaključak
Usporedni grafikon
| Osnove za usporedbu | B-stablo | Binarno stablo |
|---|---|---|
| Bitno ograničenje | Čvor može imati najviše M broja dječjih čvorova (gdje je M redoslijed stabla). | Čvor može imati najviše 2 broja podvrsta. |
| koristi | Koristi se kada se podaci pohranjuju na disk. | Koristi se kada se zapisi i podaci pohranjuju u RAM-u. |
| Visina stabla | dnevnikM N (gdje je m redoslijed stabla M-puta) | dnevnik2 N |
| primjena | Struktura podataka indeksiranja koda u mnogim DBMS-ima. | Optimizacija koda, Huffmanovo kodiranje itd. |
Definicija B-stabla
Stablo B je izbalansirano M stablo, a poznato je i kao stablo uravnotežene sorte. Slično je s binarnim stablom pretraživanja gdje su čvorovi organizirani na osnovi interverznog presjeka. Složenost prostora B-stabla je O (n). Vremenska složenost umetanja i brisanja je O (log n).
Postoje određeni uvjeti koji moraju biti istiniti za stablo B:
- Visina stabla mora biti što je moguće manja.
- Iznad lišća stabla ne bi trebalo biti praznih potkoljenica.
- Listovi stabla moraju doći na istoj razini.
- Svi čvorovi trebaju imati najmanje djece, osim čvorova na odlasku.
Svojstva B-stabla reda M
- Svaki čvor može imati maksimalni M broj djece i minimalni M / 2 broj djece ili bilo koji broj od 2 do maksimuma.
- Svaki čvor ima jednu tipku manje od djece s maksimalnim M-1 tipkama.
- Raspored tipki je prema određenom redoslijedu unutar čvorova. Svi ključevi u poddrvi na lijevoj strani tipke su prethodnici, a oni koji se nalaze u desnoj tipki nazivaju se nasljednici.
- U vrijeme umetanja punog čvora, stablo se dijeli na dva dijela, a ključ s srednjom vrijednošću ubacuje se u nadređeni čvor.
- Operacija spajanja se događa kada su čvorovi izbrisani.
Definicija binarnog stabla
Binarno stablo struktura je stabala koja za svoje podređene čvorove može imati najviše dva pokazivača. To znači da najviši stupanj čvora može imati 2, a može postojati i nul ili jedan stupanj.
Postoje određene varijante binarnog stabla poput strogo binarnog stabla, kompletnog binarnog stabla, proširenog binarnog stabla itd.
- Strogo binarno stablo je stablo u kojem svaki ne-terminalni čvor mora imati lijevo podređenje i desno poddrevo.
- Drvo se naziva Kompletno binarno stablo kad zadovoljava uvjet da ima 2 ja čvorovi na svakoj razini gdje je i razina.
- Navojni binarni zapis binarno je stablo koji se sastoji od 0 nema čvorova ili 2 broja čvorova.
Tehnike prelaska
Prelazak stabala jedna je od najčešćih operacija koja se izvodi na strukturi podataka o stablima u kojoj se svaki čvor posjetio točno jednom na sistematski način.
- Inorder - U ovom se stazu prolazi lijevo potkresivnost rekurzivno, zatim se posjećuje korijenski čvor, a u posljednjem je desna podrema.
- Preorer - U ovom je stazu korijenski koridor posjećen najprije, zatim lijevo podređenje i na kraju desno poddrevo.
- Postorder - Ova tehnika posjećuje lijevo subtree, zatim desno subtree i posljednji root root.
- U stablu B maksimalni broj podređenih čvorova koji može imati ne-terminalni čvor je M gdje je M redoslijed B-stabla. S druge strane, binarno stablo može imati najviše dva potresa ili podređenih čvorova.
- B-stablo koristi se kada se podaci pohranjuju na disk, dok se binarno stablo koristi kad se podaci pohranjuju u brzoj memoriji poput RAM-a.
- Drugo područje primjene za B-stablo je struktura podataka indeksiranja koda u DBMS-u, nasuprot tome, Binarno stablo se koristi u optimizaciji koda, huffmanovom kodiranju itd.
- Maksimalna visina B stabla je trupacMN (M je red stabla). Suprotno, maksimalna visina binarnog stabla je zapisnik2N (N je broj čvorova, a baza je 2 jer je za binarne).
Zaključak
B-stablo se koristi preko binarnog i binarnog stabla pretraživanja. Glavni razlog za to je memorijska hijerarhija gdje je CPU povezan s predmemoriranjem kanala velike propusnosti dok je CPU povezan s diskom putem kanala niske propusnosti. Binarno stablo koristi se kada su zapisi pohranjeni u RAM-u (mali i brzi), a B-stablo kad se zapisi pohranjuju na disk (veliki i spor). Dakle, upotreba B-stabla umjesto Binarnog stabla značajno smanjuje vrijeme pristupa zbog visokog faktora grananja i smanjene visine stabla.
