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

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ópontjai szülő-gyermek kapcsolatban vannak ábrázolva
• 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ópontjuk kulcsai
• Hasonlóképpen, a bal oldali részfa csomópontjainak kulcsai kisebb értékűek, mint a szülőcsomópontjuk kulcsai.

1. Van a fő csomópont vagy a 11-es szülőszint. Alatta bal és jobb oldali 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észfának vannak értékei, mint a szülőcsomópontnak

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

• A két fő tényező, amely a bináris keresési fát minden valós probléma optimális megoldásává teszi, 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.
• Ezenkívül abban az esetben, ha a keresendő elem nagyobb vagy kisebb, mint a szülőcsomópont, a csomópont tudja, hogy melyik faoldalt kell keresni. Ennek az az oka, hogy a bal oldali részfa mindig kisebb, mint a szülőcsomópont, és a jobb oldali részfa értéke mindig egyenlő vagy nagyobb, mint a szülőcsomópont.
• 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 fák összes szintje tele van az utolsó szint lehetséges kivételeivel. Hasonlóképpen, az összes csomópont megtelt, és a szélső bal oldalt irányítja.
• Teljes bináris fa: A levél kivételével minden csomópontnak van 2 gyermekcsomópontja.
• Kiegyensúlyozott vagy tökéletes bináris fa: A fában minden csomópontnak két gyermeke van. Emellett mindegyik alcsomópontnak ugyanaz a szintje.

Tudjon meg többet 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ölni kívánt elemtől függően az algoritmus az összehasonlítás után 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: megkeresi az elemet a bináris fából
• Beszúrás: hozzáad egy elemet a bináris fához
• Törlés: az elem törlése 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 kezdje, majd lépjen tovább a gyökércsomópont jobb vagy bal részfájához, attól függően, hogy az elhelyezendő elem kisebb vagy nagyobb, mint a gyökér.

1. A keresendő elem a 10
2. Hasonlítsa össze az elemet a 12-es gyökércsomóponttal, 10 < 12, így a bal oldali részfára lép. Nem kell elemezni a jobb oldali részfát
3. Hasonlítsa össze a 10-et a 7-es csomóponttal, 10 > 7, tehát lépjen a jobb oldali részfára
4. Ezután hasonlítsa össze a 10-et a következő csomóponttal, amely 9, 10 > 9, és nézze meg a megfelelő részfa gyermekét
5. 10 egyezik a csomópont értékével, 10 = 10, visszaadja az értéket a felhasználónak.

Pszeudo kód a kereséshez a BST-ben

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 egyenes művelet. Először a gyökércsomópontot szúrja be, majd a következő értéket összehasonlítja a gyökércsomóponttal. Ha az érték nagyobb, mint a gyökér, akkor a jobb oldali részfához kerül, ha pedig kisebb, mint a gyökér, akkor a bal oldali részfához.

1. Van egy 6 elemből álló lista, amelyeket balról jobbra kell beilleszteni a BST-be
2. Szúrja be a 12-t gyökércsomópontként, és hasonlítsa össze a következő 7-es és 9-es értéket a jobb és bal részfába történő beszúráshoz
3. Hasonlítsa össze a fennmaradó 19, 5 és 10 értékeket a 12 gyökércsomóponttal, és ennek megfelelően helyezze el őket. 19 > 12 helyezze a 12 jobb gyermekeként, 5 < 12 és 5 < 7, ezért helyezze a 7 bal gyermekeként. Hasonlítsa össze most a 10-et, 10 < 12 és 10 > 7 és 10 > 9, 10. mint a 9 jobb oldali részfája.

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öl OperaTIONS

Egy csomópont BST-ből való törlésére van néhány eset, pl. gyökér vagy levél csomópont törlése. Ezenkívül a gyökér törlése után gondolnunk kell a gyökércsomópontra.

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 gyermekekkel: ez a legegyszerűbb helyzet, csak törölni kell azt a csomópontot, amelynek nincs több gyermeke a jobb vagy a bal oldalon.
• 2. eset – Csomópont egy gyermekkel: miután törölte a csomópontot, egyszerűen csatlakoztassa a gyermek csomópontját a törölt érték szülőcsomópontjához.
• 3. eset Csomópont két gyerekkel: ez a legnehezebb helyzet, és a következő két szabály szerint működik
• 3a – Sorrendelődben: törölnie kell a két gyermeket tartalmazó csomópontot, és le kell cserélnie a törölt csomópont bal oldali részfájának legnagyobb értékére.
• 3b – Sorrend utódjában: törölnie kell a két gyermeket tartalmazó csomópontot, és le kell cserélnie a törölt csomópont jobb oldali részfájának legnagyobb értékére.

1. Ez az első olyan törlési eset, amikor olyan csomópontot töröl, amelynek nincsenek gyermekei. Amint az ábrán látható, 19, 10 és 5 éveseknek nincs gyereke. De a 19-et töröljük.
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 szerkezetét 19 nélkül

1. Ez a második törlési eset, amikor egy olyan csomópontot töröl, amelynek 1 gyermeke van, ahogy az ábrán látható, hogy 9-nek egy gyermeke van.
2. Törölje a 9-es csomópontot, és cserélje ki a gyermek 10-re, és adjon hozzá egy hivatkozást 7-től 10-ig
3. Tekintse meg a BST új szerkezetét 9 nélkül

1. Itt törli a 12-es csomópontot, amelynek két gyermeke van
2. A csomópont törlése a sorrend előd szabálya alapján történik, ami azt jelenti, hogy a 12-es bal oldali részfa legnagyobb eleme helyettesíti azt.
3. Törölje a 12-es csomópontot és cserélje ki 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. 1 Töröljön egy 12-es csomópontot, amelynek két gyermeke van
2. 2 A csomópont törlése az In Order Successor szabály alapján történik, ami azt jelenti, hogy a 12-es jobb oldali részfa legnagyobb eleme helyettesíti azt.
3. 3 Törölje a 12-es csomópontot, és cserélje ki 19-re, mivel ez a legnagyobb érték a jobb oldali részfán
4. 4 Tekintse meg a BST új struktúráját a 12 törlése után

Pszeudo kód egy 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 to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Fontos feltételek

• Beszúrás: Beszúr egy elemet egy fába/fát hoz létre.
• Keresés: Egy fa elemében keres.
• Előrendelési bejárás: Előrendelési módon bejár egy fát.
• Inorder Traversal: Rendezett módon halad át egy fán.
• Utólagos bejárás: rendelés utáni módon bejár egy fát.

Összegzésként

• A BST egy haladó 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 mindig jelen marad.
• Van egy bal oldali részfa és egy jobb oldali részfa. A bal oldali részfa olyan értékeket tartalmaz, amelyek kisebbek, mint a gyökércsomópont. A jobb oldali részfa azonban olyan értéket tartalmaz, amely nagyobb, mint a gyökércsomópont.
• Minden csomópontnak lehet nulla, egy vagy két gyermeke.
• A bináris keresési fa megkönnyíti az olyan elsődleges műveleteket, mint a keresés, beszúrás és törlés.
• A törlésnek, mivel a legösszetettebb, több eset is van, például egy csomópont gyermek nélkül, csomópont egy gyermekkel és csomópont két gyermekkel.
• Az algoritmust valós megoldásokban, például játékokban, automatikus kiegészítésben és grafikában használják.