Különbség a B-fa és a bináris fa között
Tartalom
- Összehasonlító táblázat
- A B-fa meghatározása
- Az M sorrendű B-fa tulajdonságai
- A bináris fa meghatározása
- Átjárási technikák
- Következtetés
A B-fa és a bináris fa a nemlineáris adatszerkezet típusai. Bár a kifejezések hasonlóak, de minden szempontból eltérőek. Egy bináris fa akkor használatos, ha az iratokat vagy az adatokat a RAM-ban tárolja a lemez helyett, mivel a RAM elérési sebessége sokkal nagyobb, mint a lemeznél. Másrészt, a B-fát akkor használják, amikor az adatokat a lemezen tárolja, ez csökkenti a hozzáférési időt a fa magasságának csökkentésével és a csomópontban lévő ágak növelésével.
Egy másik különbség a B-fa és a bináris fa között az, hogy a B-fa minden gyermekcsomópontjának azonos szinten kell lennie, míg a bináris fa nem rendelkezik ilyen korlátozással. Egy bináris fa legfeljebb 2 alfát vagy csomópontot tartalmazhat, míg a B-fa esetében M nem lehet alfája vagy csomópontja, ahol M a B-fa sorrendje.
- Összehasonlító táblázat
- Meghatározás
- Főbb különbségek
- Következtetés
Összehasonlító táblázat
| Az összehasonlítás alapja | B-tree | Bináris fa |
|---|---|---|
| Alapvető kényszer | Egy csomópontnál max M gyermekcsomópont lehet (ahol M a fa sorrendje). | Egy csomópontnak legfeljebb 2 alfája lehet. |
| Használt | Akkor használja, amikor az adatok a lemezen vannak tárolva. | Akkor használja, amikor az iratokat és az adatokat a RAM memóriájában tárolja. |
| A fa magassága | logM N (ahol m az M-irányú fa sorrendje) | log2 N |
| Alkalmazás | Kódindexáló adatszerkezet sok DBMS-ben. | Kód optimalizálás, Huffman kódolás stb. |
A B-fa meghatározása
A B-fa a kiegyensúlyozott M-irányú fa, és más néven a kiegyensúlyozott fafaj. Hasonló a bináris keresési fához, ahol a csomópontok a bejövő bejárása alapján vannak elrendezve. A B-fa térbonyolultsága O (n). A beillesztés és a törlés ideje O (log n).
Bizonyos feltételeknek teljesülniük kell egy B-fa esetében:
- A fa magasságának a lehető legkisebbnek kell lennie.
- A fa levelei felett nem lehet üres alfák.
- A fa leveleinek ugyanabban a szintben kell lenniük.
- Az összes csomópontnak a lehető legkevesebb gyermeknek kell lennie, kivéve a szabadságcsomókat.
Az M sorrendű B-fa tulajdonságai
- Minden csomópontban lehet M legnagyobb gyermekek száma és minimális M / 2 gyermekeinek száma, vagy bármilyen szám lehet 2 és maximum között.
- Minden csomópontban van egy kulcs kevesebb, mint a gyerekeknél, legfeljebb M-1 kulcsokkal.
- A kulcsok elrendezése bizonyos pontrendben van a csomópontokon belül. A kulcs bal oldalán található összes részbõl álló kulcs a kulcs elõdjei, és a kulcs jobb oldalán lévõket utódoknak nevezzük.
- A teljes csomópont beillesztésekor a fa két részre oszlik, és a medián értékű kulcsot a szülő csomópontba helyezik.
- Az egyesítésre a csomópontok törlésekor kerül sor.
A bináris fa meghatározása
A bináris fa olyan faszerkezet, amelynek legfeljebb két mutatója lehet a gyermek csomópontjai számára. Ez azt jelenti, hogy a csomópont legmagasabb foka 2 lehet, és nulla vagy egy fokos is lehet.
Vannak egy bináris fa bizonyos változatai, például szigorúan bináris fa, teljes bináris fa, kiterjesztett bináris fa stb.
- A szigorúan bináris fa olyan fa, ahol minden nem-terminális csomópontnak bal és jobb oldali részfával kell rendelkeznie.
- A fát teljes bináris fának hívják, ha teljesíti a 2-es feltétel feltételeit én csomópontok minden szinten, ahol i a szint.
- A menetes bináris egy bináris fa, amely vagy 0 csomópont nélküli számból, vagy 2 csomópont számból áll.
Átjárási technikák
A fa áthaladása az egyik leggyakoribb művelet, amelyet a fa adatstruktúrán hajtanak végre, amelyben minden csomópont pontosan egyszer meglátogatta szisztematikus módon.
- Inorder - Ebben a fa-átjárásban a bal alfát rekurzív módon meglátogatják, majd meglátogatják a gyökér csomópontot és a jobb oldali alfát.
- Előkészítő - Ebben a fa-átjárásban a gyökér csomópontot először meglátogatjuk, majd a bal alsó részben és az utolsó jobb alfában.
- Postorder - Ez a technika meglátogatja a bal alsó, majd a jobb alsót és az utolsó gyökér csomópontot.
- A B-fában a nem terminális csomópontok maximális száma lehet M, ahol M a B-fa sorrendje. Másrészt a bináris fának legfeljebb két alfája vagy gyermekcsomópontja lehet.
- A B-fát akkor használják, amikor az adatok lemezre vannak tárolva, míg a bináris fát akkor használják, amikor az adatokat gyors memóriában tárolják, például RAM-ban.
- A B-fa másik alkalmazási területe a kódindexelő adatszerkezet a DBMS-ben, ezzel szemben a bináris fa a kód optimalizálásában, a huffman kódolásban stb. Szolgál.
- A B-fa maximális magassága logMN (M a fa sorrendje). Ezzel szemben a bináris fa maximális magassága log2N (N a csomópontok száma és az alap 2, mert a bináris).
Következtetés
A B-fát a bináris és a bináris keresőfánál használják, ennek fő oka a memóriahierarchia, ahol a CPU a cache-hez kapcsolódik a nagy sávszélességű csatornákkal, míg a CPU a lemezhez csatlakozik az alacsony sávszélességű csatornán keresztül. Bináris fát használunk, ha az iratokat RAM-ban tároljuk (kicsi és gyors), és B-fát, ha az iratokat lemezen tároljuk (nagy és lassú). Tehát a B-fa használata 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 alacsonyabb magassága miatt.
