Binaarihakupuu - jäsennelty tietokanta, joka sisältää solmuja, kaksi linkkiä muihin solmuihin, oikealle ja vasemmalle. Solmut ovat luokan objekti, jolla on dataa, ja NULL on merkki, joka merkitsee puun lopun.
Sitä kutsutaan usein BST:ksi, jolla on erityinen ominaisuus: juuria suuremmat solmut sijaitsevat sen oikealla puolella ja pienemmät vasemmalla.
Yleinen teoria ja terminologia
Binäärihakupuussa jokainen solmu, juurta lukuun ottamatta, on yhdistetty solmusta toiseen suunnatulla reunalla, jota kutsutaan emopääksi. Jokainen niistä voidaan yhdistää mieliv altaiseen määrään solmuja, joita kutsutaan lapsiksi. Solmuja, joissa ei ole "lapsia", kutsutaan lehdiksi (ulkosolmuiksi). Elementtejä, jotka eivät ole lehtiä, kutsutaan sisäisiksi. Solmut, joilla on sama vanhempi, ovat sisaruksia. Ylintä solmua kutsutaan juuriksi. Määritä BST:ssä jokaiselle solmulle elementti ja varmista, että niille on asetettu erityinen ominaisuus.
Puun terminologia:
- Solmun syvyys on sen reunojen määrä, joka määritellään juuresta siihen.
- Solmun korkeus on siitä syvimpään lehtiin määritettyjen reunojen lukumäärä.
- Puun korkeus määräytyy juuren korkeuden mukaan.
- Binaarihakupuu on erityinen muotoilu, se tarjoaa parhaan korkeuden ja solmumäärän suhteen.
- Korkeus h ja N solmua enintään O (log N).
Voit todistaa tämän helposti laskemalla kunkin tason solmut juuresta alkaen olettaen, että se sisältää eniten niitä: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Tämän ratkaiseminen h:lle antaa h=O (log n).
Puun edut:
- Ota huomioon tietojen rakenteelliset suhteet.
- Käytetään edustamaan hierarkioita.
- Varmista tehokas asennus ja haku.
- Puut ovat erittäin joustavia tietoja, joiden avulla voit siirtää alipuita pienellä vaivalla.
Hakutapa
Yleensä määrittääksesi, onko arvo BST:ssä, käynnistä binäärihakupuu sen juuresta ja määritä, täyttääkö se vaatimukset:
- ole juurella;
- ole juuren vasemmassa alipuussa;
- juuren oikeassa alipuussa.
Jos mikään perusrekisteri ei täyty, suoritetaan rekursiivinen haku vastaavasta alipuusta. Itse asiassa on kaksi perusvaihtoehtoa:
- Puu on tyhjä - palauta false.
- Arvo on juurisolmussa - palauta tosi.
Tulee huomioida, että binäärihakupuu, jolla on kehitetty skeema, alkaa aina etsiä polkua juuresta lehteen. Pahimmassa tapauksessa se menee lehtiin asti. Siksi pahin aika on verrannollinen pisimmän polun pituuteen juuresta lehteen, joka on puun korkeus. Yleensä tämä on silloin, kun sinun on tiedettävä, kuinka kauan etsiminen kestää puuhun tallennettujen arvojen lukumäärän funktiona.
Toisin sanoen BST:n solmujen lukumäärän ja puun korkeuden välillä on suhde sen "muodon" mukaan. Pahimmassa tapauksessa solmuilla on vain yksi lapsi, ja tasapainotettu binäärihakupuu on olennaisesti linkitetty lista. Esimerkki:
50
/
10
15
30
/
20
Tässä puussa on 5 solmua ja korkeus=5. Arvojen löytäminen alueelta 16-19 ja 21-29 vaatii seuraavan polun juuresta lehteen (arvon 20 sisältävä solmu), ts., se vie aikaa suhteessa solmujen määrään. Parhaimmillaan heillä kaikilla on 2 lasta ja lehdet sijaitsevat samalla syvyydellä.
Tässä binäärihakupuussa on 7 solmua ja korkeus=3. Yleensä tällaisen puun (täyspuun) korkeus on noin log 2 (N), missä N on puun solmujen lukumäärä. Log 2:n (N) arvo on kuinka monta kertaa (2) N voidaan jakaa ennen kuin nolla saavutetaan.
Yhteenveto: Huonoin aika, joka tarvitaan hakuun BST:ssä, on O (puun korkeus). Huonoin tapaus "lineaarinen" puu on O(N), missä N on puun solmujen lukumäärä. Parhaimmillaan "täydellinen" puu on O(log N).
BST-binäärilisäys
Mietitään, missä pitäisi ollauusi solmu sijaitsee BST:ssä, sinun on ymmärrettävä logiikka, se on sijoitettava sinne, missä käyttäjä löytää sen. Lisäksi sinun tulee muistaa säännöt:
- Kaksoiskappaleet eivät ole sallittuja, arvon kaksoiskappaleen lisääminen aiheuttaa poikkeuksen.
- Julkinen lisäysmenetelmä käyttää auttaja-rekursiivista "auttaja"-menetelmää todelliseen lisäämiseen.
- Uuden arvon sisältävä solmu lisätään aina lehtinä BST:hen.
- Julkinen lisäysmenetelmä palauttaa void-menetelmän, mutta apumenetelmä palauttaa BST-solmun. Se tekee tämän käsitelläkseen tapausta, jossa sille välitetty solmu on tyhjä.
Yleensä apumenetelmä osoittaa, että jos alkuperäinen binäärihakupuu on tyhjä, tuloksena on puu, jossa on yksi solmu. Muussa tapauksessa tulos on osoitin samaan solmuun, joka välitettiin argumenttina.
Poistaminen binäärialgoritmissa
Kuten voit odottaa, elementin poistaminen edellyttää poistettavan arvon sisältävän solmun löytämistä. Tässä koodissa on useita asioita:
- BST käyttää auttajaa, ylikuormitettua poistomenetelmää. Jos etsimäsi elementti ei ole puussa, apumenetelmää kutsutaan lopulta n==null. Tätä ei pidetä virheenä, puu ei yksinkertaisesti muutu tässä tapauksessa. Poista-apumenetelmä palauttaa arvon - osoittimen päivitettyyn puuhun.
- Kun lehti poistetaan, binäärihakupuusta poisto asettaa sen vanhemman vastaavan lapsiosoittimen nollaksi tai juuren nollaksi, jos poistettava onsolmu on juuri eikä sillä ole lapsia.
- Huomaa, että poistokutsun on oltava jokin seuraavista: root=delete (juuri, avain), n.setLeft (delete (n.getLeft (), avain)), n.setRight (delete(n. getRight(), avain)). Siten kaikissa kolmessa tapauksessa on oikein, että poistomenetelmä palauttaa yksinkertaisesti nollan.
- Kun poistettavan arvon sisältävän solmun haku onnistuu, on kolme vaihtoehtoa: poistettava solmu on lehti (ei lapsia), poistettavalla solmulla on yksi lapsi, sillä on kaksi lapset.
- Kun poistettavalla solmulla on yksi lapsi, voit yksinkertaisesti korvata sen lapsella ja palauttaa osoittimen lapseen.
- Jos poistettavalla solmulla on nolla tai 1 lapsia, poistomenetelmä "seuraa polkua" juuresta kyseiseen solmuun. Joten pahin aika on verrannollinen puun korkeuteen sekä haussa että lisäyksessä.
Jos poistettavalla solmulla on kaksi lasta, suoritetaan seuraavat vaiheet:
- Etsi poistettava solmu seuraamalla polkua juuresta siihen.
- Etsi v:n pienin arvo oikeasta alipuusta jatkamalla polkua lehtiin.
- Poista rekursiivisesti v:n arvo, seuraa samaa polkua kuin vaiheessa 2.
- Siksi, pahimmassa tapauksessa polku juuresta lehtiin suoritetaan kahdesti.
Likkojen järjestys
Traversal on prosessi, joka vierailee puun kaikissa solmuissa. Koska C-binäärihakupuu on epälineaarinen tietorakenne, yksilöllistä läpikulkua ei ole. Esimerkiksi joskus useita läpikulkualgoritmejaryhmitelty kahteen tyyppiin:
- ristysyvyys;
- ensipassi.
On vain yksi leveysristeys - tason ohittaminen. Tämä läpikulku vierailee solmuissa tasolla alas ja vasemmalle, ylhäältä ja oikealle.
Syvyysristeyksiä on kolmea eri tyyppiä:
- Ennakkotilauksen hyväksyminen - ensin vanhemman ja sitten vasemman ja oikean lapsen luona.
- Järjestyksen syöttäminen - vasemman lapsen, sitten vanhemman ja oikean lapsen luona.
- Jälkitilauksen ohi - vasemman lapsen luona, sitten oikean lapsen luona, sitten vanhemman luona.
Esimerkki binäärihakupuun neljästä läpikäynnistä:
- Ennakkotilaus - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- Tilauksessa - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- Jälkitilaus - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- Tasojärjestys - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Kuva näyttää järjestyksen, jossa solmuissa vieraillaan. Numero 1 on ensimmäinen solmu tietyssä läpikäymisessä ja 7 on viimeinen solmu.
Nämä yleiset läpikäynnit voidaan esittää yhtenä algoritmina olettaen, että jokaisessa solmussa käydään kolme kertaa. Euler-kiertue on kävely binaaripuun ympäri, jossa jokaista reunaa käsitellään seinänä, jota käyttäjä ei voi ylittää. Tässä kävelyssä jokaisessa solmussa käydään joko vasemmalla, alapuolella tai oikealla. Euler-kierros, joka vierailee vasemmalla olevissa solmuissa, ohittaa prepositiot. Kun alla olevissa solmuissa käydään, ne kulkevat järjestyksessä. Ja kun oikeanpuoleisissa solmuissa käydään - hankivaiheittainen ohitus.
Navigointi ja virheenkorjaus
Helpottaaksesi puussa navigoimista luomalla toimintoja, jotka tarkistavat ensin, ovatko ne vasen vai oikea lapsi. Solmun paikan muuttaminen edellyttää, että pääsolmun osoitin on helposti saatavilla. Puun oikea toteuttaminen on erittäin vaikeaa, joten sinun on tiedettävä ja käytettävä virheenkorjausprosesseja. Binäärihakupuussa toteutuksella on usein osoittimia, jotka eivät varsinaisesti osoita kulkusuuntaa.
Tämän kaiken selvittämiseksi käytetään toimintoa, joka tarkistaa, voiko puu olla oikea, ja auttaa löytämään monia virheitä. Se esimerkiksi tarkistaa, onko pääsolmu lapsisolmu. Assert(is_wellformed(root)) -toiminnolla monet virheet voidaan havaita ennenaikaisesti. Käyttämällä paria annettua keskeytyspistettä tässä funktiossa voit myös määrittää tarkalleen, mikä osoitin on väärässä.
Function Konsolenausgabe
Tämä toiminto huuhtelee koko puun konsoliin ja on siksi erittäin hyödyllinen. Järjestys, jossa puun tulostavoite suoritetaan:
- Tämän tekemiseksi sinun on ensin määritettävä, mitä tietoja solmun kautta lähetetään.
- Ja sinun on myös tiedettävä kuinka leveä ja korkea puu on, jotta voit ottaa huomioon jätettävän tilan määrän.
- Seuraavat funktiot laskevat nämä tiedot puulle ja jokaiselle alipuulle. Koska voit kirjoittaa konsoliin vain rivi riviltä, sinun on myös tulostettava puu rivi riviltä.
- Nyt tarvitsemme toisen tavan vetäytyäkoko puu, ei vain rivi riviltä.
- Dumppaustoiminnon avulla voit lukea puuta ja parantaa merkittävästi lähtöalgoritmia nopeuden suhteen.
Tätä toimintoa on kuitenkin vaikea käyttää suurissa puissa.
Kopioi rakentaja ja tuhoaja
Koska puu ei ole triviaali tietorakenne, on parempi toteuttaa kopiokonstruktori, tuhoaja ja osoitusoperaattori. Destruktori on helppo toteuttaa rekursiivisesti. Erittäin suurille puille se pystyy käsittelemään "kasan ylivuotoa". Tässä tapauksessa se muotoillaan iteratiivisesti. Ajatuksena on poistaa kaikista lehtien pienintä arvoa edustava lehti, joten se on puun vasemmalla puolella. Ensimmäisten lehtien leikkaaminen luo uusia, ja puu kutistuu, kunnes se lopulta lakkaa olemasta.
Kopiokonstruktori voidaan toteuttaa myös rekursiivisesti, mutta ole varovainen, jos poikkeus tehdään. Muuten puusta tulee nopeasti hämmentävä ja virhe altis. Tästä syystä iteratiivista versiota suositellaan. Ajatuksena on käydä vanhan ja uuden puun läpi, kuten tekisit tuhoajassa, kloonaamalla kaikki solmut, jotka ovat vanhassa puussa, mutta eivät uusia.
Tällä menetelmällä binäärihakupuun toteutus on aina hyvässä tilassa ja tuhoaja voi poistaa sen jopa epätäydellisenä. Jos tapahtuu poikkeus, sinun tarvitsee vain neuvoa tuhoaja poistamaan puolivalmis puu. toimeksiantooperaattorivoidaan helposti toteuttaa Copy & Swap -toiminnolla.
Binaarihakupuun luominen
Optimaaliset binäärihakupuut ovat uskomattoman tehokkaita, jos niitä hallinnoidaan oikein. Joitakin sääntöjä binäärihakupuille:
- Yläsolmussa on enintään 2 alisolmua.
- Vasen lapsisolmu on aina pienempi kuin yläsolmu.
- Kelvollinen lapsisolmu on aina suurempi tai yhtä suuri kuin yläsolmu.
Matriisi, jota käytetään binäärihakupuun rakentamiseen:
- Peruskokonaislukutaulukko, jossa on seitsemän arvoa lajittelemattomassa järjestyksessä.
- Matriisin ensimmäinen arvo on 10, joten ensimmäinen askel puun rakentamisessa on luoda 10 juurisolmu, kuten tässä näkyy.
- Juurisolmujoukon kanssa kaikki muut arvot ovat tämän solmun lapsia. Sääntöihin viitaten, ensimmäinen askel 7:n lisäämiseksi puuhun on verrata sitä juurisolmuun.
- Jos arvo 7 on pienempi kuin 10, siitä tulee vasen lapsisolmu.
- Jos arvo 7 on suurempi tai yhtä suuri kuin 10, se siirtyy oikealle. Koska 7:n tiedetään olevan pienempi kuin 10, se on nimetty vasemmaksi lapsisolmuksi.
- Suorita vertailuja rekursiivisesti jokaiselle elementille.
- Noudata samaa kaavaa, suorita sama vertailu taulukon 14. arvoon.
- Vertaamalla arvoa 14 juurisolmuun 10, tietäen, että 14 on oikea lapsi.
- Kävelemme taulukon läpi,tule 20.
- Aloita vertaamalla taulukkoa 10:een sen mukaan, kumpi on suurempi. Joten siirry oikealle ja vertaa sitä vuoteen 14, hän on yli 14, eikä hänellä ole lapsia oikealla.
- Nyt on arvo 1. Noudattaen samaa kaavaa kuin muutkin arvot, vertaa 1:tä 10:een siirtymällä vasemmalle ja vertaamalla 7:ään ja lopuksi 7. solmun vasempaan lapsiin.
- Jos arvo on 5, vertaa sitä 10:een. Koska 5 on pienempi kuin 10, siirry vasemmalle ja vertaa sitä arvoon 7.
- Tiedäksesi, että 5 on pienempi kuin 7, jatka puuta alaspäin ja vertaa viittä arvoon 1.
- Jos 1:llä ei ole lapsia ja 5 on suurempi kuin 1, niin 5 on kelvollinen 1 solmun lapsi.
- Lisää lopuksi arvo 8 puuhun.
- Kun 8 on alle 10, siirrä sitä vasemmalle ja vertaa sitä 7:ään, 8 on suurempi kuin 7, joten siirrä sitä oikealle ja viimeistele puu, jolloin 8 on oikea 7:n lapsi.
Optimaisten binäärihakupuiden yksinkertaisen eleganssin hankkiminen ja arviointi. Kuten monet ohjelmoinnin aiheet, binäärihakupuiden teho tulee niiden kyvystä jakaa tiedot pieniksi, toisiinsa liittyviksi komponenteiksi. Tästä lähtien voit työskennellä koko tietojoukon kanssa järjestelmällisesti.
Mahdolliset binaarihaun ongelmat
Binaarihakupuut ovat mahtavia, mutta muutama varoitus on pidettävä mielessä. Ne ovat yleensä tehokkaita vain, jos ne ovat tasapainossa. Tasapainoinen puu on puu, jossapuun minkä tahansa solmun alipuiden korkeuksien ero on enintään yksi. Katsotaanpa esimerkkiä, joka saattaa auttaa selventämään sääntöjä. Oletetaan, että taulukko alkaa lajiteltavana.
Jos yrität ajaa binäärihakupuualgoritmia tässä puussa, se toimii täsmälleen ikään kuin se vain iteroisi taulukkoa, kunnes haluttu arvo löytyy. Binaarihaun voima on kyky suodattaa nopeasti pois ei-toivotut arvot. Kun puu ei ole tasapainossa, se ei tarjoa samoja etuja kuin tasapainoinen puu.
On erittäin tärkeää tarkastella tietoja, joita käyttäjä käsittelee luodessaan binaarihakupuuta. Voit integroida rutiineja, kuten taulukoiden satunnaistamisen, ennen kuin otat käyttöön kokonaislukujen binaarihakupuun sen tasapainottamiseksi.
Binaarihaun laskentaesimerkkejä
Meidän on määritettävä, millainen puu syntyy, jos 25 lisätään seuraavaan binäärihakupuuhun:
10
/
/
5 15
/ /
/ /
2 12 20
Kun lisätään x puuhun T, joka ei vielä sisällä x:tä, avain x sijoitetaan aina uuteen lehtiin. Tämän yhteydessä uusi puu näyttää tältä:
10
/
/
5 15
/ /
/ /
2 12 20
25
Millaisen puun saisit, jos lisäisit 7 seuraavaan binäärihakupuuhun?
10
/
/
5 15
/ /
/ /
2 12 20
Vastaus:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Binaarihakupuuta voidaan käyttää minkä tahansa objektin tallentamiseen. Binaarihakupuun käytön etuna linkitetyn luettelon sijasta on, että jos puu on kohtuullisen tasapainoinen ja enemmän kuin "täysi" kuin "lineaarinen", lisäys-, haku- ja kaikki poistotoiminnot voidaan toteuttaa suoritettavaksi O(log N) aika.
