Mikä on binaarinen hakupuu?
Binaarihakupuu on edistyksellinen algoritmi, jota käytetään solmun, sen vasemman ja oikean haaran analysointiin, jotka mallinnetaan puurakenteessa ja palautetaan arvo. BST on suunniteltu binäärisen hakualgoritmin arkkitehtuurille; täten se mahdollistaa nopeammat hakut, lisäykset ja solmujen poistot. Tämä tekee ohjelmasta todella nopean ja tarkan.
Tässä tietorakenteen opetusohjelmassa opit:
- Mikä on binaarinen hakupuu?
- Binaarisen hakupuun attribuutit
- Miksi tarvitsemme binaarihakupuuta?
- Binaaristen puiden tyypit
- Kuinka binaarinen hakupuu toimii?
- Tärkeät ehdot
Binaarisen hakupuun attribuutit
BST koostuu useista solmuista ja koostuu seuraavista määritteistä:
- Puun solmut ovat edustettuina vanhemman ja lapsen suhteessa
- Jokaisella vanhemmalla solmulla voi olla nolla alisolmua tai enintään kaksi alisolmua tai alipuuta vasemmalla ja oikealla puolella.
- Jokaisella alipuussa, joka tunnetaan myös nimellä binäärihakupuu, on alahaaroja itsensä oikealla ja vasemmalla puolella.
- Kaikki solmut on linkitetty avainarvopareihin.
- Vasemmalla alipuussa olevien solmujen avaimet ovat pienempiä kuin niiden solmun avaimet
- Vastaavasti vasemman alipuun solmujen avaimilla on pienemmät arvot kuin heidän ylätason solmuillaan.
- Siellä on pääsolmu tai ylätaso 11. Sen alla on vasen ja oikea solmu / haara, joilla on omat avainarvot
- Oikean alipuun avainarvot ovat suuremmat kuin yläsolmun
- Vasemmalla alipuussa on arvot kuin pääsolmulla
Miksi tarvitsemme binaarihakupuuta?
- Kaksi tärkeintä tekijää, jotka tekevät binäärihakupuusta optimaalisen ratkaisun reaalimaailman ongelmiin, ovat nopeus ja tarkkuus.
- Johtuen siitä, että binaarihaku on haaramaisessa muodossa vanhempien ja lasten suhteilla, algoritmi tietää, missä puun paikassa elementtejä on etsittävä. Tämä vähentää avainarvojen vertailuja, jotka ohjelman on tehtävä halutun elementin löytämiseksi.
- Lisäksi, jos etsittävä elementti on suurempi tai vähemmän kuin yläsolmu, solmu tietää, mitä puupuolta etsitään. Syynä on, että vasen alipuu on aina pienempi kuin yläsolmu, ja oikean alipuun arvot ovat aina yhtä suuret tai suuremmat kuin yläsolmun.
- BST: tä käytetään yleisesti monimutkaisten hakujen, vankan pelilogiikan, automaattisen täydennystoiminnan ja grafiikan toteuttamiseen.
- Algoritmi tukee tehokkaasti sellaisia toimintoja kuin haku, lisäys ja poisto.
Binaaristen puiden tyypit
Kolme erilaista binääripuuta ovat:
- Täydellinen binääripuu: Kaikki puiden tasot ovat täynnä viimeisen tason mahdollisia poikkeuksia. Vastaavasti kaikki solmut ovat täynnä ja ohjaavat vasemmistoa.
- Täysi binääripuu: Kaikissa solmuissa on 2 lapsisolmua paitsi lehti.
- Tasapainoinen tai täydellinen binääripuu: Puussa kaikilla solmuilla on kaksi lasta. Lisäksi jokaisella alisolmulla on sama taso.
Kuinka binaarinen hakupuu toimii?
Puussa on aina juurisolmu ja muita lapsisolmuja, joko vasemmalla tai oikealla. Algoritmi suorittaa kaikki operaatiot vertaamalla arvoja juuri ja sen lisälapsolmut vasempaan tai oikeaan alipuuhun vastaavasti.
Riippuu 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 toimintatyyppiä käyttöösi:
- Haku: etsii elementtiä binääripuusta
- Insert: lisää elementin binääripuuhun
- Poista: poista elementti binääripuusta
Jokaisella operaatiolla on oma rakenne ja toteutus- / analyysimenetelmä, mutta kaikista monimutkaisin on Poista-operaatio.
Hakutoiminto
Aloita aina puun analysointi juurisolmusta ja siirry sitten joko juurisolmun oikeaan tai vasempaan alipuuhun riippuen siitä, onko löydettävä elementti joko pienempi tai suurempi kuin juuri.
- Haettava elementti on 10
- Vertaa elementtiä juurisolmuun 12, 10 <12, joten siirryt vasemmalle alipuulle. Oikeaa alipuuta ei tarvitse analysoida
- Vertaa nyt 10: tä solmuun 7, 10> 7, joten siirry oikeaan alipuun
- Vertaa sitten 10 seuraavaan solmuun, joka on 9, 10> 9, etsi oikea alipuun lapsi
- 10 vastaa solmun arvoa, 10 = 10, palauta arvo käyttäjälle.
Lisää toiminta
Tämä on hyvin suoraviivainen toiminta. Ensin lisätään juurisolmu ja sitten seuraavaa arvoa verrataan juurisolmuun. Jos arvo on suurempi kuin juuri, se lisätään oikeaan alipuun ja jos se on pienempi kuin juuri, se lisätään vasempaan alipuun.
- On luettelo kuudesta elementistä, jotka on lisättävä BST: ään vasemmalta oikealle
- Lisää 12 juurisolmuksi ja vertaa seuraavia arvoja 7 ja 9 lisäystä varten oikealle ja vasemmalle alipuun
- Vertaa jäljellä olevia arvoja 19, 5 ja 10 juurisolmuun 12 ja aseta ne vastaavasti. 19> 12 aseta se 12: n, 5 <12 & 5 <7: n oikeaksi lapseksi, joten aseta se 7: n vasemmaksi lapseksi.
- Vertaa nyt 10, 10 on <12 & 10 on> 7 ja 10 on> 9, aseta 10 oikeanpuoleiseksi osapuuksi 9.
Poista toiminnot
Poista on edistynein ja monimutkaisin kaikkien muiden toimintojen joukossa. BST: ssä käsitellään useita poistettavia tapauksia.
- Tapaus 1 - Solmu, jossa ei ole lapsia: tämä on helpoin tilanne, sinun tarvitsee vain poistaa solmu, jolla ei ole muita lapsia oikealla tai vasemmalla.
- Tapaus 2 - Yhden lapsen solmu: Kun olet poistanut solmun, yhdistä sen alisolmu yksinkertaisesti poistetun arvon vanhempaan solmuun.
- Tapaus 3 Solmu, jossa on kaksi lasta: tämä on vaikein tilanne, ja se toimii seuraavien kahden säännön mukaan
- 3a - Tilauksen edeltäjässä: sinun on poistettava solmu kahdella lapsella ja korvattava se suurimmalla arvolla poistetun solmun vasemmassa alipuussa
- 3b - Tilaa seuraaja: sinun on poistettava solmu, jossa on kaksi lasta, ja korvattava se suurimmalla arvolla poistetun solmun oikeanpuoleisessa alipuussa
- Tämä on ensimmäinen poisto, jossa poistetaan solmu, jolla ei ole lapsia. Kuten kaaviosta näet, 19: llä, 10: llä ja 5: llä ei ole lapsia. Mutta poistamme 19.
- Poista arvo 19 ja poista linkki solmusta.
- Tarkastele BST: n uutta rakennetta ilman 19: tä
- Tämä on toinen poisto, jossa poistetaan solmu, jolla on 1 lapsi, kuten kaaviosta näet, että yhdeksällä on yksi lapsi.
- Poista solmu 9 ja korvaa se alatasolla 10 ja lisää linkki välillä 7-10
- Tarkastele BST: n uutta rakennetta ilman 9
- Täällä poistat solmun 12, jolla on kaksi lasta
- Solmun poisto tapahtuu järjestyksessä edeltäjän säännön perusteella, mikä tarkoittaa, että vasemman 12 alipuun suurin elementti korvaa sen.
- Poista solmu 12 ja korvaa se 10: llä, koska se on vasemman alipuun suurin arvo
- Tarkastele BST: n uutta rakennetta poistamisen jälkeen 12
- 1 Poista solmu 12, jolla on kaksi lasta
- 2 Solmun poisto tapahtuu In In Successor -säännön perusteella, mikä tarkoittaa, että 12: n oikean alipuun suurin elementti korvaa sen
- 3 Poista solmu 12 ja korvaa se 19: llä, koska se on oikean alipuun suurin arvo
- 4 Tarkastele BST: n uutta rakennetta poistamisen jälkeen 12
Tärkeät ehdot
- Lisää - Lisää elementti puuhun / luo puu.
- Haku - etsii elementtiä puusta.
- Ennakkotilaus - kulkee puun ennakkotilauksella.
- Tilausliikenne - kulkee puun järjestyksessä.
- Postorder Traversal - kulkee puun jälkikäteen.
Yhteenveto
- BST on edistyneen tason algoritmi, joka suorittaa erilaisia toimintoja solmun arvojen ja juurisolmun vertailun perusteella.
- Mikä tahansa vanhempien ja lasten hierarkian piste edustaa solmua. Ainakin yksi vanhempi tai juurisolmu pysyy läsnä koko ajan.
- On vasen 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.
- Binaarinen hakupuu helpottaa ensisijaisia toimintoja, kuten hakua, lisäämistä ja poistamista.
- Poista monimutkaisimmalla on useita tapauksia, esimerkiksi solmu, jolla ei ole lasta, solmu, jossa on yksi lapsi, ja solmu, jossa on kaksi lasta.
- Algoritmia käytetään todellisissa ratkaisuissa, kuten peleissä, automaattisen täydennyksen tiedoissa ja grafiikoissa.