Ero B-puun ja binaaripuun välillä
Sisältö
- Vertailutaulukko
- Määritelmä B-tree
- M-luokan B-puun ominaisuudet
- Määritelmä Binaarinen puu
- Läpinäkyvät tekniikat
- johtopäätös
B-puu ja binaaripuu ovat epälineaarisen tietorakenteen tyyppejä. Vaikka termit näyttävät olevan samanlaisia, mutta ovat erilaisia kaikilta osin. Binaarista puuta käytetään, kun tietueet tai tiedot tallennetaan RAM-muistiin levyn sijasta, koska RAM-muistin käyttönopeus on paljon suurempi kuin levyn. Toisaalta B-puuta käytetään, kun dataa tallennetaan levylle. Se lyhentää pääsyaikaa vähentämällä puun korkeutta ja lisäämällä oksat solmussa.
Toinen ero B-puun ja binaaripuun välillä on, että B-puussa on oltava kaikki lapsisolmut samalla tasolla, kun taas binaaripuussa ei ole tällaista rajoitusta. Binaaripuussa voi olla enintään 2 alapuuta tai solmua, kun taas B-puussa ei voi olla M: tä alapuuta tai solmua, joissa M on B-puun järjestys.
- Vertailutaulukko
- Määritelmä
- Keskeiset erot
- johtopäätös
Vertailutaulukko
| Vertailun perusteet | B-tree | Binaarinen puu |
|---|---|---|
| Olennainen rajoitus | Solmulla voi olla enimmillään M lukumäärä lapsisolmuja (missä M on puun järjestys). | Solmulla voi olla korkeintaan 2 lukumäärä alijäämiä. |
| käytetty | Sitä käytetään, kun tietoja on tallennettu levylle. | Sitä käytetään, kun tietueet ja tiedot tallennetaan RAM-muistiin. |
| Puun korkeus | HirsiM N (missä m on M-suuntaisen puun järjestys) | Hirsi2 N |
| hakemus | Koodin indeksointidatarakenne monissa DBMS-järjestelmissä. | Koodin optimointi, Huffman-koodaus jne. |
Määritelmä B-tree
B-puu on tasapainoinen M-suuntainen puu, jota kutsutaan myös tasapainoiseksi lajittelupuuksi. Se on samanlainen kuin binaarinen hakupuu, jossa solmut on järjestetty sisääntulon läpikulun perusteella. B-puun tilan monimutkaisuus on O (n). Lisäys- ja poistoaikojen monimutkaisuus on O (log n).
On tiettyjä ehtoja, joiden on oltava totta B-puulle:
- Puun korkeuden on oltava mahdollisimman pieni.
- Puun lehtien yläpuolella ei saa olla tyhjiä alapuita.
- Puun lehtien on oltava samalla tasolla.
- Kaikissa solmuissa tulisi olla vähiten lapsia lukuun ottamatta poistosolmuja.
M-luokan B-puun ominaisuudet
- Jokaisessa solmussa voi olla enimmäismäärä M lasten lukumäärää ja minimi M / 2 lasten lukumäärää tai mikä tahansa lukumäärä 2: sta maksimiin.
- Jokaisella solmulla on yksi avain vähemmän kuin lapsilla, joiden enimmäismäärä on M-1.
- Näppäinten järjestely on tietyssä järjestyksessä solmujen sisällä. Kaikkia näppäimen alaosassa olevia näppäimiä, jotka ovat näppäimen vasemmalla puolella, ovat avaimen edeltäjät, ja avaimen oikealla puolella olevia avaimia kutsutaan seuraajiksi.
- Kun koko solmu on asetettu, puu hajoaa kahteen osaan, ja mediaaniarvoinen avain työnnetään emo-solmuun.
- Yhdistäminen tapahtuu, kun solmut poistetaan.
Määritelmä Binaarinen puu
Binaarinen puu on puurakenne, jolla voi olla korkeintaan kaksi osoitinta lapsisolmuilleen. Se tarkoittaa, että korkein aste, joka solmulla voi olla, on 2 ja siellä voi olla myös nolla tai yhden asteen solmu.
Binaaripuusta on tiettyjä variantteja, kuten tiukasti binaaripuu, täydellinen binaaripuu, laajennettu binaaripuu jne.
- Tiukasti binaarinen puu on puu, jossa jokaisella ei-päätelaitteella on oltava vasen ala- ja oikea alaosa.
- Puuta kutsutaan täydelliseksi binaaripuuksi, kun se täyttää 2: n ehdon minä solmut jokaisella tasolla, missä i on taso.
- Kierteinen binaari on binaarinen puu, joka koostuu joko 0 solmujen määrästä tai 2 lukumäärästä solmuja.
Läpinäkyvät tekniikat
Puun kulku on yksi yleisimmistä puun tietorakenteelle suoritettavista operaatioista, jossa jokainen solmu vieraili tarkalleen kerran systemaattisesti.
- Inorder - Tässä puiden poikittaisessa vasemmassa alaosaa käydään rekursiivisesti, sitten juurisolmua käydään ja viimeisessä oikeassa alaosaa käydään.
- Preorer - Tämän puun läpi kulkeva juurisolmu käydään alussa, sitten vasemmassa alareunassa ja viimeisessä oikeassa alapuussa.
- Postorder - Tämä tekniikka vierailee vasemmassa alareunassa, sitten oikeassa alaryhmässä ja viimeisessä juurisolmussa.
- B-puussa enimmäismäärä lapsisolmuja, joita ei-päätelaitteella voi olla, on M, missä M on B-puun järjestys. Toisaalta, binaaripuussa voi olla korkeintaan kaksi alapuuta tai lapsisolmua.
- B-puuta käytetään, kun dataa tallennetaan levylle, kun taas binaarista puuta käytetään, kun dataa tallennetaan pikamuistiin, kuten RAM.
- Toinen sovellusalue B-puulle on koodin indeksointi tietorakenne DBMS: ssä, sen sijaan binaarista puuta käytetään koodin optimoinnissa, huffman-koodauksessa jne.
- B-puun enimmäiskorkeus on lokiMN (M on puiden järjestys). Binäärisen puun enimmäiskorkeus on log2N (N on solmujen lukumäärä ja emäs on 2, koska se on binaarinen).
johtopäätös
B-puuta käytetään binaarisen ja binaarisen hakupuun päällä. Tärkein syy tähän on muistihierarkia, jossa CPU on kytketty välimuistiin suuren kaistanleveyden kanavilla, kun CPU on kytketty levylle matalan kaistanleveyden kanavan kautta. Binaarista puuta käytetään, kun tietueet tallennetaan RAM-muistiin (pieni ja nopea) ja B-puuta, kun tietueita tallennetaan levylle (suuri ja hidas). Joten B-puun käyttö binaaripuun sijasta vähentää pääsyaikaa huomattavasti korkean haarautumiskertoimen ja puun korkeuden vuoksi.
