B-fa és bináris fa
Tartalom
- Tartalom: A B-fa és a bináris fa közötti különbség
- Összehasonlító táblázat
- B-tree
- Bináris fa
- Főbb különbségek
- Következtetés
- Magyarázó videó
A B-fa és a bináris fa közötti különbség az, hogy a B-fa egy rendezett fa, ahol a csomópontok a keresztirányban vannak rendezve, míg a bináris fa egy rendezett fa, amelynek mutatója van minden csomóponton.
Az adatszerkezetek a legfontosabb fogalmak a számítógépes programozásban, és az adatszerkezetekben a két legfontosabb fogalom a B-fa és a bináris fa. Mindkettő különbözik egymástól. A B-fa egy válogatott fa, ahol a csomópontokat a keresztirányban rendezik, míg a bináris fa rendezett fa, amelynek mutatója van minden csomóponton. A B-fa és a bináris fa nemlineáris adatszerkezetek. Név szerint úgy tűnik, hogy mindkét kifejezés azonos, de nem azonosak, mivel különböznek egymástól. Egy bináris fa kódot a RAM-ban tárolnak, míg a B-fa kódot a lemez tárolja.
A B-fa egy M-irányú, kiegyensúlyozott fa, a B-fa kiegyensúlyozott fafajnak nevezik. A B-fában bejáratás van. A B-fa térbonyolultsága O (n). A beillesztés és a törlés ideje O (log n). A B-fa esetében a fa magasságának a lehető legkisebbnek kell lennie. A B-fában nem szabad üres részfát lennie. A fa összes levélének azonos szintűnek kell lennie. Minden csomópontban maximálisan M számú gyermek lehet, és minimum M / 2 gyermek lehet. A B-fa minden csomópontjának kevesebb kulcsnak kell lennie, mint a gyermekkulcsnak. A B-fa esetében a kulcs bal oldalán lévő kulcsok elődei. Amikor egy csomópont megtelt, és új csomópontot próbál beilleszteni, a fa két részre oszlik. Egyesítheti a csomópontokat a B-fában, amíg a csomópontok nem törlődnek.
A bináris fa két mutatóval rendelkezik, amelyek tartalmazzák a gyermek csomópontjainak címét. Vannak olyan típusú bináris fák, mint például egy szigorúan bináris fa, teljes bináris fa, kiterjesztett bináris fa stb. A szigorúan bináris fában bal alsó és jobb oldali részfának kell lennie, egy teljes bináris fában két csomópontnak kell lennie. minden szinten és a menetes bináris fában 0–2 csomópontnak kell lennie. Ha transzverzális technikákról beszélünk, akkor három keresztirányú technika a keresztirányú, az előrendelő keresztirányú és a postrend szerinti keresztirányú.
Tartalom: A B-fa és a bináris fa közötti különbség
- Összehasonlító táblázat
- B-tree
- Bináris fa
- Főbb különbségek
- Következtetés
- Magyarázó videó
Összehasonlító táblázat
bázis | B-tree | Bináris fa |
bázis | A B-fa egy rendezett fa, ahol a csomópontok rendezve vannak az inorder áthaladásakor. | A bináris fa olyan rendezett fa, amelynek mutatója van minden csomóponton. |
Bolt | A B-fa kódot a lemez tárolja. | A bináris fa kódot a RAM tárolja |
Magasság | A B-fa magassága log N lesz | A bináris fa magassága log lesz2 N |
Alkalmazás | A DBMS a B-fa alkalmazása. | A Huffman kódolás egy bináris fa alkalmazás. |
B-tree
A B-fa egy M-irányú, kiegyensúlyozott fa, a B-fa kiegyensúlyozott fafajnak nevezik. A B-fában bejáratás van. A B-fa térbonyolultsága O (n). A beillesztés és a törlés ideje O (log n). A B-fa esetében a fa magasságának a lehető legkisebbnek kell lennie.
A B-fában nem szabad üres részfát lennie. A fa összes levélének azonos szintűnek kell lennie. Minden csomópontban maximálisan M számú gyermek és minimum M / 2 gyermek lehet. A B-fa minden csomópontjának kevesebb kulcsnak kell lennie, mint a gyermekkulcsnak. A B-fa esetében a kulcs bal oldalán lévő kulcsok elődei. Ha egy csomópont megtelt, és új csomópontot próbál beilleszteni, a fa két részre oszlik. Egyesítheti a csomópontokat a B-fában, amíg a csomópontok nem törlődnek.
Bináris fa
A bináris fa két mutatóval rendelkezik, amelyek tartalmazzák a gyermek csomópontjainak címét. Vannak olyan típusú bináris fák, mint egy szigorúan bináris fa, teljes bináris fa, kiterjesztett bináris fa stb.
A szigorúan bináris fában bal és jobb részfáknak kell lennie, a teljes bináris fában minden szinten két csomópontnak kell lennie, és a menetes bináris fában 0 és 2 közötti csomópontnak kell lennie. Ha transzverzális technikákról beszélünk, akkor három transzverzális technikára van szükség, amelyek transzverzális, preorder transzverzális és post order transzverzális.
Főbb különbségek
- A B-fa egy válogatott fa, ahol a csomópontok be vannak rendezve a keresztirányban, míg a bináris fa rendezett fa, amelynek mutatója van minden csomóponton.
- A B-fa kódot a lemez tárolja, míg a bináris fa kódot a RAM-on.
- A B-fa magassága logN, míg a bináris fa magassága log2 N
- A DBMS a B-fa alkalmazása, míg a Huffman-kódolás a bináris fa alkalmazása.
Következtetés
A fenti cikkben egyértelmű különbséget látunk a B-fa és a bináris fa között a megvalósításuk között.