Avainero – binääripuu vs binäärihakupuu
Tietorakenne on systemaattinen tapa järjestää tiedot, jotta niitä voidaan käyttää tehokkaasti. Tietojen järjestämisen tietorakenteen avulla pitäisi lyhentää ajo- tai suoritusaikaa. Lisäksi tietorakenteen tulee vaatia vähimmäismäärä muistia. Joskus tiedot voidaan järjestää puurakenteeseen. Puu edustaa reunoilla yhdistettyä solmua. Ylin solmu on juuri. Jokaisessa solmussa voi olla enintään kaksi solmua. Ne tunnetaan lapsisolmuina. Pääsolmun vasemmalla puolella oleva solmu on vasen lapsisolmu, kun taas pääsolmun oikealla puolella oleva solmu on oikea solmu. Binary Tree ja Binary Search Tree ovat kaksi puutietorakennetta. Binääripuu on eräänlainen tietorakenne, jossa jokaisella pääsolmulla voi olla enintään kaksi alisolmua. Binäärihakupuu on binääripuu, jossa vasen aliosa sisältää vain solmuja, joiden arvot ovat pienempiä tai yhtä suuria kuin emosolmun, ja jossa oikea aliosa sisältää vain solmuja, joiden arvot ovat suurempia kuin yläsolmun arvot. Se on tärkein ero. Toisin kuin tietorakenteilla, kuten taulukoilla, binääripuulla ja binäärihakupuulla ei ole ylärajaa tietojen tallentamiselle.
Mikä on binääripuu?
Kun tiedot järjestetään puurakenteeseen, puun yläosassa olevaa solmua kutsutaan juurisolmuksi. Koko puulla voi olla vain yksi juuri. Jokaisella solmulla, paitsi juurisolmulla, on yksi reuna ylöspäin solmuun. Sitä kutsutaan pääsolmuksi. Pääkoodin alapuolella olevaa solmua kutsutaan sen alisolmuksi. Jokaisella pääsolmulla voi olla enintään kaksi alisolmua. Niitä kutsutaan vasemmaksi lapsisolmuksi ja oikeaksi lapsisolmuksi. Solmua, jossa ei ole lapsisolmua, kutsutaan lehtisolmuksi. Ei ole olemassa erityistä tapaa järjestää tietoja binääripuussa. Pääsolmusta jokaiseen solmuun on polku.
Kuva 01: Esimerkki binääripuusta
Yllä on esimerkki binääripuusta. Elementti 2 puun huipussa on juuri. Jokaisessa solmussa on enintään kaksi solmua. Jos puu sisältää silmukoita tai jos yksi solmu sisältää enemmän kuin kaksi solmua, sitä ei voida luokitella binääripuuksi. Solmusta toiseen siirtymiseen on aina yksi polku. Juurisolmun 2 lapsisolmut ovat 7 ja 5. On myös mahdollista, että solmulla ei ole solmuja. Mutta millään solmulla ei voi olla enempää kuin kaksi solmua. Juuren oikea elementti on 5. Tämä elementti 5 on lapsisolmun 9 yläsolmu. Solmuilla 4 ja 11 ei ole lapsielementtejä. Siksi ne ovat lehtisolmuja.
Binääripuuta käytetään tietojen tallentamiseen hierarkkisessa järjestyksessä. Se on samanlainen kuin tietokoneen tiedostorakenne. Tietorakenne, kuten taulukko, voi tallentaa tietyn määrän tietoa. Mutta binääripuussa solmujen lukumäärällä ei ole ylärajaa.
Mikä on binäärihakupuu?
Binäärihakupuu on binääripuutietorakenne. Kuten binääripuussa, myös binäärihakupuussa voi olla kaksi solmua. Jokaisella solmulla, paitsi juurisolmulla, on yksi reuna ylöspäin solmuun. Sitä kutsutaan pääsolmuksi. Annetun alapuolella olevaa solmua, joka on yhdistetty reunallaan alaspäin, kutsutaan sen lapsisolmuksi. Solmua, jossa ei ole lapsisolmua, kutsutaan lehtisolmuksi. Jokaisessa pääsolmussa voi olla enintään kaksi solmua. On lapsisolmuja, jotka viittaavat vasempaan lapsisolmuun ja oikeaan lapsisolmuun. Ylintä elementtiä kutsutaan juurisolmuksi. Vasen lapsi sisältää vain solmuja, joiden arvot ovat pienempiä tai yhtä suuria kuin yläsolmu. Oikea lapsi sisältää vain solmuja, joiden arvot ovat suurempia tai yhtä suuria kuin yläsolmu.
Kuva 02: Esimerkki binäärihakupuusta
Elementti 8 on ylin elementti. Siksi se on juurisolmu. Jos 3 on yläsolmu, 1 ja 6 ovat lapsisolmuja. 1 on vasen lapsisolmu, kun taas 6 on oikea lapsisolmu. Vasen lapsi sisältää arvoja, jotka ovat pienempiä tai yhtä suuria kuin yläsolmu. Kun 3 on pääsolmu, vasemmalla puolella tulee olla elementti, joka on pienempi tai yhtä suuri kuin 3. Tässä esimerkissä se on 1. Oikea lapsi sisältää vain solmuja, joiden arvot ovat suurempia kuin pääsolmun. Kun 3 on pääsolmu, oikean alisolmun tulee olla suurempi kuin 3. Tässä esimerkissä se on 6. Samoin on olemassa tietty järjestys järjestää jokainen tietoelementti binäärihakupuuksi. Se on tietorakenne, joka tarjoaa tehokkaan tavan lajitella, hakea ja etsiä tietoja.
Mitä yhtäläisyyksiä binääripuulla ja binäärihakupuulla on?
- Sekä binääripuu että binäärihakupuu ovat hierarkkisia tietorakenteita.
- Sekä binääripuulla että binäärihakupuulla on juuri.
- Sekä binääripuussa että binäärihakupuussa voi olla enintään kaksi alisolmua.
Mitä eroa on binääripuulla ja binäärihakupuulla?
Binaaripuu vs binäärihakupuu |
|
| Binääripuu on eräänlainen tietorakenne, jossa jokaisella pääsolmulla voi olla enintään kaksi alisolmua. | Binäärihakupuu on binääripuu, jossa vasemmanpuoleinen alataso sisältää vain solmuja, joiden arvot ovat pienempiä tai yhtä suuria kuin emosolmu, ja jossa oikea aliosa sisältää vain solmuja, joiden arvot ovat suurempia kuin yläsolmu. |
| Tietojen järjestelyjärjestys | |
| Binääripuulla ei ole tiettyä järjestystä tietoelementtien järjestämiseksi. | Binäärihakupuulla on tietty järjestys tietoelementtien järjestämiseksi. |
| Käyttö | |
| Binääripuuta käytetään tehokkaana tiedonhakuun puurakenteessa. | Binaarihakupuuta käytetään tietojen lisäämiseen, poistamiseen ja etsimiseen. |
Yhteenveto – Binääripuu vs binäärihakupuu
Tietorakenne on tapa järjestää tietoja. Joskus tiedot voidaan järjestää puurakenteeseen. Kaksi niistä on binääripuu ja binäärihakupuu. Tässä artikkelissa käsiteltiin eroa binääripuun ja binäärihakupuun välillä. Binääripuu on eräänlainen tietorakenne, jossa jokaisella pääsolmulla voi olla enintään kaksi alisolmua. Binäärihakupuu on binääripuu, jossa vasen aliosa sisältää vain solmuja, joiden arvot ovat pienempiä tai yhtä suuria kuin emosolmu, ja jossa oikea aliosa sisältää vain solmuja, joiden arvot ovat suurempia kuin yläsolmu.
Lataa PDF Binary Tree vs Binary Search Tree
Voit ladata tämän artikkelin PDF-version ja käyttää sitä offline-tarkoituksiin lainaushuomautuksen mukaisesti. Lataa PDF-versio tästä: Ero binaaripuun ja binaarihakupuun välillä
