Binäärihakupuu (BST) esimerkin kanssa

Mikä on binäärihakupuu?

Binäärihakupuu on edistynyt algoritmi, jota käytetään solmun, sen vasemman ja oikean haaran analysointiin, jotka on mallinnettu puurakenteessa, ja arvon palauttamiseen. BST on suunniteltu yksinkertaisen binäärihakualgoritmin arkkitehtuurille; siksi se mahdollistaa nopeammat solmujen haut, lisäykset ja poistot. Tämä tekee ohjelmasta todella nopean ja tarkan.

Binaarihakupuun attribuutit

BST koostuu useista solmuista ja koostuu seuraavista määritteistä:

• Puun solmut esitetään vanhempi-lapsi-suhteessa.
• Jokaisella pääsolmulla voi olla nolla lapsisolmua tai enintään kaksi alisolmua tai alipuuta vasemmalla ja oikealla puolella.
• Jokaisella alipuulla, joka tunnetaan myös nimellä binäärihakupuu, on alihaara niiden oikealla ja vasemmalla puolella.
• Kaikki solmut on linkitetty avain-arvo-pareilla.
• Vasemmassa alipuussa olevien solmujen avaimet ovat pienempiä kuin niiden pääsolmun avaimet.
• Vastaavasti oikeanpuoleisessa alipuussa olevien solmujen avaimet ovat suurempia kuin niiden pääsolmun avaimet.

1. On pääsolmu eli ylätaso 11. Sen alla on vasen ja oikea solmu/haara, joilla on omat avainarvonsa.
2. Oikean alipuun avainarvot ovat suurempia kuin pääsolmun.
3. Vasemman alipuun avainarvot ovat pienemmät kuin pääsolmun.

Miksi tarvitsemme binaarihakupuuta?

• Kaksi tärkeintä tekijää, jotka tekevät binäärisestä hakupuusta optimaalisen ratkaisun mihin tahansa reaalimaailman ongelmaan, ovat nopeus ja tarkkuus.
• Koska binäärihaku on haaramaisessa muodossa, jossa on emo-lapsi-suhteet, algoritmi tietää, mistä puun paikasta elementtejä pitää etsiä. Tämä vähentää avainarvovertailujen määrää, jotka ohjelman on tehtävä halutun elementin löytämiseksi.
• Lisäksi, jos etsittävä alkio on suurempi tai pienempi kuin pääsolmu, solmu tietää, kummalta puun puolelta etsiä. Syynä tähän on se, että vasen alipuu on aina pienempi kuin pääsolmu ja oikean alipuun arvot ovat aina yhtä suuret tai suuremmat kuin pääsolmun.
• BST:tä käytetään yleisesti monimutkaisten hakujen, vankan pelilogiikan, automaattisen täydennyksen ja grafiikan toteuttamiseen.
• Algoritmi tukee tehokkaasti toimintoja, kuten haku, lisääminen ja poistaminen.

Binaaristen puiden tyypit

Kolmen tyyppisiä binääripuita ovat:

• Täydellinen binääripuu: Kaikki puun tasot ovat täynnä, viimeistä tasoa lukuun ottamatta. Samoin kaikki solmut ovat täynnä, ja ne osoittavat vasemmalle reunalle.
• Täysi binääripuu: Kaikilla solmuilla on kaksi lapsisolmua paitsi lehtisolmu.
• Tasapainotettu eli täydellinen binääripuu: Puussa kaikilla solmuilla on kaksi lasta. Lisäksi jokaisella alisolmulla on sama taso.

Lue lisää Binääripuu tietorakenteessa jos olet kiinnostunut.

Kuinka binäärihakupuu toimii?

Puussa on aina juurisolmu ja muita lapsisolmuja, joko vasemmalla tai oikealla. Algoritmi suorittaa kaikki toiminnot vertaamalla arvoja juuriin ja sen muihin lapsisolmuihin vasemmassa tai oikeassa alipuussa vastaavasti.

Lisättävästä, haettavasta tai poistettavasta elementistä riippuen algoritmi voi vertailun jälkeen helposti poistaa juurisolmun vasemman tai oikean alipuun.

BST tarjoaa ensisijaisesti seuraavat kolme toimintotyyppiä käyttöösi:

• Hae: etsii elementin binääripuusta.
• Aseta: lisää elementin binääripuuhun.
• Poistaa: poistaa elementin binääripuusta.

Jokaisella toiminnolla on oma rakenne ja suoritus-/analyysimenetelmänsä, mutta monimutkaisin kaikista on Delete-toiminto.

Haku OperaTUKSEN

Aloita puun analysointi aina juurisolmusta ja siirry sitten joko juurisolmun oikeaan tai vasempaan alipuuhun riippuen siitä, onko etsittävä elementti pienempi vai suurempi kuin juurisolmu.

1. Haettava elementti on 10.
2. Vertaa elementtiä juurisolmuun 12, 10 < 12, jolloin siirryt vasempaan alipuuhun. Oikeaa alipuuta ei tarvitse analysoida.
3. Vertaa nyt lukua 10 solmuun 7, 10 > 7, joten siirry oikeaan alipuuhun.
4. Vertaa sitten lukua 10 seuraavaan solmuun, joka on 9, 10 > 9, katso oikeanpuoleista alipuun lasta.
5. 10 vastaa solmun arvoa, 10 = 10, palauttaa arvon käyttäjälle.

Pseudo Code BST-hakua varten

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)

liite OperaTUKSEN

Tämä on hyvin yksinkertainen operaatio. Ensin lisätään juurisolmu, jonka jälkeen seuraavaa arvoa verrataan juurisolmuun. Jos arvo on suurempi kuin juurisolmu, se lisätään oikeaan alipuuhun, ja jos se on pienempi kuin juurisolmu, se lisätään vasempaan alipuuhun.

1. BST:hen on lisättävä kuusi elementtiä vasemmalta oikealle.
2. Lisää 12 juurisolmuksi ja vertaa seuraavia arvoja 7 ja 9 lisätäksesi ne vastaavasti oikeaan ja vasempaan alipuuhun.
3. Vertaa jäljellä olevia arvoja 19, 5 ja 10 juurisolmuun 12 ja sijoita ne vastaavasti. Jos 19 > 12, sijoita se luvun 12 oikeaksi lapseksi; jos 5 < 12 ja 5 < 7, sijoita se siis luvun 7 vasemmaksi lapseksi. Vertaa nyt arvoa 10: 10 on < 12 ja 10 on > 7 ja 10 on > 9, sijoita 10 luvun 9 oikeaksi alipuuksi.

Pseudokoodi solmun lisäämiseksi BST:hen

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

Poista OperaTIONS

BST:stä solmun poistamiseen on joitakin tapauksia, kuten juuren tai lehtisolmun poistaminen. Juuren poistamisen jälkeen meidän on otettava huomioon juurisolmu.

Oletetaan, että haluamme poistaa lehtisolmun, voimme vain poistaa sen, mutta jos haluamme poistaa juuren, meidän on korvattava juuren arvo toisella solmulla. Otetaan seuraava esimerkki:

• Tapaus 1 – Solmu, jossa ei ole lapsia: Tämä on helpoin tilanne, sinun tarvitsee vain poistaa solmu, jolla ei ole muita lapsisolmuja oikealla tai vasemmalla.
• Tapaus 2 – Solmu, jolla on yksi lapsi: Kun olet poistanut solmun, yhdistä sen lapsisolmu poistetun arvon pääsolmuun.
• Tapaus 3 – Solmu, jolla on kaksi lasta: Tämä on vaikein tilanne, ja se toimii seuraavien kahden säännön mukaisesti:
  • 3a – Järjestyksessään edeltäjä: Sinun on poistettava solmu, jolla on kaksi lasta, ja korvattava se poistetun solmun vasemman alipuun suurimmalla arvolla.
  • 3b – Järjestyksessään seuraaja: Sinun on poistettava solmu, jolla on kaksi lasta, ja korvattava se poistetun solmun oikean alipuun pienimmällä arvolla.

1. Tämä on ensimmäinen poistotapaus, jossa poistetaan solmu, jolla ei ole lapsia. Kuten kaaviosta näkyy, solmuilla 19, 10 ja 5 ei ole lapsia. Mutta poistamme solmun 19.
2. Poista arvo 19 ja poista linkki solmusta.
3. Katso BST:n uusi rakenne ilman 19:ää.

1. Tämä on toinen poistotapaus, jossa poistetaan solmu, jolla on yksi lapsi. Kuten kaaviosta näkyy, solmulla 9 on yksi lapsi.
2. Poista solmu 9 ja korvaa se sen lapsisolmulla 10, ja lisää linkki solmusta 7 solmuun 10.
3. Katso BST:n uusi rakenne ilman 9:ää.

1. Tässä poistat solmun 12, jolla on kaksi lasta.
2. Solmun poisto tapahtuu edeltäjäsäännön mukaisesti, mikä tarkoittaa, että vasemman puolen alipuun suurin elementti, joka sisältää 12 elementtiä, korvaa sen.
3. Poista solmu 12 ja korvaa se luvulla 10, koska se on vasemman alipuun suurin arvo.
4. Tarkastele BST:n uutta rakennetta 12:n poistamisen jälkeen.

1. Poista solmu 12, jolla on kaksi lasta.
2. Solmun poisto tapahtuu In-Order Successor -säännön perusteella, mikä tarkoittaa, että oikean alipuun pienin elementti 12 korvaa sen.
3. Poista solmu 12 ja korvaa se luvulla 19, koska se on oikean alipuun pienin arvo.
4. Tarkastele BST:n uutta rakennetta 12:n poistamisen jälkeen.

Pseudo Code solmun poistamista varten

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)

Tärkeät ehdot

• Aseta: Lisää elementin puuhun / luo puun.
• Hae: Etsii elementtiä puusta.
• Ennakkotilauksen läpikulku: Kulkee puun läpi ennakkotilauksella.
• Sisäisen järjestysläpikulku: Liikkuu puun yli tietyssä järjestyksessä.
• Jälkitilauksen läpikulku: Kulkee puun läpi jälkikäteen.

UKK