Razlika med B-drevesnim in Binarnim drevesom
Vsebina
- Primerjalna tabela
- Opredelitev B-drevesa
- Lastnosti B-drevesa reda M
- Opredelitev Binarnega drevesa
- Prehodne tehnike
- Zaključek
B-drevo in Binarno drevo sta tipi nelinearne strukture podatkov. Čeprav se zdi, da sta izraza podobna, vendar sta v vseh pogledih različna. Binarno drevo se uporablja, kadar so zapisi ali podatki shranjeni v RAM-u namesto na disku, saj je hitrost dostopa RAM-a veliko večja od diska. Po drugi strani se B-drevo uporablja, ko se podatki shranijo na disk, zmanjša čas dostopa z zmanjšanjem višine drevesa in povečanjem vej v vozlišču.
Druga razlika med B-drevesnim in binarnim drevesom je, da mora imeti B-drevo vsa svoja podrejena vozlišča na isti ravni, medtem ko dvojiško drevo nima takšnih omejitev. Binarno drevo ima lahko največ 2 podvrsti ali vozlišč, medtem ko ima v B-drevesu M nič podrezij ali vozlišč, kjer je M vrstni red B-drevesa.
- Primerjalna tabela
- Opredelitev
- Ključne razlike
- Zaključek
Primerjalna tabela
| Osnove za primerjavo | B-drevo | Binarno drevo |
|---|---|---|
| Bistvena omejitev | Vozlišče lahko ima največ M število otroških vozlišč (kjer je M vrstni red drevesa). | Vozlišče ima lahko največ 2 podštevilka. |
| Rabljeni | Uporablja se pri shranjevanju podatkov na disku. | Uporablja se, kadar so zapisi in podatki shranjeni v RAM-u. |
| Višina drevesa | dnevnikM N (kjer je m vrstni red drevesa M) | dnevnik2 N |
| Uporaba | Struktura podatkov o indeksiranju kode v mnogih sistemih DBMS. | Optimizacija kode, Huffmanovo kodiranje itd. |
Opredelitev B-drevesa
Drevo B je uravnoteženo M-way drevo in znano tudi kot drevo uravnotežene sorte. Podobno je z binarnim iskalnim drevesom, kjer so vozlišča organizirana na podlagi prečkanja. Prostornost kompleksnosti B-drevesa je O (n). Časovna zapletenost vstavljanja in brisanja je O (log n).
Za drevo B veljajo nekateri pogoji:
- Višina drevesa mora biti čim manjša.
- Nad listi drevesa ne sme biti nobenih praznih podkosti.
- Listi drevesa morajo priti na isti ravni.
- Vsa vozlišča morajo imeti najmanj otrok, razen vozlišč.
Lastnosti B-drevesa reda M
- Vsako vozlišče ima največ M otrok in najmanjše M / 2 število otrok ali poljubno število od 2 do največjega.
- Vsako vozlišče ima eno tipko manj kot otroci z največ M-1 tipkami.
- Razporeditev tipk je v določenem vrstnem redu znotraj vozlišč. Vsi ključi v poddrevi, ki so na levi strani tipke, so predhodniki ključa in tisti, ki so prisotni na desni strani, se imenujejo nasledniki.
- Ob vstavitvi polnega vozlišča se drevo razcepi na dva dela in ključ z srednjo vrednostjo se vstavi v nadrejeno vozlišče.
- Operacija spajanja se izvede, ko so vozlišča izbrisana.
Opredelitev Binarnega drevesa
Binarno drevo je drevesna struktura, ki ima lahko največ dva kazalca za svoja podrejena vozlišča. Pomeni, da ima vozlišče najvišjo stopnjo 2 in lahko obstaja tudi nič ali enostopenjsko vozlišče.
Obstajajo določene različice binarnega drevesa, kot je strogo binarno drevo, popolno binarno drevo, razširjeno binarno drevo itd.
- Strogo binarno drevo je drevo, pri katerem mora imeti vsako nesternalno vozlišče levo poddrevo in desno podtretje.
- Drevo se imenuje Popolno binarno drevo, kadar izpolnjuje pogoj, da ima 2 jaz vozlišča na vsaki ravni, kjer je i nivo.
- Navojni binarni zapis je binarno drevo, ki je sestavljeno iz 0 nič vozlišč ali 2 števila vozlišč.
Prehodne tehnike
Prehod dreves je ena najpogostejših operacij, ki se izvaja na strukturi podatkov o drevesih, v kateri je vsako vozlišče sistematično obiskal točno enkrat.
- Inorder - V tem drevesnem prehodu se levo podkritje obišče rekurzivno, nato se obišče korensko vozlišče in v zadnjem desnem podklesarju je obiskano.
- Preorer - V tem drevesnem prehodu je koreninsko vozlišče najprej obiskano, nato levo poddrevo in nazadnje desno podtretje.
- Postorder - Ta tehnika obišče levo podrevje, nato desno podrevje in nazadnje korensko vozlišče.
- V B-drevesu je največje število otroških vozlišč, ki jih lahko ima ne-terminalno vozlišče, M, kjer je M vrstni red B-drevesa. Po drugi strani ima lahko binarno drevo največ dva podvrsta ali podrejena vozlišča.
- B-drevo se uporablja, kadar so podatki shranjeni na disku, medtem ko se binarno drevo uporablja, kadar so podatki shranjeni v hitrem pomnilniku, kot je RAM.
- Drugo področje uporabe B-drevesa je struktura podatkov o indeksiranju kode v DBMS, nasprotno pa je binarno drevo uporabljeno pri optimizaciji kod, kodiranju Huffmana itd.
- Največja višina B-drevesa je hlodMN (M je vrstni red drevesa). Največja višina binarnega drevesa je dnevnik2N (N je število vozlišč, osnova pa 2, ker je za binarno različico).
Zaključek
Drevo B se uporablja nad binarnim in binarnim iskalnim drevesom. Glavni razlog za to je hierarhija pomnilnika, pri kateri je CPU povezan s predpomnilnikom s kanali visoke pasovne širine, medtem ko je CPU povezan z diskom prek kanala z nizko pasovno širino. Binarno drevo se uporablja, kadar so zapisi shranjeni v RAM-u (majhni in hitri), B-drevo pa, kadar so zapisi shranjeni na disku (velik in počasen). Uporaba B-drevesa namesto Binarnega drevesa znatno zmanjša čas dostopa zaradi visokega razvejanega faktorja in zmanjšane višine drevesa.
