Kulcskülönbség – Bináris fa és bináris keresőfa
Az adatstruktúra az adatok szisztematikus rendszerezési módja a hatékony felhasználás érdekében. Az adatok adatszerkezettel történő elrendezése csökkenti a futási időt vagy a végrehajtási időt. Ezenkívül az adatszerkezetnek minimális mennyiségű memóriát kell igényelnie. Néha az adatok fastruktúrába rendezhetők. A fa egy élekkel összekapcsolt csomópontot jelöl. A legfelső csomópont a gyökér. Minden csomópontnak maximum két csomópontja lehet. Gyermek csomópontokként ismertek. A szülőcsomóponttól balra lévő csomópont a bal oldali gyermekcsomópont, míg a szülőcsomóponttól jobbra lévő csomópont a jobb oldali csomópont. A bináris fa és a bináris keresőfa két fa adatstruktúra. A bináris fa olyan adatstruktúra, amelyben minden szülőcsomópont legfeljebb két gyermekcsomóponttal rendelkezhet. A bináris keresési fa olyan bináris fa, ahol a bal oldali gyermek csak olyan csomópontokat tartalmaz, amelyek értéke kisebb vagy egyenlő, mint a szülőcsomópont, és ahol a jobb utód csak olyan csomópontokat tartalmaz, amelyek értéke nagyobb, mint a szülőcsomóponté. Ez a legfontosabb különbség. Az adatstruktúrákkal, például a tömbökkel ellentétben a bináris fának és a bináris keresési fának nincs felső határa az adatok tárolására.
Mi az a bináris fa?
Ha az adatokat fastruktúrában rendezi el, a fa tetején lévő csomópontot gyökércsomópontnak nevezzük. Az egész fának csak egy gyökér lehet. A gyökércsomópont kivételével minden csomópontnak van egy éle felfelé egy csomóponthoz. Szülőcsomópontnak hívják. A szülőkód alatti csomópontot gyermekcsomópontnak nevezzük. Minden szülőcsomópontnak legfeljebb két gyermekcsomópontja lehet. Bal gyermekcsomópontnak és jobb gyermekcsomópontnak nevezik őket. A gyermekcsomópont nélküli csomópontot levélcsomópontnak nevezzük. Nincs konkrét mód az adatok elrendezésére a bináris fában. A gyökércsomóponttól minden csomópontig van egy útvonal.
01. ábra: Példa a bináris fára
Fent egy bináris fa példa látható. A 2. elem a fa tetején a gyökér. Minden csomópontnak legfeljebb két csomópontja van. Ha egy fa bármilyen hurkot tartalmaz, vagy ha egy csomópont kettőnél több csomópontot tartalmaz, akkor nem minősíthető bináris fának. Az egyik csomópontból a másikba való eljutáshoz mindig egy út vezet. A 2. gyökércsomópont gyermekcsomópontjai a 7 és az 5. Az is lehetséges, hogy egy csomópontnak nincsenek csomópontjai. De egyetlen csomópontnak sem lehet kettőnél több csomópontja. A gyökér jobb oldali eleme az 5. Ez az 5. elem a 9. gyermekcsomópont szülőcsomópontja. A 4. és 11. csomópontnak nincsenek gyermekelemei. Ezért ezek levél csomópontok.
A bináris fa az adatok hierarchikus sorrendben történő tárolására szolgál. Hasonló a számítógép fájlszerkezetéhez. Az adatstruktúra, mint egy tömb, meghatározott mennyiségű adatot tárolhat. De egy bináris fában a csomópontok számának nincs felső határa.
Mi az a bináris keresőfa?
A bináris keresési fa egy bináris fa adatstruktúra. A bináris fához hasonlóan a bináris keresési fának is lehet két csomópontja. A gyökércsomópont kivételével minden csomópontnak van egy éle felfelé egy csomóponthoz. Szülőcsomópontnak hívják. Az adott alatti, élével lefelé csatlakozó csomópontot gyermekcsomópontnak nevezzük. A gyermekcsomópont nélküli csomópontot levélcsomópontnak nevezzük. Minden szülőcsomópontnak legfeljebb két csomópontja lehet. Vannak utódcsomópontok, amelyek bal oldali gyermekcsomópontra és jobb gyermekcsomópontra utalnak. A legfelső elemet gyökércsomópontnak nevezzük. A bal oldali gyermek csak olyan csomópontokat tartalmaz, amelyek értéke kisebb vagy egyenlő, mint a szülőcsomópont. A megfelelő gyermek csak a szülőcsomópontnál nagyobb vagy azzal egyenlő értékű csomópontokat tartalmaz.
02. ábra: Példa a bináris keresőfára
A 8-as elem a legfelső elem. Ezért ez a gyökércsomópont. Ha a 3 szülőcsomópont, akkor az 1 és a 6 gyermekcsomópont. Az 1 a bal oldali gyermekcsomópont, míg a 6 a jobb gyermekcsomópont. A bal oldali gyermek értéke kisebb vagy egyenlő, mint a szülőcsomópont. Ha a 3 a szülőcsomópont, akkor a bal oldalon olyan elemnek kell lennie, amely kisebb vagy egyenlő, mint 3. Ebben a példában ez 1. A jobb oldali gyermek csak olyan csomópontokat tartalmaz, amelyek értéke nagyobb, mint a szülőcsomópont. Ha a 3 a szülőcsomópont, akkor a megfelelő gyermekcsomópontnak nagyobbnak kell lennie, mint 3. Ebben a példában ez 6. Hasonlóképpen van egy bizonyos sorrend az egyes adatelemek bináris keresési fába rendezéséhez. Ez egy adatstruktúra, amely hatékony módot biztosít az adatok rendezésére, lekérésére és keresésére.
Mi a hasonlóság a bináris fa és a bináris keresőfa között?
- A bináris fa és a bináris keresőfa is hierarchikus adatszerkezet.
- Mind a bináris fának, mind a bináris keresőfának van gyökere.
- Mind a bináris fának, mind a bináris keresőfának legfeljebb két gyermek csomópontja lehet.
Mi a különbség a bináris fa és a bináris keresőfa között?
Bináris fa vs bináris keresőfa |
|
| A bináris fa olyan adatstruktúra, amelyben minden szülőcsomópontnak legfeljebb két gyermekcsomópontja lehet. | A bináris keresési fa olyan bináris fa, ahol a bal oldali gyermek csak olyan csomópontokat tartalmaz, amelyek értéke kisebb vagy egyenlő, mint a szülőcsomópont, a jobb oldali pedig csak a szülőcsomópontnál nagyobb értékű csomópontokat tartalmaz. |
| Adatrendezési sorrend | |
| A bináris fának nincs meghatározott sorrendje az adatelemek elrendezésére. | A bináris keresési fának meghatározott sorrendje van az adatelemek elrendezésére. |
| Használat | |
| A bináris fát az adatok és információk hatékony megkeresésére használják egy fastruktúrában. | A bináris keresési fa az adatok beszúrására, törlésére és keresésére szolgál. |
Összefoglaló – Bináris fa és bináris keresőfa
Az adatstruktúra az adatok rendszerezésének egyik módja. Néha az adatok fastruktúrába rendezhetők. Ezek közül kettő a bináris fa és a bináris keresőfa. Ez a cikk a bináris fa és a bináris keresési fa közötti különbséget tárgy alta. A bináris fa olyan adatstruktúra, amelyben minden szülőcsomópont legfeljebb két gyermekcsomóponttal rendelkezhet. A bináris keresési fa olyan bináris fa, ahol a bal oldali gyermek csak olyan csomópontokat tartalmaz, amelyek értéke kisebb vagy egyenlő, mint a szülőcsomópont, és ahol a jobb utód csak olyan csomópontokat tartalmaz, amelyek értéke nagyobb, mint a szülőcsomópont.
Töltse le a Binary Tree vs Binary Search Tree PDF fájlját
A cikk PDF-verzióját letöltheti, és offline célokra használhatja az idézési megjegyzés szerint. Kérjük, töltse le a PDF verziót innen: Különbség a bináris fa és a bináris keresőfa között
