Rozdiel medzi stromom B a binárnym stromom
Obsah
- Porovnávacia tabuľka
- Definícia B-stromu
- Vlastnosti B-stromu rádu M
- Definícia binárneho stromu
- Techniky kríženia
- záver
B-strom a binárny strom sú typy nelineárnej dátovej štruktúry. Podmienky sa síce zdajú podobné, ale vo všetkých aspektoch sa líšia. Binárny strom sa používa, keď sú záznamy alebo dáta uložené v pamäti RAM namiesto disku, pretože rýchlosť prístupu k pamäti RAM je oveľa vyššia ako na disku. Na druhej strane, B-strom sa používa, keď sú dáta uložené na disku, znižuje prístupový čas znížením výšky stromu a zväčšením vetiev v uzle.
Ďalším rozdielom medzi B-stromom a binárnym stromom je to, že B-strom musí mať všetky svoje podriadené uzly na rovnakej úrovni, zatiaľ čo binárny strom nemá také obmedzenia. Binárny strom môže mať maximálne 2 podstromy alebo uzly, zatiaľ čo v B-stromu môže mať M žiadny podstrom alebo uzly, kde M je poradie B-stromu.
- Porovnávacia tabuľka
- definícia
- Kľúčové rozdiely
- záver
Porovnávacia tabuľka
| Základ pre porovnanie | B-tree | Binárny strom |
|---|---|---|
| Základné obmedzenia | Uzol môže mať maximálny počet podriadených uzlov M (kde M je poradie stromu). | Uzol môže mať maximálne 2 počet podstromov. |
| použité | Používa sa pri ukladaní údajov na disk. | Používa sa pri ukladaní záznamov a údajov do pamäte RAM. |
| Výška stromu | logM N (kde m je poradie stromu M-way) | log2 N |
| prihláška | Štruktúra dát indexovania kódu v mnohých DBMS. | Optimalizácia kódu, Huffmanovo kódovanie atď. |
Definícia B-stromu
Strom B je vyvážený strom M a tiež sa nazýva vyvážený strom. Je to podobné binárnemu vyhľadávaciemu stromu, kde sú uzly usporiadané na základe priecestia. Priestorová zložitosť stromu B je O (n). Časová náročnosť vkladania a mazania je O (log n).
Pre strom B existujú určité podmienky:
- Výška stromu musí byť čo najmenšia.
- Nad listami stromu by nemali byť žiadne prázdne podstromy.
- Listy stromu musia byť na rovnakej úrovni.
- Všetky uzly by mali mať najmenší počet detí s výnimkou uzlov.
Vlastnosti B-stromu rádu M
- Každý uzol môže mať maximálny počet M detí a minimálny počet detí M / 2 alebo ľubovoľný počet od 2 do maxima.
- Každý uzol má o jeden kľúč menej ako deti s maximálnym počtom klávesov M-1.
- Usporiadanie kľúčov je v konkrétnom poradí v uzloch. Všetky kľúče v podstrome nachádzajúcom sa vľavo od kľúča sú predchodcami kľúča a tie, ktoré sa nachádzajú napravo od kľúča, sa nazývajú nástupcovia.
- V čase vloženia celého uzla sa strom rozdelí na dve časti a do rodičovského uzla sa vloží kľúč so strednou hodnotou.
- Operácia zlúčenia sa uskutoční po vymazaní uzlov.
Definícia binárneho stromu
Binárny strom je stromová štruktúra, ktorá môže mať nanajvýš dva ukazovatele pre svoje podriadené uzly. To znamená, že najvyšší stupeň, ktorý môže mať uzol, je 2 a môže existovať aj uzol s nulovým alebo jedným stupňom.
Existujú určité varianty binárneho stromu, ako napríklad striktne binárny strom, kompletný binárny strom, rozšírený binárny strom atď.
- Striktne binárny strom je strom, v ktorom musí mať každý nekonečný uzol ľavú podstromu a pravú podstromu.
- Strom sa nazýva Kompletný binárny strom, ak spĺňa podmienku 2 ja uzly na každej úrovni, kde i je úroveň.
- Závitový binárny kód je binárny strom, ktorý pozostáva z 0 bez uzlov alebo z 2 uzlov.
Techniky kríženia
Prechod stromu je jednou z najčastejších operácií vykonávaných na dátovej štruktúre stromu, v ktorej každý uzol systematicky navštevoval presne jedenkrát.
- Inorder- V tomto stromovom priechode sa ľavý podstrom navštevuje rekurzívne, potom sa navštívi koreňový uzol a na poslednom pravom podstrome sa navštívi.
- Preorer - V tomto stromovom priechode je koreňový uzol navštívený najskôr potom ľavým podstromom a posledným pravým podstromom.
- Postorder - Táto technika navštevuje ľavý podstrom, potom pravý podstrom a na poslednom koreňovom uzle.
- V B-stromu je maximálny počet podriadených uzlov, ktoré môže mať nekoncový uzol, M, kde M je poradie B-stromu. Na druhej strane binárny strom môže mať najviac dva podstromy alebo podriadené uzly.
- B-strom sa používa, keď sa údaje ukladajú na disk, zatiaľ čo binárny strom sa používa, keď sa údaje ukladajú v rýchlej pamäti, napríklad RAM.
- Ďalšou oblasťou aplikácie pre B-strom je štruktúra indexovania údajov v DBMS, naopak, binárny strom sa používa na optimalizáciu kódu, huffmanovo kódovanie atď.
- Maximálna výška stromu B je logMN (M je poradie stromu). Naopak, maximálna výška binárneho stromu je log2N (N je počet uzlov a báza 2, pretože je určený pre binárne súbory).
záver
B-strom sa používa nad binárnym a binárnym vyhľadávacím stromom. Hlavným dôvodom je hierarchia pamäte, kde je CPU spojené s vyrovnávacou pamäťou s kanálmi s vysokou šírkou pásma, zatiaľ čo CPU je pripojené k disku cez kanál s malou šírkou pásma. Binárny strom sa používa, keď sa záznamy ukladajú do pamäte RAM (malé a rýchle) a strom B sa používa, keď sa záznamy ukladajú na disk (veľké a pomalé). Takže použitie B-stromu namiesto binárneho stromu významne znižuje čas prístupu kvôli vysokému faktoru vetvenia a zníženej výške stromu.
