Ďalším rozdielom medzi stromom B a binárnym stromom je, že B-strom musí mať všetky jeho podradné uzly na rovnakej úrovni, zatiaľ čo binárny strom nemá také obmedzenie. Binárny strom môže mať maximálne 2 podstrešky alebo uzly, zatiaľ čo v B-strome môže mať M žiaden substres alebo uzol, kde M je poradie B-stromu.
Porovnávacia tabuľka
| Základ pre porovnanie | B-tree | Binárny strom |
|---|---|---|
| Základné obmedzenie | Uzol môže mať maximálny počet M počet detských uzlov (kde M je poradie stromu). | Uzol môže mať maximálne 2 počet substrán. |
| použité | Používa sa, keď sú dáta uložené na disku. | Používa sa, keď sú záznamy a dáta uložené v pamäti RAM. |
| Výška stromu | log M N (kde m je poradie stromu M-cesta) | log 2 N |
| prihláška | Kódovanie indexovania dátovej štruktúry v mnohých DBMS. | Optimalizácia kódu, kódovanie Huffman atď. |
Definícia B-stromu
B-strom je vyvážený M-way strom a tiež známy ako vyvážený strom triedenia. Je to podobný binárnemu vyhľadávaciemu stromu, kde sú uzly organizované na základe traverzu v inorder. Komplexnosť B-stromu je O (n). Doba zložitosti vkladania a vymazávania je O (log n).
Existujú určité podmienky, ktoré musia platiť pre strom B:
- Výška stromu musí byť čo najmenšia.
- Nad listami stromu by nemali byť žiadne prázdne substráty.
- Listy stromu musia prichádzať na rovnakej úrovni.
- Všetky uzly by mali mať najmenší počet detí s výnimkou zanechania uzlov.
Vlastnosti B-stromu objednávky M
- Každý uzol môže mať maximálny počet M detí a minimálny počet detí M / 2 alebo akékoľvek číslo od 2 do maxima.
- Každý uzol má o jeden kľúč menej ako deti s maximálnymi kľúčmi M-1.
- Usporiadanie kľúčov je v určitom špecifickom poradí v uzloch. Všetky kľúče v podstrom prítomných v ľavej časti kľúča sú predchodcami kľúča a kľúč, ktorý sa nachádza vpravo od kľúča, sa nazýva nástupcovia.
- V čase vloženia plného uzla sa strom rozdelí na dve časti a kľúč s mediánnou hodnotou sa vloží do nadradeného uzla.
- Operácia zlúčenia prebieha po odstránení uzlov.
Definícia binárneho stromu
Binárny strom je stromová štruktúra, ktorá môže mať maximálne dva ukazovatele pre svoje detské uzly. To znamená, že najvyšší stupeň, ktorý uzol môže mať, je 2 a môže existovať nulový alebo jeden stupeň uzol príliš.
Existujú určité varianty binárneho stromu, ako je striktne binárny strom, úplný binárny strom, rozšírený binárny strom atď.
- Striktne binárny strom je strom, kde každý neterminálny uzol musí mať podstrom a podstrom vpravo.
- Strom sa nazýva kompletný binárny strom, ak spĺňa podmienku, že má 2 uzly i na každej úrovni, kde i je úroveň.
- Závitová binárka je binárny strom, ktorý pozostáva buď z 0 počtu uzlov alebo z dvoch uzlov.
Traversal Techniques
Traverz stromu je jednou z najčastejších operácií vykonávaných na dátovej štruktúre stromov, v ktorej každý uzol navštívil presne raz systematicky.
- Inorder- V tomto stromovom prechode sa ľavý podstrom navštívi rekurzívne, potom sa navštívi koreňový uzol av poslednom pravom podstrom je navštívený.
- Preorer - v tomto stromovom traverzu je koreňový uzol navštívený na prvom a potom ľavom podstrom a na poslednom správnom podstrom.
- Postorder - táto technika navštívi ľavý podstrom, potom správny podstrom a posledný root uzol.
Kľúčové rozdiely medzi B-stromom a binárnym stromom
- V B-strome môže mať maximálny počet detských uzlov nekonečný uzol M, kde M je poradie B-stromu. Na druhej strane binárny strom môže mať nanajvýš dva substrety alebo detské uzly.
- B-strom sa používa, keď sú dáta uložené na disku, zatiaľ čo binárny strom sa používa, keď sú dáta uložené v rýchlej pamäti ako RAM.
- Ďalšou oblasťou aplikácie pre B-tree je kódová indexácia dátovej štruktúry v DBMS, naopak Binárny strom sa používa pri optimalizácii kódu, huffmanovom kódovaní atď.
- Maximálna výška stromu B je log M N (M je poradie stromu). Oproti tomu maximálna výška binárneho stromu je log 2 N (N je počet uzlov a základňa je 2, pretože je to pre binárne).
záver
B-strom sa používa na binárnom a binárnom vyhľadávacom strome, hlavným dôvodom je hierarchia pamäte, v ktorej je procesor pripojený k vyrovnávacej pamäti s kanálmi s vysokou šírkou pásma, zatiaľ čo CPU je pripojený k disku cez kanál s nízkou šírkou pásma. Binárny strom sa používa, keď sú záznamy uložené v pamäti RAM (malé a rýchle) a B-strom sa používa, keď sú záznamy uložené na disku (veľké a pomalé). Takže použitie B-stromu namiesto binárneho stromu výrazne znižuje prístupový čas kvôli vysokému rozvetveniu a zníženej výške stromu.
