Egy másik különbség a B-fa és a bináris fa között az, hogy a B-fa ugyanazon a szinten minden gyermekcsomóponttal rendelkezik, míg a bináris fa nem rendelkezik ilyen korlátozással. A bináris fa maximum 2 alfát vagy csomópontot tartalmazhat, míg a B-fában az alfák vagy csomópontok M nem lehetnek, ahol M a B-fa sorrendje.
Összehasonlító táblázat
| Az összehasonlítás alapja | B-tree | Bináris fa |
|---|---|---|
| Alapvető kényszer | Egy csomópont max. M számú gyermekcsomóponton lehet (ahol M a fa sorrendje). | Egy csomópont maximum 2 alfát tartalmazhat. |
| Használt | Ezt akkor használják, ha az adatokat tárolja a lemezen. | Ezt akkor használják, ha a rekordokat és az adatokat RAM-ban tárolják. |
| A fa magassága | log M N (ahol m az M-út fa sorrendje) | log 2 N |
| Alkalmazás | Kód indexelése adatszerkezet számos DBMS-ben. | Kódoptimalizálás, Huffman kódolás stb. |
A B-fa meghatározása
A B-fa a kiegyensúlyozott M-út és a kiegyensúlyozott rendezési fa. Ez hasonló a bináris keresési fához, ahol a csomópontok a belépő út alapján szerveződnek. A B-fa térkomplexitása O (n). A beillesztési és törlési idő komplexitása O (log n).
Bizonyos feltételeknek igaznak kell lenniük egy B-fának:
- A fa magassága a lehető legkisebb legyen.
- A fa levelei felett nem lehet üres alfák.
- A fa leveleinek ugyanolyan szinten kell lenniük.
- Minden csomópontnak a legkisebb számú gyermeknek kell lennie, kivéve a szabadságcsomópontokat.
M sorrendű B-fa tulajdonságai
- Minden csomópont maximum M gyermekszámot és minimális M / 2 gyermekszámot, vagy bármilyen számot 2-től maximumig.
- Minden csomópontnak egy kulcs van, mint a maximális M-1 gombokkal rendelkező gyermekek.
- A kulcsok elrendezése a csomópontokban bizonyos sorrendben van. A kulcs bal oldalán található alfán minden kulcsa a kulcs elődei, és a kulcs jobb oldalán találhatóak az utódok.
- A teljes csomópont beillesztésekor a fa két részre oszlik, és a medián értékű kulcs a szülő csomópontba kerül.
- Az egyesülési művelet akkor történik, amikor a csomópontokat töröljük.
A bináris fa meghatározása
A bináris fa egy olyan fa struktúra, amely legfeljebb két mutatóval rendelkezik a gyermekcsomópontjaira. Ez azt jelenti, hogy a csomópont legmagasabb szintje 2 lehet, és nulla vagy egyfokozatú csomópont is lehet.
A bináris fa bizonyos változatai, mint például a szigorúan bináris fa, a teljes bináris fa, a kiterjesztett bináris fa stb.
- A szigorúan bináris fa olyan fa, ahol minden nem-terminális csomópontnak balra és jobbra kell lennie.
- A fát teljes bináris fának nevezzük, ha kielégíti azt a feltételt, hogy minden szinten 2 i csomópont van, ahol i a szint.
- A menetes bináris egy bináris fa, amely 0 csomópontból vagy 2 csomópontból áll.
Traversal technikák
A fa áthaladása az egyik leggyakoribb művelet, amelyet a faadatszerkezeten végeznek, ahol minden egyes csomópont rendszeresen egyszer egyszer látogatott meg.
- Inorder- Ebben a fában az áthaladás során a bal alfát rekurzívan látogatjuk, majd a gyökércsomópontot meglátogatjuk, és végül a jobb oldali alfát látogatjuk meg.
- Előadó- Ebben a fában a gyökércsomópontot először a bal oldali alfán és végül a jobb oldali alfán látogatják meg.
- Postorder- Ez a technika a bal alrészt, majd a jobb oldalt és az utolsó gyökér csomópontot látogatja.
A B-fa és a bináris fa közötti különbségek
- A B-fában a nem végpontos csomópontok maximális száma lehet M, ahol M a B-fa sorrendje. Másrészt, a Bináris fa legfeljebb két alfát vagy gyermekcsomópontot tartalmazhat.
- A B-fát akkor használják, ha az adatokat tárolják a lemezen, míg a bináris fát akkor használják, ha az adatokat gyors memóriában tárolják, mint a RAM.
- A B-fa másik alkalmazási területe a DBMS-ben a kód indexelő adatszerkezet, ezzel szemben a bináris fa a kód optimalizálásában, a huffman kódolásban stb.
- A B-fa maximális magassága log N N (M a fa sorrendje). A bináris fa maximális magassága log 2 N (N a csomópontok száma és az alap 2, mert bináris).
Következtetés
A B-fát a bináris és bináris keresési fa fölött használják. Ennek fő oka a memóriahierarchia, ahol a CPU a nagy sávszélességű csatornákkal a gyorsítótárhoz van csatlakoztatva, míg a CPU-t kis sávszélességű csatornán keresztül a lemezhez csatlakoztatja. A bináris fát akkor használják, ha a memóriában tárolt rekordokat (kicsi és gyors) tárolják, és a B-fát akkor használják, ha a lemezeket tárolják (nagy és lassú). Tehát a B-fa használata a Bináris fa helyett jelentősen csökkenti a hozzáférési időt a magas elágazási tényező és a fa csökkentett magassága miatt.
