Ensinnäkin ymmärrämme binääripuu ja binäärihakupuu erikseen, ja sitten tarkastellaan binääripuun ja binäärihakupuun välisiä eroja.
Mikä on binaaripuu?
A Binäärinen puu on
Binääripuu voidaan esittää seuraavasti:
Yllä olevassa kuvassa voimme havaita, että jokainen solmu sisältää enintään 2 lasta. Jos jokin solmu ei sisällä vasenta tai oikeaa aliosaa, osoittimen arvo kyseiseen lapseen nähden olisi NULL.
Binääripuussa käytetyt perusterminologiat ovat:
Binääripuussa on yksi puu, joka tunnetaan nimellä a täydellinen binääripuu . Se on a puu, jossa kaikissa sisäisissä solmuissa on oltava kaksi solmua ja kaikkien lehtien solmujen on oltava samalla syvyydellä. Täydellisen binääripuun tapauksessa binääripuussa olevien solmujen kokonaismäärä voidaan laskea käyttämällä seuraavaa yhtälöä:
n = 2m+1-1
missä n on solmujen lukumäärä, m on solmun syvyys.
Mikä on binäärihakupuu?
A Binäärihakupuu on puu, joka noudattaa jotakin järjestystä elementtien järjestämisessä, kun taas binääripuu ei seuraa mitään järjestystä. Binaarihakupuussa vasemman solmun arvon on oltava pienempi kuin pääsolmun ja oikean solmun arvon on oltava suurempi kuin pääsolmun.
Ymmärretään binäärihakupuun käsite esimerkkien avulla.
Yllä olevasta kuvasta voidaan havaita, että juurisolmun arvo on 15, mikä on suurempi kuin kaikkien vasemman alipuun solmujen arvo. Juurisolmun arvo on pienempi kuin oikeanpuoleisen alipuun kaikkien solmujen arvot. Nyt siirrymme juurisolmun vasempaan jälkeläiseen. 10 on suurempi kuin 8 ja pienempi kuin 12; se täyttää myös binaarihakupuun ominaisuuden. Nyt siirrymme juurisolmun oikeaan jälkeläiseen; arvo 20 on suurempi kuin 17 ja pienempi kuin 25; se myös täyttää binäärihakupuun ominaisuuden. Siksi voimme sanoa, että yllä oleva puu on binäärihakupuu.
Jos nyt muutamme yllä olevan binääripuun arvon 12 arvoon 16, meidän on selvitettävä, onko se edelleen binäärihakupuu vai ei.
Juurisolmun arvo on 15, joka on suurempi kuin 10 mutta pienempi kuin 16, joten se ei täytä binaarihakupuun ominaisuutta. Siksi se ei ole binäärihakupuu.
Toiminnot binaarihakupuussa
Voimme suorittaa lisäys-, poisto- ja hakutoimintoja binäärihakupuussa. Ymmärretään, kuinka haku suoritetaan binäärihaulla. Alla näkyy binääripuu, jolla meidän on suoritettava hakutoiminto:
Oletetaan, että meidän on etsittävä 10 yllä olevasta binääripuusta. Suorittaaksemme binäärihaun, otamme huomioon kaikki järjestetyssä taulukossa olevat kokonaisluvut. Ensin luomme täydellisen luettelon hakutilaan, ja kaikki numerot ovat hakutilassa. Hakuavaruus on merkitty kahdella osoittimella, eli alku ja loppu. Yllä olevan binääripuun taulukko voidaan esittää muodossa
Ensin lasketaan keskielementti ja verrataan keskimmäistä elementtiä etsittävään elementtiin. Keskielementti lasketaan käyttämällä n/2:ta. n:n arvo on 7; keskimmäinen elementti on siis 15. Keskielementti ei ole sama kuin haettu elementti, eli 10.
Huomautus: Jos etsittävä elementti on pienempi kuin keskielementti, haku suoritetaan vasemmalla puoliskolla; muussa tapauksessa haku suoritetaan oikealla puoliskolla. Tasa-arvon tapauksessa elementti löytyy.
Koska etsittävä elementti on pienempi kuin keskielementti, haku suoritetaan vasemmanpuoleisesta taulukosta. Nyt haku on puolitettu, kuten alla:
Vasemman taulukon keskielementti on 10, joka on yhtä suuri kuin haettu elementti.
Aika monimutkaisuus
Binäärihaussa on n elementtiä. Jos keskimmäinen elementti ei ole sama kuin haettu elementti, niin hakuavaruus pienennetään arvoon n/2 ja jatketaan hakuavaruuden pienentämistä n/2:lla, kunnes elementti löytyy. Jos siirrymme n:stä n/2:een n/4:ään ja niin edelleen, se vie log2n askelta.
Erot binaaripuun ja binaarihakupuun välillä
| Vertailun perusteita | Binäärinen puu | Binäärihakupuu |
|---|---|---|
| Määritelmä | Binääripuu on epälineaarinen tietorakenne, jossa solmulla voi olla korkeintaan kaksi lasta, eli solmulla voi olla 0, 1 tai enintään kaksi lasta. Binäärihakupuu on järjestetty binääripuu, jossa noudatetaan tiettyä järjestystä puun solmujen järjestämiseksi. | |
| Rakenne | Binääripuun rakenne on sellainen, että ensimmäinen tai ylin solmu tunnetaan juurisolmuna. Jokainen binaaripuun solmu sisältää vasemman ja oikean osoittimen. Vasen osoitin sisältää vasemman alipuun osoitteen, kun taas oikea osoitin oikean alipuun osoitteen. | Binäärihakupuu on yksi binääripuutyypeistä, jonka vasemman alipuun kaikkien solmujen arvo on pienempi tai yhtä suuri kuin juurisolmu ja kaikkien oikeanpuoleisen alipuun solmujen arvo on suurempi tai yhtä suuri kuin juurisolmun arvo. |
| Toiminnot | Toiminnot, jotka voidaan toteuttaa binääripuussa, ovat lisäys, poisto ja läpikulku. | Binäärihakupuut ovat lajiteltuja binääripuita, jotka tarjoavat nopean lisäyksen, poistamisen ja haun. Haut toteuttavat pääasiassa binaarihaun, koska kaikki avaimet on järjestetty lajiteltuun järjestykseen. |
| tyypit | Neljä binääripuutyyppiä ovat täysi binääripuu, täydellinen binääripuu, täydellinen binääripuu ja laajennettu binääripuu. | Binäärihakupuita on erilaisia, kuten AVL-puut, Splay-puut, Tango-puut jne. |