Mi az a bináris keresési fa?
A bináris keresési fa egy olyan fejlett algoritmus, amelyet a csomópont, annak bal és jobb elágazásának elemzésére használnak, amelyeket fa struktúrában modelleznek és visszaadják az értéket. A BST egy bináris keresési algoritmus architektúrájára van kidolgozva; ennélfogva lehetővé teszi a csomópontok gyorsabb keresését, beillesztését és eltávolítását. Ezáltal a program nagyon gyors és pontos.
Ebben az Adatstruktúra oktatóanyagban megtudhatja:
- Mi az a bináris keresési fa?
- A bináris keresési fa attribútumai
- Miért van szükség bináris keresési fára?
- A bináris fák típusai
- Hogyan működik a bináris keresési fa?
- Fontos feltételek
A bináris keresési fa attribútumai
A BST több csomópontból áll, és a következő attribútumokból áll:
- A fa csomópontjai a szülő-gyermek kapcsolatban vannak ábrázolva
- Minden szülőcsomópontnak lehet nulla gyermekcsomópontja, vagy legfeljebb két alcsomópontja vagy alfája a bal és a jobb oldalon.
- Minden részfának, más néven bináris kereső fának, alágai vannak önmagától jobbra és balra.
- Az összes csomópont kulcs-érték párokkal van összekapcsolva.
- A bal alfán található csomópontok kulcsai kisebbek, mint a szülőcsomópontjaik
- Hasonlóképpen, a bal alfa csomópontok kulcsainak értéke kisebb, mint a szülő csomópontjainak.
- Van a fő csomópont vagy a szülő 11. szintje. Alatta vannak bal és jobb csomópontok / elágazások saját kulcsértékekkel
- A jobb oldali alfa kulcsértékei nagyobbak, mint a szülőcsomópont
- A bal alfa értékei vannak, mint a szülőcsomópont
Miért van szükség bináris keresési fára?
- A két fő tényező, amely a bináris keresési fát optimális megoldássá teszi a valós problémákra, a sebesség és a pontosság.
- Annak a ténynek köszönhetően, hogy a bináris keresés elágazó formátumú, szülő-gyermek kapcsolatokkal, az algoritmus tudja, hogy a fa melyik helyén kell keresni az elemeket. Ez csökkenti a kulcsérték-összehasonlítások számát, amelyet a programnak el kell végeznie a kívánt elem megtalálásához.
- Ezenkívül abban az esetben, ha a keresendő elem nagyobb vagy kevesebb, mint a szülőcsomópont, a csomópont tudja, melyik fa oldalon kell keresni. Ennek oka, hogy a bal alfa mindig kisebb, mint a szülőcsomópont, és a jobb oldali alfa értéke mindig egyenlő vagy nagyobb, mint a szülőcsomópont.
- A BST-t általában komplex keresések, robusztus játéklogikák, automatikus kiegészítési tevékenységek és grafikák megvalósítására használják.
- Az algoritmus hatékonyan támogatja a műveleteket, például a keresést, a beszúrást és a törlést.
A bináris fák típusai
Háromféle bináris fa:
- Komplett bináris fa: A fák összes szintje tele van az utolsó szint lehetséges kivételeivel. Hasonlóképpen, az összes csomópont tele van, a szélsőbalra irányítva.
- Teljes bináris fa: Az összes csomópontnak van 2 gyermekcsomópontja, a levél kivételével.
- Kiegyensúlyozott vagy tökéletes bináris fa: A fában az összes csomópontnak két gyermeke van. Ezenkívül minden alcsomópontnak ugyanaz a szintje.
Hogyan működik a bináris keresési fa?
A fának mindig van gyökércsomópontja és további gyermekcsomópontjai, legyenek azok bal vagy jobb oldalon. Az algoritmus az összes műveletet úgy hajtja végre, hogy az értékeket ennek megfelelően hasonlítja össze a gyökérrel és annak további gyermekcsomópontjaival a bal vagy a jobb alfában.
Attól függ, hogy milyen elemet kell beilleszteni, keresni vagy törölni, az összehasonlítás után az algoritmus könnyen eldobhatja a gyökércsomópont bal vagy jobb részfáját.
A BST elsősorban a következő három típusú műveletet kínálja az Ön használatához:
- Keresés: az elemet a bináris fából keresi
- Insert: hozzáad egy elemet a bináris fához
- Törlés: az elem törlése egy bináris fáról
Minden műveletnek megvan a maga szerkezete és végrehajtási / elemzési módszere, de a legösszetettebb a Delete művelet.
Keresés művelet
Mindig kezdje meg a fa elemzését a gyökércsomópontnál, majd lépjen tovább a gyökércsomópont jobb vagy bal részfájáig, attól függően, hogy a található elem kisebb vagy nagyobb, mint a gyökér.
- A keresendő elem 10
- Hasonlítsa össze az elemet a 12, 10 <12 gyökércsomóponttal, így a bal alfára lép. Nem kell elemezni a jobb részfát
- Most hasonlítsa össze a 10-et a 7-es, 10> 7-es csomópontokkal, így lépjen a jobb oldali alfára
- Ezután hasonlítsa össze a 10-et a következő csomóponttal, amely 9, 10> 9, keresse meg a jobb alfa gyermeket
- 10 egyezik a csomópont értékével, 10 = 10, adja vissza az értéket a felhasználónak.
Helyezze be a műveletet
Ez egy nagyon egyszerű művelet. Először beillesztjük a gyökércsomópontot, majd összehasonlítjuk a következő értéket a gyökércsomóponttal. Ha az érték nagyobb, mint a gyökér, akkor hozzáadódik a jobb alfához, és ha kisebb, mint a gyökér, akkor a bal alfához.
- Van egy lista 6 elemből, amelyeket be kell illeszteni egy BST-be balról jobbra sorrendben
- Helyezze be a 12-et gyökércsomópontként, és hasonlítsa össze a következő 7-es és 9-es értékeket a megfelelő beillesztéshez a jobb és a bal alfába
- Hasonlítsa össze a fennmaradó 19., 5. és 10. értéket a 12 gyökércsomóponttal, és ennek megfelelően helyezze el őket. 19> 12 helyezze a 12-es, 5 <12 & 5 <7 jobb gyermekévé, ezért helyezze a 7-es bal gyermekévé.
- Most hasonlítsd össze a 10-et, a 10-et <12 és a 10-t> 7 és a 10-et> 9, a 10. helyet pedig a 9-es jobb részfaként.
Műveletek törlése
A Delete a legfejlettebb és legösszetettebb az összes többi művelet közül. A BST-ben több esetet kezelnek törlés céljából.
- 1. eset - Csomópont nulla gyermekkel: ez a legegyszerűbb helyzet, csak törölnie kell azt a csomópontot, amelynek jobb vagy bal oldalán nincs további gyermeke.
- 2. eset - Csomópont egy gyermekkel: miután törölte a csomópontot, egyszerűen csatlakoztassa annak gyermekcsomópontját a törölt érték szülőcsomópontjához.
- 3. eset Csomópont két gyermekkel: ez a legnehezebb helyzet, és a következő két szabály alapján működik
- 3a - Az elődben: törölje a csomópontot két gyermekkel, és cserélje ki a törölt csomópont bal alfájának legnagyobb értékére
- 3b - Rendelés utódjában: törölnie kell a két gyermekkel rendelkező csomópontot, és a törölt csomópont jobb oldali részén lévő legnagyobb értékre kell cserélnie
- Ez az első olyan törlési eset, amikor olyan csomópontot töröl, amelynek nincs gyermeke. Amint az ábrán látható, hogy 19-nek, 10-nek és 5-nek nincs gyermeke. De töröljük a 19-et.
- Törölje a 19. értéket, és távolítsa el a hivatkozást a csomópontból.
- Tekintse meg a BST új struktúráját 19 nélkül
- Ez a második olyan törlési eset, amikor egy olyan csomópontot töröl, amelynek 1 gyermeke van, amint azt az ábra is láthatja, hogy 9-nek egy gyermeke van.
- Törölje a 9 csomópontot, cserélje le 10 gyermekére, és adjon hozzá egy linket 7-től 10-ig
- Tekintse meg a BST új struktúráját 9 nélkül
- Itt törölni fogja a 12 csomópontot, amelynek két gyermeke van
- A csomópont törlése a order előd szabály alapján történik, ami azt jelenti, hogy a bal 12-es alfán a legnagyobb elem helyettesíti.
- Törölje a 12 csomópontot, és cserélje le 10-re, mivel ez a bal alsó rész legnagyobb értéke
- Tekintse meg a BST új struktúráját a 12 törlése után
- 1 Töröljön egy 12 csomópontot, amelynek két gyermeke van
- 2 A csomópont törlése az In Order Successor szabály alapján történik, ami azt jelenti, hogy a jobb 12-es alfa legnagyobb eleme helyettesíti azt
- 3 Törölje a 12 csomópontot, és cserélje le 19-re, mivel ez a legnagyobb érték a jobb részfán
- 4 A törlés után tekintse meg a BST új struktúráját
Fontos feltételek
- Beszúrás - Elem beszúrása egy fába / fa létrehozása.
- Keresés - elemet keres egy fában.
- Preorder Traversal - Előre rendelhető módon halad át a fán.
- Inorder Traversal - Sorrendben halad át a fán.
- Postorder Traversal - utólag halad át a fán.
Összegzés
- A BST egy fejlett szintű algoritmus, amely különféle műveleteket hajt végre a csomópontértékek és a gyökércsomópont összehasonlítása alapján.
- A szülő-gyermek hierarchia bármely pontja képviseli a csomópontot. Legalább egy szülő vagy gyökércsomópont folyamatosan jelen van.
- Van egy bal és jobb alfa. A bal alfa olyan értékeket tartalmaz, amelyek kisebbek, mint a gyökércsomópont. A jobb részfa azonban tartalmaz egy értéket, amely nagyobb, mint a gyökércsomópont.
- Minden csomópontnak lehet nulla, egy vagy két gyermeke.
- A bináris keresőfa megkönnyíti az elsődleges műveleteket, például a keresést, a beszúrást és a törlést.
- A törlés a legösszetettebbnek több esetben van, például egy csomópont, amelynek nincs gyermeke, egy csomópont egy gyerekkel és egy csomópont két gyermekkel.
- Az algoritmust valós megoldásokban használják, mint például játékok, automatikus kiegészítés és grafika.