Mikä on binäärihakupuu?

Binäärihakupuu on yksi erilaisista tietorakenteista, jotka auttavat meitä järjestämään ja lajittelemaan tietoja. Se on tehokas tapa tallentaa tietoja hierarkiassa ja erittäin joustava.

Tässä artikkelissa tarkastellaan lähemmin sen toimintaa – sekä sen ominaisuuksia ja sovelluksia.

Mikä on binäärihakupuu?

Binäärihakupuu on tietorakenne, joka koostuu solmuista – samanlainen kuin linkitetyt luettelot. Solmuja voi olla kahden tyyppisiä: vanhempi ja lapsi. Juurisolmu on rakenteen alkupiste, joka haarautuu kahdeksi lapsisolmuksi, joita kutsutaan vasemmaksi ja oikeaksi solmuksi.

Jokaiseen solmuun voi viitata vain sen vanhempi, ja voimme kulkea puun solmujen läpi suunnasta riippuen. Binäärihakupuulla on kolme pääominaisuutta:

1. Vasen solmu on pienempi kuin sen emo.
2. Oikea solmu on suurempi kuin sen emo.
3. Vasemman ja oikean alipuun on oltava binäärihakupuita.

Täydellinen binäärihakupuu saavutetaan, kun kaikki tasot on täytetty, ja jokaisella solmulla on vasen ja oikea lapsisolmu.

Aiheeseen liittyvä: Tietotiedekirjastot Pythonille jokaisen datatieteilijän tulisi käyttää

Binaarihakupuun perustoiminnot

Nyt sinulla on parempi käsitys siitä, mitä binäärihakupuu on, voimme tarkastella sen perustoimintoja alla.

1. Hakutoiminto

Haun avulla voimme paikantaa tietyn arvon puussa. Voimme käyttää kahdenlaisia ​​hakuja: leveyshaku (BFS) ja syvyyshaku (DFS). Breadth-first-haku on hakualgoritmi, joka alkaa juurisolmusta ja kulkee vaakasuunnassa puolelta toiselle, kunnes tavoite löytyy. Jokaisessa solmussa käydään kerran tämän haun aikana.

Syvyys-ensimmäinen haku sen sijaan kulkee puun poikki pystysuunnassa - alkaen juurisolmusta ja jatkaen yhtä oksaa alaspäin. Jos tavoite löytyy, operaatio päättyy. Mutta jos ei, se ja etsii muut solmut.

2. Lisää toiminta

Lisäystoiminto käyttää hakutoimintoa määrittääkseen paikan, johon uusi solmu tulee lisätä. Prosessi alkaa juurisolmusta ja haku alkaa, kunnes kohde saavutetaan. Lisäyksen yhteydessä on otettava huomioon kolme tapausta.

• Tapaus 1: Kun solmua ei ole. Lisättävästä solmusta tulee juurisolmu.

• Tapaus 2: Ei ole lapsia. Tässä tapauksessa solmua verrataan juurisolmuun. Jos se on suurempi, siitä tulee oikea lapsi; muuten siitä tulee vasen lapsi.

• Tapaus 3: Kun juuri ja sen lapset ovat läsnä. Uutta solmua verrataan jokaiseen sen polulla olevaan solmuun sen määrittämiseksi, missä solmussa se vierailee seuraavaksi. Jos solmu on suurempi kuin juurisolmu, se kulkee alas oikeaa alipuuta tai muuten vasenta. Vastaavasti kullakin tasolla tehdään vertailuja sen määrittämiseksi, meneekö se oikealle vai vasemmalle, kunnes se saapuu määränpäähänsä.

3. Poista-toiminto

Poista-toimintoa käytetään tietyn solmun poistamiseen puusta. Poistamista pidetään hankalana, koska solmun poistamisen jälkeen puu on järjestettävä uudelleen vastaavasti. On kolme päätapausta, jotka on otettava huomioon:

• Tapaus 1: Lehtisolmun poistaminen. Lehtisolmu on solmu, jolla ei ole lapsia. Tämä on helpoin poistaa, koska se ei vaikuta muihin solmuihin; yksinkertaisesti kuljemme puun poikki, kunnes saavutamme sen ja poistamme sen.

• Tapaus 2: Solmun poistaminen yhden lapsen kanssa. Yhdellä solmulla varustetun vanhemman poistaminen johtaa siihen, että lapsi ottaa asemansa, ja kaikki seuraavat solmut siirtyvät tason ylöspäin. Osapuiden rakenteeseen ei tule muutoksia.

• Tapaus 3: Solmun poistaminen, jossa on kaksi lasta. Kun meidän on poistettava solmu, jossa on kaksi lasta, meidän on ensin löydettävä seuraava solmu, joka voi ottaa asemansa. Kaksi solmua voi korvata poistetun solmun, järjestyksen seuraajan tai edeltäjän. Järjestyksen seuraaja on oikean alipuun vasemmanpuoleisin lapsi, ja järjestyksen edeltäjä on vasemman alipuun oikeanpuoleisin lapsi. Kopioimme seuraajan/edeltäjän sisällön solmuun ja poistamme järjestyksen seuraajan/edeltäjän.

Aiheeseen liittyvä: Tietorakenteiden rakentaminen JavaScriptin ES6-luokilla

Kuinka kulkea binäärihakupuussa

Traversal on prosessi, jonka kautta navigoimme binäärihakupuussa. Se tehdään tietyn kohteen paikallistamiseksi tai puun ääriviivojen tulostamiseksi. Aloitamme aina juurisolmusta ja meidän on seurattava reunoja päästäksemme muihin solmuihin. Jokaista solmua tulee pitää alipuuna, ja prosessia toistetaan, kunnes kaikki solmut on käyty.

• Tilauksen läpikulku: Liikkuminen järjestyksessä tuottaa kartan nousevassa järjestyksessä. Tällä menetelmällä aloitamme vasemmasta alipuusta ja jatkamme juureen ja oikeaan alipuuhun.

• Ennakkotilauskierros: Tässä menetelmässä käydään ensin juurisolmussa, sen jälkeen vasemmassa alipuussa ja oikeassa alipuussa.

• Tilauksen jälkeinen läpikäynti: Tämä läpikulku sisältää vierailun juurisolmussa viimeisenä. Aloitamme vasemmasta alipuusta, sitten oikeasta alipuusta ja sitten juurisolmusta.

Reaalimaailman sovellukset

Joten kuinka hyödynnämme binäärihakupuualgoritmeja? Kuten voidaan olettaa, ne ovat erittäin tehokkaita etsimisessä ja lajittelussa. Binääripuiden suurin vahvuus on niiden organisoitu rakenne. Se mahdollistaa haun suorittamisen huomattavalla nopeudella vähentämällä analysoitavan tiedon määrää puoleen kulkua kohti.

Binaarihakupuut mahdollistavat dynaamisesti muuttuvan tietojoukon tehokkaan ylläpitämisen järjestäytyneessä muodossa. Ne ovat erittäin hyödyllisiä sovelluksille, joissa tietoja lisätään ja poistetaan usein. Videopelimoottorit käyttävät puihin perustuvaa algoritmia, joka tunnetaan nimellä binääritilaosio, auttaakseen objektien järjestämisessä. Microsoft Excel ja useimmat taulukkolaskentaohjelmistot käyttävät binääripuita perustietorakenteena.

Saatat yllättyä tietää, että morsekoodi käyttää binaarihakupuuta tietojen koodaamiseen. Toinen merkittävä syy binäärihakupuulle ovat niin hyödyllisiä, ovat niiden useat muunnelmat. Niiden joustavuus on johtanut lukuisiin muunnelmien luomiseen kaikenlaisten ongelmien ratkaisemiseksi. Oikein käytettynä binaarihakupuut ovat suuri voimavara.

Binäärihakupuut: täydellinen lähtökohta

Yksi tärkeimmistä tavoista mitata insinöörin asiantuntemusta on tietorakenteiden tuntemus ja soveltaminen. Tietorakenteet ovat hyödyllisiä ja voivat auttaa luomaan tehokkaamman järjestelmän. Binaarihakupuut ovat loistava johdatus tietorakenteisiin kaikille aloittaville kehittäjille.

15 JavaScript-taulukkomenetelmää, jotka sinun pitäisi hallita tänään

Haluatko ymmärtää JavaScript-taulukoita, mutta et pääse niihin käsiksi? Katso ohjeita JavaScript-taulukkoesimerkeistämme.

Lue Seuraava

Kirjailijasta