Kitas skirtumas tarp B-medžio ir dvejetainio medžio yra tas, kad B-medis turi turėti visus jo mazgus viename lygyje, o dvejetainis medis neturi tokio suvaržymo. Dvejetainis medis gali turėti ne daugiau kaip 2 subtrees arba mazgus, o B-medyje gali būti M subtilų arba mazgų, kuriuose M yra B-medžio eilė.
Palyginimo diagrama
| Palyginimo pagrindas | B-medis | Dvejetainis medis |
|---|---|---|
| Esminis suvaržymas | Mazgas gali turėti maks. M vaikų mazgų skaičių (kur M yra medžio eilė). | Mazgas gali turėti ne daugiau kaip 2 subtūkių skaičių. |
| Naudota | Jis naudojamas, kai duomenys saugomi diske. | Jis naudojamas, kai įrašai ir duomenys yra saugomi RAM. |
| Medžio aukštis | log M N (kur m yra M kelio eilės tvarka) | log 2 N |
| Taikymas | Kodų indeksavimo duomenų struktūra daugelyje DBVS. | Kodo optimizavimas, „Huffman“ kodavimas ir kt. |
B medžio apibrėžimas
B-medis yra subalansuotas M-kelias ir taip pat žinomas kaip subalansuotas rūšies medis. Jis yra panašus į dvejetainį paieškos medį, kuriame mazgai yra organizuojami pagal inertiškumą. B-medžio erdvės sudėtingumas yra O (n). Įterpimo ir ištrynimo laiko sudėtingumas yra O (log n).
Yra tam tikrų sąlygų, kurios turi atitikti B medį:
- Medžio aukštis turi būti kuo mažesnis.
- Virš medžio lapų neturėtų būti tuščių medžių.
- Medžio lapai turi būti tame pačiame lygyje.
- Visi mazgai turi turėti mažiausiai vaikų, išskyrus atostogų mazgus.
B eilės M savybės
- Kiekvienas mazgas gali turėti maksimalų M vaikų skaičių ir minimalų M / 2 vaikų skaičių arba bet kokį skaičių nuo 2 iki maksimalaus.
- Kiekvienas mazgas turi vieną raktą mažiau nei vaikai, turintys maksimalius M-1 raktus.
- Raktų išdėstymas yra tam tikroje konkrečioje eilutėje. Visi raktai, esantys kairėje pusėje esančiame subtree, yra raktų pirmtakai, o raktų dešinėje esantys vadinamieji - įpėdiniai.
- Įterpiant pilną mazgą, medis padalija į dvi dalis, o raktas su medianine reikšme įterpiamas į pagrindinį mazgą.
- Sujungimas vyksta tada, kai mazgai ištrinami.
Dvejetainio medžio apibrėžimas
Dvejetainis medis yra medžio struktūra, kuri gali turėti ne daugiau kaip du nukreipimus savo vaikų mazgų atžvilgiu. Tai reiškia, kad didžiausias laipsnis, kurį gali turėti mazgas, gali būti 2 ir taip pat gali būti nulis arba vieno laipsnio mazgas.
Yra tam tikrų dvejetainio medžio variantų, pvz., Griežtai dvejetainis medis, pilnas dvejetainis medis, išplėstas dvejetainis medis ir tt
- Griežtai dvejetainis medis yra medis, kuriame kiekvienas ne galinis mazgas turi turėti kairę subtree ir dešinę pusę.
- Medis vadinamas užbaigtu dvejetainiu medžiu, kai jis atitinka 2 i mazgus kiekviename lygyje, kur i yra lygis.
- Srieginis dvejetainis yra dvejetainis medis, kurį sudaro 0 mazgų arba 2 mazgų skaičius.
Traverso metodai
Medžių judėjimas yra viena iš dažniausiai atliekamų medžių duomenų struktūros operacijų, kuriose kiekvienas mazgas sistemingai aplankė vieną kartą.
- Inorder- Šiame medyje važiuoja kairysis subtree, rekursyviai, tada lankomasis mazgas yra aplankomas, o paskutiniame tinkle apsilankoma.
- Tikslas- Šiame medyje perkeliamas šaknų mazgas pirmą kartą, o paskui - kairėje subtree ir galiausiai dešinėje.
- Postorder- Šis metodas apsilanko kairėje subtree, tada dešinėje pusėje ir paskutiniame šaknų mazge.
Pagrindiniai skirtumai tarp B-medžio ir dvejetainio medžio
- B-medyje maksimalus vaikų mazgų skaičius, neturintis galinių mazgų, gali būti M, kur M yra B-medžio eilė. Kita vertus, dvejetainis medis gali turėti ne daugiau kaip du subtrees arba vaikų mazgus.
- B-medis naudojamas tada, kai duomenys saugomi diske, o dvejetainis medis yra naudojamas, kai duomenys saugomi kaip atmintis.
- Kita B-medžio taikymo sritis yra kodų indeksavimo duomenų struktūra DBVS, priešingai, kodinis optimizavimas, „huffman“ kodavimas ir kt.
- Maksimalus B medžio aukštis yra log M N (M yra medžių eilė). Binarinio medžio aukštis yra lygus log 2 N (N yra mazgų skaičius, o bazė yra 2, nes ji skirta dvejetainiams).
Išvada
B-medis naudojamas per dvejetainį ir dvejetainį paieškos medį. Pagrindinė priežastis yra atminties hierarchija, kurioje CPU yra prijungtas prie talpyklos su didelės spartos kanalais, o CPU yra prijungtas prie disko per mažo pralaidumo kanalą. Dvejetainis medis naudojamas, kai įrašai yra saugomi RAM (mažas ir greitas), o B-medis naudojamas, kai įrašai yra saugomi diske (didelis ir lėtas). Taigi, naudojant B-medį, o ne dvejetainį medį, žymiai sumažėja prieigos laikas dėl aukšto šakos faktoriaus ir sumažinto medžio aukščio.
