Bináris keresőfa (BST) példával

Mi az a bináris keresőfa?

A Bináris Keresőfa (BST) egy fejlett algoritmus, amely a csomópont, annak bal és jobb ágainak elemzésére szolgál, amelyeket egy fa struktúrában modelleznek, és az érték visszaadására. A BST egy alapvető bináris keresési algoritmus architektúráján alapul; így lehetővé teszi a csomópontok gyorsabb keresését, beszúrását és eltávolítását. Ezáltal a program igazán gyors és pontos.

A bináris keresőfa attribútumai

A BST több csomópontból áll, és a következő attribútumokból áll:

• A fa csomópontjait szülő-gyermek kapcsolat képviseli.
• Minden szülőcsomópontnak nulla gyermekcsomópontja vagy legfeljebb két alcsomópontja vagy részfa lehet a bal és a jobb oldalon.
• Minden részfának, más néven bináris keresési fának, vannak alágai a jobb és a bal oldalon.
• Az összes csomópont kulcs-érték párokhoz kapcsolódik.
• A bal oldali részfán található csomópontok kulcsai kisebbek, mint a szülőcsomópont kulcsai.
• Hasonlóképpen, a jobb oldali részfán található csomópontok kulcsai nagyobbak, mint a szülőcsomópont kulcsai.

1. Ott van a fő csomópont vagy szülő 11-es szint. Alatta bal és jobb csomópontok/ágak találhatók saját kulcsértékekkel.
2. A jobb oldali részfa kulcsértékei nagyobbak, mint a szülőcsomóponté.
3. A bal oldali részfa kulcsértékei kisebbek, mint a szülőcsomóponté.

Miért van szükségünk bináris keresőfára?

• A bináris keresőfát bármely valós probléma optimális megoldásává tevő két fő tényező a sebesség és a pontosság.
• Tekintettel arra, hogy a bináris keresés ágszerű formátumú szülő-gyermek relációkkal, 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 végre kell hajtania a kívánt elem megtalálásához.
• Továbbá, ha a keresendő elem értéke nagyobb vagy kisebb, mint a szülőcsomópont értéke, a csomópont tudja, hogy a fa melyik oldalán kell keresni. Ennek az az oka, hogy a bal oldali részfa mindig kisebb, mint a szülőcsomópont értéke, a jobb oldali részfa pedig mindig egyenlő vagy nagyobb értékekkel rendelkezik, mint a szülőcsomópont értéke.
• A BST-t általában összetett keresések, robusztus játéklogikák, automatikus kiegészítések és grafikák megvalósítására használják.
• Az algoritmus hatékonyan támogatja az olyan műveleteket, mint a keresés, beszúrás és törlés.

A bináris fák típusai

Háromféle bináris fa létezik:

• Teljes bináris fa: A fa összes szintje megtelt, egy lehetséges kivétellel az utolsó szinten. Hasonlóképpen, az összes csomópont megtelt, amelyek a bal szélsőre mutatnak.
• Teljes bináris fa: A levél kivételével minden csomópontnak 2 gyermekcsomópontja van.
• Kiegyensúlyozott vagy tökéletes bináris fa: A fában minden csomópontnak két gyermeke van. Ezenkívül minden alcsomópontnak ugyanaz a szintje van.

Tudjon meg többet a Bináris fa az adatstruktúrában ha érdekel.

Hogyan működik a bináris keresőfa?

A fának mindig van egy gyökércsomópontja és további gyermekcsomópontjai, akár a bal, akár a jobb oldalon. Az algoritmus az összes műveletet úgy hajtja végre, hogy az értékeket összehasonlítja a gyökérrel és annak további gyermekcsomópontjaival a bal vagy jobb részfában.

A beszúrandó, keresendő vagy törölendő elemtől függően az összehasonlítás után az algoritmus könnyen el tudja hagyni a gyökércsomópont bal vagy jobb oldali 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: kikeresi az elemet a bináris fából.
• beszúrása: hozzáad egy elemet a bináris fához.
• Töröl: törli az elemet egy bináris fából.

Minden műveletnek megvan a saját felépítése és végrehajtási/elemzési módszere, de a legösszetettebb az összes közül a Delete művelet.

Keresés OperaCIÓ

A fa elemzését mindig a gyökércsomópontnál kezdjük, majd haladjunk tovább a gyökércsomópont jobb vagy bal alfájához, attól függően, hogy a keresendő elem kisebb vagy nagyobb, mint a gyökér.

1. A keresendő elem a 10.
2. Hasonlítsd össze az elemet a 12-es gyökércsomóponttal, 10 < 12, így a bal oldali részfára lépsz. A jobb oldali részfát nem kell elemezni.
3. Most hasonlítsuk össze a 10-et a 7-es csomponttal, 10 > 7, tehát menjünk a jobb oldali részfára.
4. Ezután hasonlítsd össze a 10-et a következő csomóponttal, ami a 9, 10 > 9, és keresd meg a jobb oldali részfa gyermekét.
5. 10 egyezik a csomópont értékével, 10 = 10, visszaadja az értéket a felhasználónak.

Pszeudo Code a BST-ben való kereséshez

search(element, root)
    if !root
        return -1
    if root.value == element
        return 1
    if root.value < element
        search(element, root.right)
    else
        search(element, root.left)

betétlap OperaCIÓ

Ez egy nagyon egyszerű művelet. Először a gyökércsomópontot illesztjük be, majd a következő értéket összehasonlítjuk a gyökércsomóponttal. Ha az érték nagyobb, mint a gyökér, akkor a jobb oldali részfához adjuk hozzá, ha pedig kisebb, akkor a bal oldali részfához.

1. Van egy lista 6 elemből, amelyeket balról jobbra kell beilleszteni egy BST-be.
2. Helyezze be a 12-es értéket gyökércsomópontként, és hasonlítsa össze a következő 7-es és 9-es értékeket a jobb és bal oldali részfába való beszúráshoz.
3. Hasonlítsuk össze a fennmaradó 19, 5 és 10 értékeket a 12 gyökércsomóponttal, és helyezzük el őket ennek megfelelően. Ha 19 > 12, akkor a 12 jobb oldali gyermekeként helyezzük el; ha 5 < 12 és 5 < 7, akkor a 7 bal oldali gyermekeként helyezzük el. Most hasonlítsuk össze a 10-et, ahol 10 < 12, 10 > 7 és 10 > 9, és a 10-et a 9 jobb oldali részfájaként helyezzük el.

Pszeudokód csomópont beszúrásához a BST-ben

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
        y = x
        if x.value < element.value
            x = x.right
        else
            x = x.left
    if y.value < element
        y.right = element
    else
        y.left = element

Törölni OperaTIONS

Egy BST-ből egy csomópont törlésére több eset is létezik, például egy gyökér vagy egy levélcsomópont törlése. A gyökér törlése után a gyökércsomópontra is gondolnunk kell.

Tegyük fel, hogy törölni szeretnénk egy levélcsomópontot, egyszerűen törölhetjük, de ha törölni akarunk egy gyökeret, akkor a gyökér értékét egy másik csomópontra kell cserélnünk. Vegyük a következő példát:

• 1. eset – Csomópont nulla gyermekkel: Ez a legegyszerűbb helyzet, csak azt a csomópontot kell törölni, amelynek nincsenek további gyermekei a jobb vagy a bal oldalon.
• 2. eset – Csomópont egy gyermekkel: Miután törölte a csomópontot, egyszerűen kösse össze a gyermekcsomópontját a törölt érték szülőcsomópontjával.
• 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 – Sorrendben lévő előd: Törölnöd kell a két gyermekkel rendelkező csomópontot, és a törölt csomópont bal oldali részfáján található legnagyobb értékkel kell helyettesítened.
  • 3b – Sorrendben lévő utód: Törölnöd kell a két gyermekkel rendelkező csomópontot, és a törölt csomópont jobb oldali részfáján található legkisebb értékkel kell helyettesítened.

1. Ez a törlés első esete, amikor egy olyan csomópontot törölsz, amelynek nincsenek gyermekei. Amint az ábrán látható, a 19-esnek, 10-esnek és 5-ösnek nincsenek gyermekei. De a 19-est törölni fogjuk.
2. Törölje a 19-es értéket, és távolítsa el a hivatkozást a csomópontból.
3. Tekintse meg a BST új, 19 nélküli struktúráját.

1. Ez a törlés második esete, amelyben egy olyan csomópontot törölsz, amelynek van 1 gyermeke. Amint az ábrán látható, a 9-nek egy gyermeke van.
2. Töröld a 9-es csomópontot, és cseréld le a 10-es gyermekére, majd adj hozzá egy kapcsolatot a 7-es és 10-es csomópontok között.
3. Tekintse meg a BST új, 9 nélküli struktúráját.

1. Itt törölni fogod a 12-es csomópontot, amelynek két gyermeke van.
2. A csomópont törlése az előd sorrendi szabálya alapján történik, ami azt jelenti, hogy a bal oldali 12-es részfa legnagyobb eleme fogja azt helyettesíteni.
3. Töröld a 12-es csomópontot, és cseréld le 10-re, mivel ez a legnagyobb érték a bal oldali részfán.
4. Tekintse meg a BST új struktúráját a 12 törlése után.

1. Töröljön egy 12-es 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 oldali 12-es részfa legkisebb eleme fogja azt lecserélni.
3. Töröld a 12-es csomópontot, és cseréld le 19-cel, mivel ez a legkisebb érték a jobb oldali részfán.
4. Tekintse meg a BST új struktúráját a 12 törlése után.

Pszeudo Code Csomópont törléséhez

delete (value, root):
    Node x = root
    Node y = NULL
    # searching the node
    while x:
        y = x
        if x.value < value
            x = x.right
        else if x.value > value
            x = x.left
        else if value == x
            break
    # if the node is not null, then replace it with successor
    if y.left or y.right:
        newNode = GetInOrderSuccessor(y)
        root.value = newNode.value
        # after copying the value of successor, delete the successor
        free(newNode)
    else
        free(y)

Fontos feltételek

• beszúrása: Beszúr egy elemet egy fába / létrehoz egy fát.
• Keresés: Egy elemet keres egy fában.
• Előrendelési bejárás: Előre megrendelt módon halad át egy fán.
• Sorrenden belüli bejárás: Sorrendben halad át egy fán.
• Utórendelés bejárása: Utósorrendben halad át egy fán.

GYIK