Seuraavassa opetusohjelmassa opimme B-puun tietorakenteesta ja harkitsemme sen visualisointia.
merkkijonomuoto java
Joten aloitetaan.
Mikä on B-puu?
The B Puu on erityinen monitiehakupuu , joka tunnetaan yleisesti nimellä M-tie puu, joka tasapainottaa itsensä. Tasapainoisen rakenteensa vuoksi näitä puita käytetään yleisesti valtavien tietokantojen ohjaamiseen ja hallintaan sekä hakujen yksinkertaistamiseen. B-puussa jokaisella solmulla voi olla enintään n alisolmua. B Tree on esimerkki monitasoisesta indeksoinnista tietokannan hallintajärjestelmässä (DBMS). Lehti- ja sisäsolmuilla on molemmilla tietueviitteet. B-puu tunnetaan nimellä Balanced Stored Tree, koska kaikki lehtien solmut ovat samalla tasolla.
Seuraava kaavio on esimerkki B-puusta:
Kuvio 1. A B Puu tilauksella 3
B-puun sääntöjen ymmärtäminen
Seuraavat ovat B-puun tärkeitä ominaisuuksia:
- Kaikki lehtien solmut ovat samalla tasolla.
- B-puun tietorakenne määritellään termillä minimiaste 'd'. 'd':n arvo riippuu levylohkon koosta.
- Jokaisen solmun, juuria lukuun ottamatta, tulee sisältää vähintään d-1 avaimet. Juurisolmu voi koostua vähintään yhdestä avaimesta.
- Kaikki solmut (mukaan lukien juurisolmu) voivat sisältää enintään (2pv-1) avaimet.
- Solmun lapsien lukumäärä on yhtä suuri kuin siinä olevien avainten lukumäärän lisääminen ja .
- Kaikki solmun avaimet lajitellaan nousevaan järjestykseen. Kahden näppäimen k1 ja k2 välissä oleva lapsi koostuu kaikista avaimista k1 ja k2.
- Toisin kuin binäärihakupuu, B-puun tietorakenne kasvaa ja kutistuu juuresta. Kun taas binäärihakupuu kasvaa alaspäin ja kutistuu alaspäin.
- Muiden itsetasapainoisten binaarihakupuiden tapaan B-puun tietorakenteen aika monimutkaisuus toimintojen, kuten etsimisen, lisäämisen ja poistamisen, kannalta on O(log?n) .
- Solmun lisääminen B-puuhun tapahtuu vain lehtisolmussa.
Tarkastellaan seuraavaa esimerkkiä B-puusta, jonka vähimmäisluokka on 5.
Kuva 2. A B Järjestyspuu 5
Huomaa: Vähimmäistilauksen arvo on paljon enemmän kuin 5 käytännön B-puissa.
Yllä olevassa kaaviossa voimme havaita, että kaikki lehtisolmut ovat samalla tasolla, ja kaikilla ei-lehtisolmuilla ei ole tyhjää alipuuta ja ne koostuvat avaimista, joka on yhden pienempi kuin niiden lasten lukumäärä.
B-puun sääntöjen asetettu muotoilu:
Jokainen B-puu riippuu positiivisesta vakiokokonaisluvusta, joka tunnetaan nimellä MINIMI , jota käytetään määrittämään tietoelementtien lukumäärä, jotka voidaan pitää yhdessä solmussa.
Sääntö 1: Juuressa voi olla vain yksi tietoelementti (tai ei lainkaan dataelementtejä, jos se ei ole myöskään alatasoa); jokaisessa toisessa solmussa on vähintään MINIMI tietoelementtejä.
Sääntö 2: Solmuun tallennettujen tietoelementtien enimmäismäärä on kaksi kertaa arvo MINIMI .
Sääntö 3: B-puun kunkin solmun tietoelementit tallennetaan osittain täytettyyn taulukkoon, joka on lajiteltu pienimmästä tietoelementistä (indeksissä 0 ) suurimmalle tietoelementille (taulukon lopulliseen käytettyyn paikkaan).
Sääntö 4: Ei-lehtisolmun alapuolella olevien alipuiden kokonaismäärä on aina yksi enemmän kuin kyseisessä solmussa olevien tietoelementtien lukumäärä.
- alipuu 0, alipuu 1,...
Sääntö 5: Mitä tulee muihin kuin lehtiin:
- Indeksin tietoelementti on suurempi kuin kaikki alipuun numeron tietoelementit i solmun ja
- Indeksin tietoelementti on pienempi kuin kaikki alipuun numeron tietoelementit i+1 solmusta.
Sääntö 6: Jokaisella B-puun lehdellä on sama syvyys. Siten se varmistaa, että B-puu estää epätasapainoisen puun ongelman.
Toiminnot B-puun tietorakenteessa
Sen varmistamiseksi, että mitään B-puun tietorakenteen ominaisuuksista ei riko toimintojen aikana, B-puu voidaan jakaa tai yhdistää. Seuraavassa on joitain toimintoja, jotka voimme suorittaa B-puussa:
- Haetaan tietoelementtiä B-puusta
- Tietoelementin lisääminen B-puuhun
- Tietoelementin poistaminen B-puusta
Hakuoperaatio B-puusta
Elementin etsiminen B-puusta on samanlaista kuin binäärihakupuussa. Mutta sen sijaan, että B-puu tekisi kaksisuuntaisen päätöksen (vasen tai oikea) kuten binäärihakupuu, se tekee m-suuntaisen päätöksen jokaisessa solmussa, jossa m on solmun lapsien lukumäärä.
Tietoelementin haun vaiheet B-puusta:
Vaihe 1: Haku alkaa juurisolmusta. Vertaa hakuelementtiä k juureen.
Vaihe 1.1: Jos juurisolmu koostuu elementistä k, haku on valmis.
Vaihe 1.2: Jos elementti k on pienempi kuin juuren ensimmäinen arvo, siirrymme vasemmanpuoleisimpaan alaluokkaan ja etsimme alatason rekursiivisesti.
Vaihe 1.3.1: Jos juurella on vain kaksi lasta, siirrymme oikeanpuoleiseen aliryhmään ja etsimme rekursiivisesti alisolmut.
Vaihe 1.3.2: Jos juurella on enemmän kuin kaksi avainta, etsimme loput.
Vaihe 2: Jos elementtiä k ei löydy koko puun läpikäynnin jälkeen, hakuelementti ei ole B-puussa.
1 miljoona kuinka monta 0
Visualisoidaan yllä olevat vaiheet esimerkin avulla. Oletetaan, että halusimme etsiä avainta k=34 seuraavasta B-puusta:
Kuva 3.1. Tietty B-puu
- Ensinnäkin tarkistamme, onko avain k = 34 on juurisolmussa. Koska avain ei ole juuressa, siirrymme sen lapsisolmuihin. Voimme myös havaita, että juurisolmulla on kaksi lasta; siksi vertaamme vaadittua arvoa kahden avaimen välillä.
Kuva 3.2. Avain k ei ole juuressa - Nyt kun voimme huomata, että avain k on suurempi kuin juurisolmu, eli 30, edetään juuren oikean lapsen kanssa.
Kuva 3.3. Avain k > 30, siirry oikealle lapselle - Nyt verrataan avainta k solmussa oleviin arvoihin, eli 40 ja 50. Koska avain k on pienempi kuin vasen näppäin, eli 40, siirrymme solmun vasempaan lapseen.
Kuva 3.4. Avain k<40, move to left child< li> - Koska 40:n vasemman lapsen arvo on 34, joka on vaadittu arvo, voimme päätellä, että avain on löydetty ja hakutoiminto on suoritettu.
Kuva 3.4. Avain k = 34, vasen lapsi 40
Vertasimme avainta neljään eri arvoon yllä olevassa esimerkissä, kunnes löysimme sen. Siten B-puun hakuoperaatioon vaadittava aikamonimutkaisuus on O(log?n) .
Toiminnon lisääminen B-puuhun
Kun lisäämme tietoelementtiä B-puuhun, meidän on ensin tarkistettava, onko kyseinen elementti jo puussa vai ei. Jos tietoelementti löytyy B-puusta, lisäystoimintoa ei tapahdu. Jos näin ei kuitenkaan ole, jatkamme lisäämistä. Kun elementtiä lisätään lehtisolmuun, on otettava huomioon kaksi skenaariota:
Tietoelementin lisääminen B-puuhun:
Vaihe 1: Aloitamme laskemalla solmun avainten enimmäismäärän B-puun järjestyksen perusteella.
Vaihe 2: Jos puu on tyhjä, allokoidaan juurisolmu, ja lisäämme juurisolmuna toimivan avaimen.
Vaihe 3: Etsimme nyt sopivaa solmua lisätystä varten.
Vaihe 4: Jos solmu on täynnä:
Vaihe 4.1: Lisäämme tietoelementit nousevassa järjestyksessä.
Vaihe 4.2: Jos tietoelementit ovat suurempia kuin avainten enimmäismäärä, jaamme mediaanin koko solmun.
Vaihe 4.3: Painamme mediaaninäppäintä ylöspäin ja jaamme vasen ja oikea näppäin vasen ja oikea lapsi.
Vaihe 5: Jos solmu ei ole täynnä, lisäämme solmun nousevassa järjestyksessä.
Visualisoidaan yllä olevat vaiheet esimerkin avulla. Oletetaan, että meidän on luotava B-puu järjestyksessä 4. B-puuhun lisättävät tietoelementit ovat 5, 3, 21, 11, 1, 16, 8, 13, 4 ja 9 .
- Koska m on yhtä suuri kuin 3, solmun avainten enimmäismäärä = m-1 = 3-1 = 2 .
- Aloitamme lisäämällä 5 tyhjässä puussa.
Kuva 4.1. Lisääminen 5 - Lisäämme nyt 3 puuhun. Koska 3 on pienempi kuin 5, lisäämme 3:n 5:n vasemmalle puolelle samaan solmuun.
Kuva 4.2. Lisääminen 3 - Lisäämme nyt 21 puuhun, ja koska 21 on suurempi kuin 5, se lisätään numeron 5 oikealle puolelle samaan solmuun. Koska tiedämme kuitenkin, että avainten enimmäismäärä solmussa on 2, yksi näistä avaimista siirretään yllä olevaan solmuun sen jakamiseksi. Siten 5, keskimmäinen tietoelementti, siirtyy ylöspäin, ja 3:sta ja 21:stä tulee vastaavasti vasen ja oikea solmu.
Kuva 4.3. Lisäys 21 - Nyt on aika lisätä seuraava dataelementti, eli 11, joka on suurempi kuin 5 mutta pienempi kuin 21. Siksi 11 lisätään avaimeksi 21:stä koostuvan solmun vasemmalle puolelle avaimeksi.
Kuva 4.4. Lisäys 11 - Vastaavasti lisäämme puuhun seuraavan tietoelementin 1, ja kuten voimme havaita, 1 on pienempi kuin 3; siksi se lisätään avaimena 3:sta koostuvan solmun vasemmalle puolelle avaimena.
Kuva 4.5. Lisääminen 1 - Nyt lisäämme puuhun tietoelementin 16, joka on suurempi kuin 11 mutta pienempi kuin 21. Kuitenkin avainten määrä kyseisessä solmussa ylittää avainten enimmäismäärän. Siksi solmu jakautuu siirtäen keskiavaimen juureen. Näin ollen 16 lisätään numeron 5 oikealle puolelle jakaen 11 ja 21 kahdeksi erilliseksi solmuksi.
Kuva 4.6. Lisäys 16 - Tietoelementti 8 lisätään avaimena 11:n vasemmalle puolelle.
Kuva 4.7. Lisäys 8 - Lisäämme puuhun luvun 13, joka on pienempi kuin 16 ja suurempi kuin 11. Siksi tietoelementti 13 tulee lisätä solmun oikealle puolelle, joka koostuu 8:sta ja 11:stä. Koska puussa olevien avainten enimmäismäärä voi kuitenkin olla vain 2, tapahtuu jako, jolloin keskimmäinen tietoelementti 11 siirtyy yllä olevaan solmuun ja 8 ja 13 kahdeksi erilliseksi solmuksi. Nyt yllä oleva solmu koostuu 5:stä, 11:stä ja 16:sta, mikä taas ylittää avainten enimmäismäärän. Tästä syystä tulee toinen jako, jolloin tietoelementistä 11 tulee juurisolmu, jonka lapsina ovat 5 ja 16.
Kuva 4.8. Lisäys 13 - Koska tietoelementti 4 on pienempi kuin 5, mutta suurempi kuin 3, se lisätään 1:stä ja 3:sta koostuvan solmun oikealle puolelle, mikä taas ylittää avainten enimmäismäärän solmussa. Siksi vuoto tapahtuu uudelleen, jolloin 3 siirtyy ylempään solmuun 5:n viereen.
Kuva 4.9. Lisääminen 4 - Viimeinkin tietoelementti 9, joka on suurempi kuin 8 mutta pienempi kuin 11, lisätään avaimeksi 8:sta koostuvan solmun oikealle puolelle.
Kuva 4.10. Lisäys 9
Yllä olevassa esimerkissä olemme tehneet erilaisia vertailuja. Ensimmäinen arvo lisättiin suoraan puuhun; sen jälkeen jokaista arvoa oli verrattava kyseisessä puussa käytettävissä oleviin solmuihin. Lisäystoiminnon aika monimutkaisuus B-puussa riippuu solmujen määrästä ja .
Toiminnon poistaminen B-puusta
Tietoelementin poistaminen B-puusta sisältää kolme ensisijaista tapahtumaa:
- Etsitään solmua, jossa poistettava avain on,
- Avaimen poistaminen ja
- Puun tasapainottaminen tarvittaessa.
Kun elementtiä poistetaan puusta, voi ilmetä tila, joka tunnetaan nimellä Underflow. Alivuoto tapahtuu, kun solmu koostuu alle vähimmäismäärästä avaimia; sen pitäisi kestää.
Seuraavat ovat joitain termejä, jotka on ymmärrettävä ennen poistotoiminnon visualisoimista:
Seuraavassa on kolme näkyvää tapausta poistotoiminnosta B-puussa:
Tapaus 1: Avaimen poisto/poisto on Leaf-solmussa - Tämä tapaus jaetaan edelleen kahteen eri tapaukseen:
1. Avaimen poistaminen/poistaminen ei riko solmun sisältämien avainten vähimmäismäärän ominaisuutta.
Havainnollistetaan tämä tapaus esimerkillä, jossa poistamme avaimen 32 seuraavasta B-puusta.
Kuva 4.1: Lehtisolmun avaimen (32) poistaminen B-puusta
Kuten voimme havaita, 32:n poistaminen tästä puusta ei riko yllä olevaa ominaisuutta.
2. Avaimen poistaminen/poistaminen rikkoo solmun sisältämien avainten vähimmäismäärän ominaisuutta. Tässä tapauksessa meidän on lainattava avain sen läheiseltä sisarussolmulta järjestyksessä vasemmalta oikealle.
Ensin vierailemme lähimmän vasemmiston sisaruksen luona. Jos vasemmalla sisarussolmulla on enemmän kuin vähimmäismäärä avaimia, se lainaa avaimen tästä solmusta.
Muussa tapauksessa tarkistamme, että lainataanko lähimmältä oikealta sisarussolmulta.
Havainnollistetaan nyt tämä tapaus esimerkin avulla, jossa poistetaan 31 yllä olevasta B-puusta. Lainaamme tässä tapauksessa avaimen vasemmasta sisarussolmusta.
Kuva 4.2: Lehtisolmun avaimen (31) poistaminen B-puusta
Jos molemmat lähisisarussolmut sisältävät jo vähimmäismäärän avaimia, yhdistämme solmun joko vasemman tai oikean sisarussolmun kanssa. Tämä yhdistämisprosessi tapahtuu pääsolmun kautta.
Visualisoidaan uudestaan poistamalla avain 30 yllä olevasta B-puusta.
Kuva 4.3: Lehtisolmun avaimen (30) poistaminen B-puusta
Tapaus 2: Avaimen poistaminen/poistaminen tapahtuu ei-Leaf-solmussa - Tämä tapaus jaetaan edelleen eri tapauksiin:
1. Ei-lehti/sisäinen solmu, joka poistetaan, korvataan järjestyksessä edeltävällä solmulla, jos vasemmalla alisolmulla on enemmän kuin vähimmäismäärä avaimia.
Havainnollistetaan tämä tapaus esimerkillä, jossa poistamme avaimen 33 B-puusta.
Kuva 4.4: Lehtisolmun avaimen (33) poistaminen B-puusta
2. Ei-lehti/sisäinen solmu, joka poistetaan, korvataan järjestyksen seuraajalla, jos oikealla alisolmulla on enemmän kuin vähimmäismäärä avaimia.
Jos jommallakummalla lapsilla on vähimmäismäärä avaimia, yhdistämme vasemman ja oikean alisolmut.
Visualisoidaan tämä tapaus poistamalla avain 30 B-puusta.
Kuva 4.5: Lehtisolmun avaimen (30) poistaminen B-puusta
Jos pääsolmulla on yhdistämisen jälkeen vähemmän avaimia kuin vähimmäismäärä, voidaan etsiä sisaruksia, kuten Tapaus 1 .
Tapaus 3: Seuraavassa tapauksessa puun korkeus pienenee. Jos kohdeavain on sisäisessä solmussa ja avaimen poistaminen johtaa siihen, että solmussa on vähemmän avaimia (joka on vähemmän kuin vaadittu vähimmäismäärä), etsi järjestyksen edeltäjä ja järjestyksessä seuraaja. Jos molemmilla lapsilla on vähimmäismäärä avaimia, lainaaminen ei onnistu. Tämä johtaa Tapaus 2(3) , eli alisolmujen yhdistäminen.
abstrakti luokka vs käyttöliittymä
Etsimme jälleen sisarusta lainataksemme avainta. Kuitenkin, jos sisarus koostuu myös vähimmäismäärästä avaimia, yhdistämme solmun sisaruksen kanssa pääsolmun kanssa ja järjestämme alisolmut vaatimusten mukaisesti (nousevassa järjestyksessä).
Visualisoidaan tämä tapaus esimerkin avulla, jossa poistetaan tietoelementti 10 annetusta B-puusta.
Kuva 4.6: Lehtisolmun avaimen (10) poistaminen B-puusta
Aika monimutkaisuus yllä olevissa esimerkeissä vaihtelee riippuen sijainnista, josta avain on poistettava. Siten B-puun poistotoiminnon aika monimutkaisuus on O(log?n) .
Johtopäätös
Tässä opetusohjelmassa olemme oppineet B-puusta ja visualisoineet sen erilaisia toimintoja eri esimerkein. Olemme myös ymmärtäneet joitain B-puun perusominaisuuksia ja sääntöjä.