Binäärihakupuu (BST) esimerkin kanssa

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 vasemmanpuoleisten alipuusolmujen avaimilla on pienemmät arvot kuin niiden pääsolmun avaimilla.

1. Siellä on pääsolmu eli ylätaso 11. Sen alla on vasen ja oikea solmu/haara omilla avainarvoillaan
2. Oikealla alipuulla on avainarvot, jotka ovat suuremmat kuin pääsolmun
3. Vasemmalla alipuulla on arvot kuin pääsolmulla

Miksi tarvitsemme binaarihakupuuta?

• Kaksi päätekijää, jotka tekevät binäärihakupuusta optimaalisen ratkaisun kaikkiin reaalimaailman ongelmiin, 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ä elementti on suurempi tai pienempi kuin pääsolmu, solmu tietää, mistä puun puolelta etsiä. Syynä on, että vasen alipuu on aina pienempi kuin emosolmu ja oikeanpuoleisella alipuulla on aina yhtä suuria tai suurempia arvoja kuin yläsolmu.
• 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 puiden tasot ovat täynnä viimeisen tason mahdollisia poikkeuksia. Samoin kaikki solmut ovat täynnä, mikä ohjaa äärivasemmalle.
• Täysi binääripuu: Kaikilla solmuilla on 2 lapsisolmua lehtiä lukuun ottamatta.
• Tasapainotettu tai täydellinen binääripuu: Puussa kaikilla solmuilla on kaksi lasta. Lisäksi jokaisella alisolmulla on sama taso.

Lisätietoja 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.

Riippuen lisättävästä, haettavasta tai poistettavasta elementistä, vertailun jälkeen algoritmi voi helposti pudottaa juurisolmun vasemman tai oikean alipuun.

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

• Haku: etsii elementin binääripuusta
• Lisää: lisää elementin binääripuuhun
• Poista: poista elementti 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 pidemmälle juurisolmun oikeaan tai vasempaan alipuuhun riippuen siitä, onko sijoitettava elementti joko pienempi tai suurempi kuin juurisolmu.

1. Haettava elementti on 10
2. Vertaa elementtiä juurisolmuun 12, 10 < 12, joten siirryt vasempaan alipuuhun. Oikea-alipuuta ei tarvitse analysoida
3. Vertaa nyt 10:tä solmuun 7, 10 > 7, joten siirry oikeanpuoleiseen alipuuhun
4. Vertaa sitten 10:tä seuraavaan solmuun, joka on 9, 10 > 9, katso oikeasta alapuusta
5. 10 vastaa solmun arvoa, 10 = 10, palauttaa arvon käyttäjälle.

Pseudokoodi hakuun BST:ssä

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 erittäin suoraviivaista toimintaa. Ensin lisätään juurisolmu, sitten seuraavaa arvoa verrataan juurisolmuun. Jos arvo on suurempi kuin juuri, se lisätään oikeaan alipuuhun, ja jos se on pienempi kuin juuri, se lisätään vasempaan alipuuhun.

1. Siellä on luettelo 6 elementistä, jotka on lisättävä BST:hen järjestyksessä vasemmalta oikealle
2. Lisää 12 juurisolmuksi ja vertaa seuraavia arvoja 7 ja 9 lisätäksesi vastaavasti oikeaan ja vasempaan alipuuhun
3. Vertaa jäljellä olevia arvoja 19, 5 ja 10 juurisolmuun 12 ja sijoita ne vastaavasti. 19 > 12 aseta se luvun 12 oikeaksi lapseksi, 5 < 12 & 5 < 7, joten aseta se luvun 7 vasemmaksi lapseksi. Vertaa nyt 10, 10 on < 12 & 10 on > 7 & 10 on > 9, paikka 10 9:n oikeanpuoleisena alipuuna.

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

Solmun poistamiseksi BST:stä on joitain tapauksia, kuten juuri tai lehtisolmun poistaminen. Myös juuren poistamisen jälkeen meidän on mietittävä juurisolmua.

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 on vain poistettava se solmu, jolla ei ole enempää lapsia oikealla tai vasemmalla.
• Tapaus 2 – Solmu yhdellä lapsilla: kun olet poistanut solmun, yhdistä sen alisolmu poistetun arvon pääsolmuun.
• Tapaus 3 Solmu, jossa on kaksi lasta: tämä on vaikein tilanne, ja se toimii seuraavien kahden säännön mukaan
• 3a – Järjestyksen edeltäjässä: sinun on poistettava kahden lapsen solmu ja korvattava se poistetun solmun vasemman alipuun suurimmalla arvolla
• 3b – Järjestyksen seuraaja: sinun on poistettava kahden lapsen solmu ja korvattava se poistetun solmun oikeanpuoleisen alipuun suurimmalla arvolla

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

1. Tämä on toinen poistotapaus, jossa poistat solmun, jolla on yksi lapsi, kuten näet kaaviosta, että solmulla 1 on yksi lapsi.
2. Poista solmu 9 ja korvaa se alinumerolla 10 ja lisää linkki 7:stä 10:een
3. Katso BST:n uusi rakenne ilman 9

1. Täällä poistat solmun 12, jolla on kaksi lasta
2. Solmun poisto tapahtuu järjestyksen edeltäjäsäännön perusteella, mikä tarkoittaa, että suurin elementti vasemmassa alipuussa 12 korvaa sen.
3. Poista solmu 12 ja korvaa se numerolla 10, koska se on vasemman alipuun suurin arvo
4. Näytä BST:n uusi rakenne poistamisen jälkeen 12

1. 1 Poista solmu 12, jolla on kaksi lasta
2. 2 Solmun poisto tapahtuu järjestyksen seuraaja -säännön perusteella, mikä tarkoittaa, että oikeanpuoleisen alipuun 12 suurin elementti korvaa sen.
3. 3 Poista solmu 12 ja korvaa se numerolla 19, koska se on oikean alipuun suurin arvo
4. 4 Näytä BST:n uusi rakenne poistamisen jälkeen 12

Pseudokoodi solmun poistamiseksi

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)

Tärkeät ehdot

• Lisää: Lisää elementin puuhun/luo puu.
• Haku: Hakee puun elementtiä.
• Preorder Traversal: Kulkee puun läpi ennakkotilaustavalla.
• Inorder Traversal: Kulkee puun läpi järjestyksessä.
• Postorder Traversal: Kulkee puun läpi tilauksen jälkeisellä tavalla.

Yhteenveto

• BST on edistyneen tason algoritmi, joka suorittaa erilaisia ​​toimintoja solmuarvojen vertailun perusteella juurisolmun kanssa.
• Mikä tahansa ylätason hierarkian pisteistä edustaa solmua. Ainakin yksi ylä- tai juurisolmu on läsnä koko ajan.
• On vasen alipuu ja oikea alipuu. Vasen alipuu sisältää arvoja, jotka ovat pienempiä kuin juurisolmu. Oikea alipuu sisältää kuitenkin arvon, joka on suurempi kuin juurisolmu.
• Jokaisella solmulla voi olla joko nolla, yksi tai kaksi lasta.
• Binäärihakupuu helpottaa ensisijaiset toiminnot, kuten haku, lisääminen ja poistaminen.
• Koska Delete on monimutkaisin, siinä on useita tapauksia, esimerkiksi solmu ilman lapsia, solmu yhdellä lapsella ja solmu, jossa on kaksi lasta.
• Algoritmia käytetään reaalimaailman ratkaisuissa, kuten peleissä, automaattisessa täydennyksessä ja grafiikassa.