B PUU tietorakenteessa: Etsi, lisää, poista toimintoesimerkki

Sisällysluettelo:

Anonim

Mikä on B-puu?

B Tree on itsestään tasapainottava tietorakenne, joka perustuu tiettyihin sääntöihin tietojen etsimiseen, lisäämiseen ja poistamiseen nopeammin ja muistia tehokkaammin. Tämän saavuttamiseksi noudatetaan seuraavia sääntöjä B-puun luomiseksi.

B-puu on erityinen puu tietorakenteessa. Vuonna 1972 McCreight otti ensimmäisen kerran käyttöön tämän menetelmän, ja Bayer nimitti sen Height Balanced m-way Search Treeiksi. Se auttaa sinua säilyttämään lajiteltuja ja sallittuja erilaisia ​​toimintoja, kuten lisäys, haku ja poisto, lyhyemmässä ajassa.

Tässä B-Tree-opetusohjelmassa opit:

  • Mikä on B-puu?
  • Miksi käyttää B-Puuta
  • B-puun historia
  • Hakutoiminto
  • Lisää toiminta
  • Poista toiminto

B-Puun säännöt

Tässä on tärkeitä sääntöjä B_Tree: n luomiseen

  • Kaikki lehdet luodaan samalla tasolla.
  • B-puu määräytyy tutkintojen määrällä, jota kutsutaan myös "järjestykseksi" (jonka määrittelee ulkopuolinen toimija, kuten ohjelmoija), johon viitataan 
    m
    eteenpäin. Arvo 
    m
    riippuu levyn lohkon koosta, jolle data ensisijaisesti sijaitsee.
  • Solmun vasemmalla alipuussa on pienemmät arvot kuin alipuun oikealla puolella. Tämä tarkoittaa, että myös solmut lajitellaan nousevassa järjestyksessä vasemmalta oikealle.
  • Lapsisolmujen, juurisolmun ja sen alisolmujen enimmäismäärä voidaan laskea tällä kaavalla: 
    m - 1
    Esimerkiksi: 
    m = 4max keys: 4 - 1 = 3

  • Jokaisessa solmussa, juuria lukuun ottamatta, on oltava vähintään 
    [m/2]-1
    Esimerkiksi: 
    m = 4min keys: 4/2-1 = 1
  • Solmun enimmäismäärä lapsisolmuja voi olla sama kuin sen aste, joka on 
    m
  • Solmujen minimi lapsi on puolet järjestyksestä, joka on m / 2 (otetaan kattoarvo).
  • Kaikki solmun avaimet lajitellaan kasvavassa järjestyksessä.

Miksi käyttää B-Puuta

Tässä on syitä B-Puun käyttämiseen

  • Vähentää levylle tehtyjen lukujen määrää
  • B Puut voidaan helposti optimoida säätämään sen kokoa (eli lapsisolmujen määrää) levyn koon mukaan
  • Se on erityisesti suunniteltu tekniikka suurten tietomäärien käsittelemiseksi.
  • Se on hyödyllinen algoritmi tietokannoille ja tiedostojärjestelmille.
  • Hyvä valinta valita, kun on kyse suurten tietoryhmien lukemisesta ja kirjoittamisesta

B-puun historia

  • Tiedot tallennetaan levylle lohkoina, näitä tietoja, kun ne tuodaan päämuistiin (tai RAM-muistiin), kutsutaan tietorakenteeksi.
  • Jos kyseessä on valtava data, yhden tietueen etsiminen levyltä edellyttää koko levyn lukemista; tämä lisää aikaa ja päämuistin kulutusta levyn suuren taajuuden ja tiedon koon vuoksi.
  • Tämän voittamiseksi luodaan hakemistotaulukot, jotka tallentavat tietueiden tietueiden viittauksen niiden sisältämien lohkojen perusteella. Tämä vähentää huomattavasti aikaa ja muistin kulutusta.
  • Koska meillä on valtavia tietoja, voimme luoda monitasoisia hakemistotaulukoita.
  • Monitasoinen hakemisto voidaan suunnitella käyttämällä B-puuta pitämään tiedot lajiteltuina itsetasapainossa.

Hakutoiminto

Hakutoiminto on yksinkertaisin toiminto B Puussa.

Seuraavaa algoritmia käytetään:

  • Anna avaimen (arvon) etsiä sanalla "k".
  • Aloita haku juuresta ja siirry rekursiivisesti alaspäin.
  • Jos k on pienempi kuin juuriarvo, etsi vasemmalta alipuuta, jos k on suurempi kuin juuriarvo, etsi oikeaa alipuuta.
  • Jos solmulla on löydetty k, palauta vain solmu.
  • Jos k: tä ei löydy solmusta, kulje lapsen kanssa suuremmalla avaimella.
  • Jos k: tä ei löydy puusta, palautamme NULL.

Lisää toiminta

Koska B Tree on itsetasapainottava puu, et voi pakottaa avainta lisäämään mihinkään solmuun.

Seuraava algoritmi pätee:

  • Suorita hakutoiminto ja etsi sopiva paikka.
  • Aseta uusi avain oikeaan paikkaan, mutta jos solmussa on jo enimmäismäärä avaimia:
  • Solmu ja vasta lisätty avain hajoavat keskiosasta.
  • Keskimmäisestä elementistä tulee kahden muun lapsisolmun vanhempi.
  • Solmujen on järjestettävä avaimet uudelleen nousevassa järjestyksessä.

KÄRKI

Seuraava ei pidä paikkaansa lisäysalgoritmista:

Koska solmu on täynnä, se jakautuu ja lisätään uusi arvo

Yllä olevassa esimerkissä:

  • Etsi sopiva sijainti solmusta avaimelle
  • Aseta avain kohdesolmuun ja tarkista säännöt
  • Onko solmun lisäämisen jälkeen enemmän kuin yhtä suuri kuin avainten vähimmäismäärä, joka on 1? Tässä tapauksessa kyllä, kyllä. Tarkista seuraava sääntö.
  • Onko solmun lisäämisen jälkeen enemmän kuin enimmäismäärä avaimia, mikä on 3? Tässä tapauksessa ei, ei. Tämä tarkoittaa, että B-puu ei riko mitään sääntöjä ja lisäys on valmis.

Yllä olevassa esimerkissä:

  • Solmu on saavuttanut näppäinten enimmäismäärän
  • Solmu jakautuu ja keskimmäisestä avaimesta tulee kahden muun solmun juurisolmu.
  • Parillisten avainten lukumäärän tapauksessa keskisolmu valitaan vasemmalla tai oikealla puolella.

Yllä olevassa esimerkissä:

  • Solmussa on alle enimmäisavaimia
  • 1 lisätään 3: n viereen, mutta nousevan järjestyksen sääntöä rikotaan
  • Tämän korjaamiseksi avaimet lajitellaan

Vastaavasti 13 ja 2 voidaan lisätä helposti solmuun, koska ne täyttävät solmuille alle avaimet -säännön.

Yllä olevassa esimerkissä:

  • Solmussa on avaimet, jotka ovat yhtä suuria kuin avaimet.
  • Avain lisätään kohdesolmuun, mutta se rikkoo max-avainten sääntöä.
  • Kohdesolmu on jaettu, ja keskimmäinen avain vasemmalla puolueella on nyt uusien lapsisolmujen vanhempi.
  • Uudet solmut on järjestetty nousevaan järjestykseen.

Samoin yllä olevien sääntöjen ja tapausten perusteella loput arvot voidaan lisätä helposti B-puuhun.

Poista toiminto

Poistotoiminnolla on enemmän sääntöjä kuin lisäys- ja hakutoiminnoilla.

Seuraava algoritmi pätee:

  • Suorita hakutoiminto ja etsi kohdeavain solmuista
  • Kolme ehtoa sovellettiin kohdeavaimen sijainnin perusteella, kuten seuraavissa osissa selitetään

Jos kohdeavain on lehtisolmussa

  • Kohde on lehtisolmussa, enemmän kuin min-näppäimiä.
    • Tämän poistaminen ei riko B Puun omaisuutta
  • Kohde on lehtisolmussa, sillä on min-avainsolmut
    • Tämän poistaminen rikkoo B Puun omaisuutta
    • Kohdesolmu voi lainata avainta välittömästä vasemmasta solmusta tai välittömästä oikeasta solmusta (sisarus)
    • Sisar sanoo kyllä, jos sillä on enemmän kuin vähimmäismäärä avaimia
    • Avain lainataan pääsolmulta, enimmäisarvo siirretään vanhemmalle, yläsolmun enimmäisarvo siirretään kohdesolmulle ja poistetaan kohdearvo
  • Kohde on lehtisolmussa, mutta millään sisaruksella ei ole enempää kuin avaimia
    • Etsi avain
    • Yhdistä sisarusten ja vanhempien solmujen vähimmäismäärän kanssa
    • Avainten kokonaismäärä on nyt yli min
    • Kohde-avain korvataan yläsolmun vähimmäismäärällä

Jos kohdeavain on sisäisessä solmussa

  • Joko valitse, järjestyksessä edeltäjä tai järjestyksessä seuraaja
  • Tilauksessa olevan edeltäjän tapauksessa vasemman alipuun suurin avain valitaan
  • Oikein seuraajana valitaan vähimmäisavain sen oikeasta alipuusta
  • Jos kohdeavaimen järjestyksessä olevassa edeltäjässä on enemmän kuin min-avaimet, vain se voi korvata kohdeavaimen järjestyksessä olevan edeltäjän maksimilla.
  • Jos kohdeavaimen järjestyksessä olevalla edeltäjällä ei ole enempää kuin min-avaimet, etsi järjestyksessä olevan seuraajaan minimiavain.
  • Jos kohdeavaimen järjestyksessä olevalla edeltäjällä ja seuraajalla on molemmilla alle min-avaimet, sulauta edeltäjä ja seuraaja.

Jos kohdeavain on juurisolmussa

  • Korvaa järjestyksessä olevan edeltäjän alipuun enimmäisosalla
  • Jos poistamisen jälkeen kohteella on alle min avainta, kohdesolmu lainaa sisarukseltaan maksimiarvon sisaruksen vanhemman kautta.
  • Kohde ottaa vanhemman enimmäisarvon, mutta sisaruksen enimmäisarvon solmuilla.

Ymmärretään nyt poistotoiminto esimerkillä.

Yllä oleva kaavio näyttää erilaisia ​​poisto-operaatioita B-puussa. Tämä B-puu on järjestyksessä 5, mikä tarkoittaa, että alisolmujen vähimmäismäärä missä tahansa solmussa voi olla 3, ja alisolmujen enimmäismäärä missä tahansa solmussa voi olla 5. Kun taas solmujen vähimmäis- ja enimmäismäärä avaimia voi olla 2 ja 4, vastaavasti.

Yllä olevassa esimerkissä:

  • Kohdesolmussa on poistettava kohdeavain
  • Kohdesolmussa on avaimia enemmän kuin vähimmäisavaimia
  • Poista avain yksinkertaisesti

Yllä olevassa esimerkissä:

  • Kohdesolmussa on avaimet, jotka ovat yhtä pienet kuin avaimet, joten sitä ei voi poistaa suoraan, koska se rikkoo ehtoja

Seuraavassa kaaviossa selitetään, kuinka tämä avain poistetaan:

  • Kohdesolmu lainaa avaimen välittömältä sisarukselta, tässä tapauksessa järjestyksessä olevalta edeltäjältä (vasen sisarus), koska sillä ei ole järjestyksessä olevaa seuraajaa (oikea sisarus)
  • Tilauksen edeltäjän enimmäisarvo siirretään vanhemmalle, ja vanhempi siirtää enimmäisarvon kohdesolmulle (katso alla oleva kaavio)

Seuraava esimerkki kuvaa, kuinka arvoavaava avain poistetaan järjestyksessä olevasta seuraajasta.

  • Kohdesolmu lainaa avaimen välittömältä sisarukselta, tässä tapauksessa järjestyksessä olevalta seuraajalta (oikea sisarus), koska sen järjestyksessä olevan edeltäjän (vasemman sisaruksen) avaimet ovat yhtä suuret kuin minimiavain.
  • Järjestyksessä olevan seuraajan vähimmäisarvo siirretään vanhemmalle, ja vanhempi siirtää enimmäisarvon kohdesolmulle.

Alla olevassa esimerkissä kohdesolmulla ei ole sisarusta, joka voisi antaa avaimensa kohdesolmulle. Siksi yhdistäminen on välttämätöntä.

Katso menettely tällaisen avaimen poistamiseksi:

  • Yhdistä kohdesolmu mihin tahansa sen välittömään sisarukseen vanhemman avaimen kanssa
    • Pääsolmun avain valitaan, että sisarukset kahden sulautuvan solmun välissä
  • Poista kohdeavain yhdistetystä solmusta

Poista operaation näennäinen koodi

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}

Tuotos :

Suurin osa poistetaan B-puusta.

Yhteenveto:

  • B Tree on itsestään tasapainottava tietorakenne, joka parantaa tietojen hakua, lisäämistä ja poistamista levyltä.
  • B-puuta säätelee määrätty aste
  • B Puun avaimet ja solmut on järjestetty nousevaan järjestykseen.
  • B-puun hakutoiminto on yksinkertaisin, joka alkaa aina juuresta ja alkaa tarkistaa onko kohde-avain suurempi tai pienempi kuin solmun arvo.
  • B-puun lisäysoperaatio on melko yksityiskohtainen, joka ensin löytää sopivan lisäyskohteen kohdeavaimelle, lisää sen, arvioi B-puun pätevyyden eri tapausten suhteen ja järjestää sitten B-puun solmut uudelleen.
  • B-puun poistotoiminto etsii ensin poistettavaa kohdeavainta, poistaa sen, arvioi pätevyyden useiden tapausten perusteella, kuten kohdesolmun, sisarusten ja vanhemman vähimmäis- ja enimmäisavaimet.