B-puu vs. binaarinen puu
Sisältö
- Sisältö: Ero B-puun ja binaaripuun välillä
- Vertailutaulukko
- B-tree
- Binaarinen puu
- Keskeiset erot
- johtopäätös
- Selittävä video
Ero B-puun ja binaaripuun välillä on se, että B-puu on lajiteltu puu, jossa solmut lajitellaan inorder-poikittain, kun taas binaaripuu on tilattu puu, jolla on osoitin jokaisessa solmussa.
Tietorakenteet ovat tärkeimmät käsitteet tietokoneohjelmoinnissa, ja tietorakenteissa kaksi tärkeintä käsitettä ovat B-puu ja Binaarinen puu. Molemmat eroavat toisistaan. B-puu on lajiteltu puu, jossa solmut lajitellaan poikkisuuntaiseksi, kun taas binaaripuu on tilattu puu, jolla on osoitin jokaisessa solmussa. B-puu ja binaaripuu ovat epälineaarisia tietorakenteita. Nimeltä molemmat termit näyttävät olevan samoja, mutta ne eivät ole samoja, koska ne ovat erilaisia. Binaarinen puukoodi tallennetaan RAM-muistiin, kun taas B-puukoodi tallennetaan levylle.
B-puu on M-suuntainen puu, joka on tasapainoinen, B-puu tunnetaan tasapainoisena lajittelupuuna. B-puussa on inorder-läpikulku. B-puun tilan monimutkaisuus on O (n). Lisäys- ja poistoaikojen monimutkaisuus on O (log n). B-puussa puun korkeuden tulisi olla mahdollisimman pieni. B-puussa ei tulisi olla tyhjää alaosaa. Puun kaikkien lehtien tulee olla samalla tasolla. Jokaisessa solmussa voi olla enintään M lasten lukumäärä ja vähintään M / 2 lasten lukumäärä. Jokaisessa B-puun solmussa tulisi olla vähemmän avainta kuin lapsiavaimessa. B-puussa näppäimen vasemmassa alaosaan kuuluvat avaimet ovat edeltäjiä. Kun solmu on täynnä ja yrität lisätä uuden solmun, puu on jaettu kahteen osaan. Voit yhdistää B-puun solmuja, kunnes solmut poistetaan.
Binaaripuussa on kaksi osoitinta, jotka sisältävät lapsisolmujen osoitteet. On olemassa tyyppejä binaaripuita, kuten tiukasti binaarinen puu, täydellinen binaaripuu, laajennettu binaaripuu jne. Tiukasti binaarisessa puussa on oltava vasen ala- ja oikea alaosa, täydellisessä binaarisessa puussa tulisi olla kaksi solmua Jokaisella tasolla ja kierteitetyssä binaaripuussa tulisi olla 0 - 2 määrää solmuja. Jos puhumme poikittaisista tekniikoista, kolme poikittaista tekniikkaa ovat poikittaisessa järjestyksessä, ennakkotilaa poikittainen ja post-order poikittaissuunnassa.
Sisältö: Ero B-puun ja binaaripuun välillä
- Vertailutaulukko
- B-tree
- Binaarinen puu
- Keskeiset erot
- johtopäätös
- Selittävä video
Vertailutaulukko
Perusta | B-tree | Binaarinen puu |
Perusta | B-puu on lajiteltu puu, jossa solmut lajitellaan inorder-läpikulun mukaan. | Binaaripuu on tilattu puu, jolla on osoitin jokaisessa solmussa. |
myymälä | B-puun koodi tallennetaan levylle. | Binaarinen puukoodi tallennetaan RAM-muistiin |
Korkeus | B-puun korkeus on log N | Binaaripuun korkeus tulee lokiksi2 N |
hakemus | DBMS on B-puun sovellus. | Huffman-koodaus on sovellus binaaripuulta. |
B-tree
B-puu on M-suuntainen puu, joka on tasapainoinen, B-puu tunnetaan tasapainoisena lajittelupuuna. B-puussa on inorder-läpikulku. B-puun tilan monimutkaisuus on O (n). Lisäys- ja poistoaikojen monimutkaisuus on O (log n). B-puussa puun korkeuden tulisi olla mahdollisimman pieni.
B-puussa ei tulisi olla tyhjää alaosaa. Puun kaikkien lehtien tulee olla samalla tasolla. Jokaisessa solmussa voi olla korkeintaan M lukumäärä lapsia ja vähintään M / 2 lukumäärää lapsia. Jokaisessa B-puun solmussa tulisi olla vähemmän avainta kuin lapsiavaimessa. B-puussa näppäimen vasemmassa alaosaan kuuluvat avaimet ovat edeltäjiä. Kun solmu on täynnä ja yrität lisätä uuden solmun, puu on jaettu kahteen osaan. Voit yhdistää B-puun solmuja, kunnes solmut poistetaan.
Binaarinen puu
Binaaripuussa on kaksi osoitinta, jotka sisältävät lapsisolmujen osoitteet. On olemassa tyyppejä binaaripuita, kuten tiukasti binaaripuu, täydellinen binaaripuu, laajennettu binaaripuu jne.
Tiukasti binaarisessa puussa on oltava vasen ala- ja oikea alaosa, täydellisessä binaarisessa puussa tulisi olla kaksi solmua jokaisella tasolla ja kierteitetyssä binaarisessa puussa tulisi olla 0 - 2 lukumäärää. Jos puhumme poikittaisista tekniikoista, on olemassa kolme poikittaista tekniikkaa, jotka ovat järjestyksessä poikittaisia, ennakkotilauksia poikittaisia ja tilauksen jälkeisiä poikittaisia.
Keskeiset erot
- B-puu on lajiteltu puu, jossa solmut lajitellaan inorder-läpikulkuun, kun taas binaaripuu on tilattu puu, jolla on osoitin jokaisessa solmussa.
- B-puukoodi tallennetaan levylle, kun taas binaarinen puukoodi tallennetaan RAMiin.
- B-puun korkeus on logN, kun taas binaarisen puun korkeus on loki2 N
- DBMS on B-puun sovellus, kun taas Huffman-koodaus on binaaripuun sovellus.
johtopäätös
Yllä olevassa artikkelissa näemme selvän eron B-puun ja binaaripuun välillä niiden toteutuksessa.