Toinen ero B-puun ja binaaripuun välillä on, että B-puussa on oltava kaikki sen lapsisolmut samalla tasolla, kun taas binääripuulla ei ole tällaista rajoitusta. Binääripuussa voi olla enintään 2 subtreesia tai solmuja, kun taas B-puussa voi olla M-osia alikokeista tai solmuista, joissa M on B-puun järjestys.
Vertailukaavio
| Vertailun perusteet | B-tree | Binary puu |
|---|---|---|
| Oleellinen rajoitus | Solmulla voi olla korkeintaan M lukumäärä lasten solmuja (missä M on puun järjestys). | Solmussa voi olla korkeintaan 2 alikantaa. |
| käytetty | Sitä käytetään, kun dataa tallennetaan levylle. | Sitä käytetään, kun tietueet ja tiedot tallennetaan RAM-muistiin. |
| Puun korkeus | log M N (jossa m on M-polun järjestys) | log 2 N |
| hakemus | Koodin indeksointitietorakenne monissa DBMS-järjestelmissä. | Koodin optimointi, Huffman-koodaus jne. |
Määritelmä B-puu
B-puu on tasapainoinen M-tie ja sitä kutsutaan myös tasapainotetuksi lajiksi. Se on samanlainen kuin binäärinen hakupuu, jossa solmut on järjestetty sisäisen liikkeen perusteella. B-puun avaruuden monimutkaisuus on O (n). Lisäys- ja poistoaikakompleksisuus on O (log n).
On olemassa tiettyjä ehtoja, joiden on täytettävä B-puu:
- Puun korkeuden on oltava mahdollisimman pieni.
- Puun lehtien yläpuolella ei saa olla mitään tyhjiä puita.
- Puun lehdet tulee tulla samalle tasolle.
- Kaikissa solmuissa pitäisi olla vähiten lapsia lukuun ottamatta lähdepisteitä.
M-järjestyksen B-puun ominaisuudet
- Jokaisella solmulla voi olla enimmäismäärä M-lapsia ja vähimmäismäärä M / 2-lapsia tai mikä tahansa numero 2: sta maksimiin.
- Jokaisella solmulla on yksi avain vähemmän kuin lapset, joilla on suurin M-1-näppäin.
- Näppäinten järjestely on tiettyyn järjestykseen solmuissa. Kaikki avaimen vasemmalla puolella olevat aliverkon avaimet ovat avaimen edeltäjiä, ja avaimen oikealla puolella olevia nimiä kutsutaan seuraajiksi.
- Täyden solmun sijoittamisen aikana puu jaetaan kahteen osaan ja avain, jonka mediaani-arvo on, lisätään vanhempaan solmuun.
- Yhdistäminen tapahtuu, kun solmut poistetaan.
Määritelmä Binary puu
Binaaripuu on puurakenne, jolla voi olla korkeintaan kaksi osoitetta sen lapsisolmuista. Se tarkoittaa, että korkein aste, jolla solmu voi olla, on 2 ja myös nollapiste tai yhden asteen solmu.
On olemassa tiettyjä binaaripuun variantteja, kuten tiukasti binäärinen puu, täydellinen binaaripuu, laajennettu binaaripuu jne.
- Tiukasti binäärinen puu on puu, jossa jokaisella ei-päätelaitteella olevalla solmulla on oltava vasen osa- ja oikea osa.
- Puuta kutsutaan täydelliseksi binääriseksi puuksi, kun se täyttää 2 i: n solmun edellytyksen jokaisella tasolla, jossa i on taso.
- Kierretty binääri on binaaripuu, joka koostuu joko 0: sta ei solmuista tai 2 solmujen lukumäärästä.
Traversal-tekniikat
Puun kulku on yksi useimmista puun tietorakenteessa suoritettavista operaatioista, joissa kukin solmu vieraili tarkalleen kerran järjestelmällisesti.
- Inorder- Tässä puussa kulkee vasemman alareunan rekursiivisesti, sitten juuren solmua käydään ja viimeisessä oikeassa alikunnassa.
- Esittäjä- Tässä puussa kulkee juuren solmu ensimmäisellä, sitten vasemmassa alikunnassa ja lopulta oikeassa alapuolessa.
- Postorder- Tämä tekniikka vierailee vasemmalla subtree sitten oikea subtree ja viimeisin root solmu.
B-puun ja binaaripuun keskeiset erot
- B-puussa lapsisolmujen enimmäismäärä ei-päätelaitteella voi olla M, jossa M on B-puun järjestys. Toisaalta binääripuulla voi olla korkeintaan kaksi subtrees- tai lapsisolmua.
- B-puuta käytetään, kun dataa tallennetaan levylle, kun taas binaaripuuta käytetään, kun dataa tallennetaan muistiin, kuten muistiin.
- Toinen B-puun sovellusalue on koodin indeksointidatan rakenne DBMS: ssä, sen sijaan binaaripuuta käytetään koodin optimoinnissa, huffman-koodauksessa jne.
- B-puun maksimikorkeus on log M N (M on puun järjestys). Vastakohtana binääripuun maksimikorkeus on log 2 N (N on solmujen lukumäärä ja pohja on 2, koska se on binaarinen).
johtopäätös
B-puuta käytetään binäärisen ja binäärisen hakupuun yli. Tärkein syy tähän on muistihierarkia, jossa CPU on kytketty välimuistiin suurten kaistanleveyskanavien kanssa, kun taas CPU on kytketty levylle pienen kaistanleveyskanavan kautta. Binaaripuuta käytetään, kun muistit tallennetaan muistiin (pieni ja nopea) ja B-puuta käytetään, kun tietueita tallennetaan levylle (suuri ja hidas). Niinpä B-puun käyttö Binary-puun sijasta vähentää merkittävästi käyttöaikaa suuren haarautumistekijän ja puun pienentyneen korkeuden vuoksi.
