Druga razlika med drevesom B in binarnim drevesom je, da mora B-drevo imeti vsa podrejena vozlišča na isti ravni, medtem ko binarno drevo nima take omejitve. Binarno drevo ima lahko največ 2 podrejenega ali vozlišča, medtem ko ima lahko v B-drevesu M ni podreje ali vozlišc, kjer je M vrstica B-drevesa.
Primerjalna tabela
| Podlaga za primerjavo | B-drevo | Binarno drevo |
|---|---|---|
| Bistvena omejitev | Vozlišče ima lahko največ M število otroških vozlišč (kjer je M vrstni red drevesa). | Vozlišče ima lahko največ 2 podrejenim. |
| Uporabljeno | Uporablja se, ko so podatki shranjeni na disku. | Uporablja se, ko so zapisi in podatki shranjeni v RAM-u. |
| Višina drevesa | log M N (kjer je m vrstica drevesa M-načina) | log 2 N |
| Uporaba | Struktura podatkov indeksiranja kode v mnogih DBMS. | Optimizacija kode, Huffmanovo kodiranje itd. |
Opredelitev B-drevesa
B-drevo je uravnoteženo drevo M-načina in je znano tudi kot uravnoteženo drevo razvrščanja. Podobno je binarnemu iskalnemu drevesu, kjer so vozlišča organizirana na podlagi obrnjene poti. Prostorska kompleksnost B-drevesa je O (n). Časovna kompleksnost vstavljanja in brisanja je O (log n).
Obstajajo določeni pogoji, ki morajo veljati za drevo B:
- Višina drevesa mora biti čim manjša.
- Nad listi drevesa ne sme biti nobenih praznih podregij.
- Listi drevesa morajo biti na isti ravni.
- Vsa vozlišča morajo imeti najmanjše število otrok, razen zapustiti vozlišča.
Lastnosti B-drevesa reda M
- Vsako vozlišče ima lahko največ M število otrok in najmanj M / 2 otrok ali poljubno število od 2 do največjega.
- Vsako vozlišče ima en ključ manj kot otroci z največjimi tipkami M-1.
- Razporeditev ključev je v določenem vrstnem redu znotraj vozlišč. Vsi ključi v podstavku, ki je prisoten na levi strani ključa, so predhodniki ključa, in da se na desni strani ključa imenujejo nasledniki.
- V času vstavljanja polnega vozlišča se drevo deli na dva dela, ključ z vrednostjo mediane pa se vstavi v starševsko vozlišče.
- Postopek združitve poteka, ko so vozlišča izbrisana.
Definicija binarnega drevesa
Binarno drevo je drevesna struktura, ki ima lahko za otroka vozlišča največ dva kazalca. To pomeni, da je najvišja stopnja, ki jo lahko ima vozlišče, 2 in da je lahko vozlišče enako ali nič.
Obstajajo nekatere različice binarnega drevesa, kot so strogo binarno drevo, popolno binarno drevo, razširjeno binarno drevo itd.
- Strogo binarno drevo je drevo, kjer mora imeti vsako netehno vozlišče levo poddrevo in desno poddrevo.
- Drevo se imenuje popolno binarno drevo, ko izpolnjuje pogoj, da ima 2 i vozlišča na vsaki ravni, kjer je i raven.
- Navojni binarni steber je binarno drevo, ki je sestavljeno iz 0 ali 2 vozlišč ali 2 števila vozlišč.
Tehnike prečkanja
Prehod dreves je ena najpogostejših operacij, ki se izvaja na drevesni podatkovni strukturi, v kateri je vsako vozlišče obiskalo natančno enkrat na sistematičen način.
- Inorder - V tem drevesu se levi podstavek obišče rekurzivno, nato pa se obišče korensko vozlišče in obišče zadnji desno poddrevo.
- Preorer - V tem drevesnem prečkanju se korensko vozlišče obišče najprej v levem podstavekju in na zadnjem desnem podstrezju.
- Postorder - Ta tehnika obiskuje levo podstablo, nato desno poddrevo in nazadnje korensko vozlišče.
Ključne razlike med drevesi B in binarnim drevesom
- V drevesu B je največje število otroških vozlišč, ki jih lahko ima nelinearno vozlišče, M, kjer je M vrstica B-drevesa. Po drugi strani lahko binarno drevo vsebuje največ dve podrejeni ali podrejeni vozlišč.
- B-drevo se uporablja, ko so podatki shranjeni v disku, medtem ko se binarno drevo uporablja, ko so podatki shranjeni v hitrem pomnilniku, kot je RAM.
- Drugo področje uporabe za B-drevo je podatkovna struktura indeksiranja kod v DBMS, v nasprotju pa je binarno drevo uporabljeno pri optimizaciji kode, kodiranju huffmanov itd.
- Največja višina B-drevesa je log M N (M je vrstni red drevesa). Največja višina binarnega drevesa je log 2 N (N je število vozlišč in baza je 2, ker je za binarno).
Zaključek
B-drevo se uporablja v binarnem in binarnem iskalnem drevesu, glavni razlog za to pa je hierarhija pomnilnika, kjer je CPU povezan s predpomnilnikom z visoko pasovno širino kanalov, medtem ko je CPU povezan z diskom preko nizko pasovne širine. Binarno drevo se uporablja, ko so zapisi shranjeni v pomnilniku RAM (majhno in hitro) in se B-drevo uporablja, ko so zapisi shranjeni v disku (veliki in počasni). Torej, uporaba B-drevesa namesto Binarnega drevesa znatno zmanjša čas dostopa zaradi visokega faktorja razvejanosti in zmanjšane višine drevesa.
