B-fa és bináris fa

Szerző: Laura McKinney
A Teremtés Dátuma: 4 Április 2021
Frissítés Dátuma: 24 Március 2024
Anonim
B-fa és bináris fa - Más
B-fa és bináris fa - Más

Tartalom

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ázisB-treeBináris fa
bázisA 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.
BoltA B-fa kódot a lemez tárolja.A bináris fa kódot a RAM tárolja
MagasságA B-fa magassága log N leszA bináris fa magassága log lesz2 N
AlkalmazásA 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

  1. 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.
  2. A B-fa kódot a lemez tárolja, míg a bináris fa kódot a RAM-on.
  3. A B-fa magassága logN, míg a bináris fa magassága log2 N
  4. 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.

Magyarázó videó