B DRVO u strukturi podataka: Primjer operacije pretraživanja, umetanja i brisanja

Sadržaj:

Anonim

Što je B stablo?

B Tree je samobalansirajuća struktura podataka koja se temelji na određenom skupu pravila za brže traženje, umetanje i brisanje podataka te memorijski učinkovit način. Da bi se to postiglo slijede sljedeća pravila za stvaranje B stabla.

B-stablo je posebna vrsta stabla u strukturi podataka. 1972. ovu je metodu prvi predstavio McCreight, a Bayer ju je nazvao Height Balanced m-way Search Tree. Pomaže vam u očuvanju sortiranih podataka i dopuštenih raznih operacija poput umetanja, pretraživanja i brisanja za manje vremena.

U ovom vodiču za B-Tree naučit ćete:

  • Što je B stablo?
  • Zašto koristiti B-Tree
  • Povijest stabla B
  • Operacija pretraživanja
  • Umetni rad
  • Izbriši operaciju

Pravila za B-Tree

Ovdje su važna pravila za stvaranje B_Tree

  • Svi listovi bit će stvoreni na istoj razini.
  • B-stablo određuje se brojem stupnjeva, koji se naziva i "redoslijedom" (određuje ga vanjski glumac, poput programera), koji se naziva 
    m
    pa nadalje. Vrijednost 
    m
    ovisi o veličini bloka na disku na kojem se primarno nalaze podaci.
  • Lijevo podstablo čvora imat će manje vrijednosti od desne strane podstabla. To znači da se čvorovi također sortiraju u uzlaznom slijedu slijeva udesno.
  • Maksimalni broj podređenih čvorova, korijenski čvor i njegovih podređenih čvorova može se izračunati prema ovoj formuli: 
    m - 1
    Na primjer: 
    m = 4max keys: 4 - 1 = 3

  • Svaki čvor, osim korijena, mora sadržavati najmanje ključeva od 
    [m/2]-1
    Na primjer: 
    m = 4min keys: 4/2-1 = 1
  • Maksimalni broj podređenih čvorova koje čvor može imati jednak je njegovom stupnju, koji je 
    m
  • Minimalna podređena vrijednost čvora može biti polovica narudžbe, što je m / 2 (uzima se gornja vrijednost).
  • Svi su ključevi u čvoru poredani u porastu.

Zašto koristiti B-Tree

Evo razloga za upotrebu B-Treea

  • Smanjuje broj čitanja na disku
  • B Stabla se mogu lako optimizirati kako bi prilagodila svoju veličinu (to je broj podređenih čvorova) prema veličini diska
  • To je posebno dizajnirana tehnika za rukovanje glomaznom količinom podataka.
  • To je koristan algoritam za baze podataka i datotečne sustave.
  • Dobar izbor za čitanje i pisanje velikih blokova podataka

Povijest stabla B

  • Podaci se pohranjuju na disk u blokovima, a ti se podaci, kada se unesu u glavnu memoriju (ili RAM), nazivaju strukturom podataka.
  • U slučaju ogromnih podataka, za pretraživanje jednog zapisa na disku potrebno je čitav disk; ovo povećava vrijeme i potrošnju glavne memorije zbog velike frekvencije pristupa disku i veličine podataka.
  • Da bi se to prevladalo, kreiraju se indeksne tablice koje spremaju referencu zapisa na temelju blokova u kojima se nalaze. To drastično smanjuje vrijeme i potrošnju memorije.
  • Budući da imamo ogromne podatke, možemo stvoriti indeksne tablice na više razina.
  • Višerazinski indeks može se dizajnirati pomoću B Tree za održavanje sortiranih podataka na samobalansirajući način.

Operacija pretraživanja

Operacija pretraživanja je najjednostavnija operacija na B Treeu.

Primjenjuje se sljedeći algoritam:

  • Neka ključ (vrijednost) pretražuje "k".
  • Počnite pretraživati ​​od korijena i rekurzivno kretati prema dolje.
  • Ako je k manja od korijenske vrijednosti, pretražite lijevo podstablo, ako je k veća od korijenske vrijednosti, pretražite desno poddrvo.
  • Ako čvor ima pronađeni k, jednostavno ga vratite.
  • Ako k nije pronađen u čvoru, prijeđite do djeteta većim ključem.
  • Ako k nije pronađen u stablu, vratit ćemo NULL.

Umetni rad

Budući da je B stablo samobalansirajuće stablo, ne možete prisilno umetnuti ključ u bilo koji čvor.

Primjenjuje se sljedeći algoritam:

  • Pokrenite operaciju pretraživanja i pronađite odgovarajuće mjesto umetanja.
  • Umetnite novi ključ na odgovarajuće mjesto, ali ako čvor već ima maksimalan broj ključeva:
  • Čvor će se zajedno s novo umetnutim ključem odvojiti od srednjeg elementa.
  • Srednji element postat će roditelj za druga dva podređena čvora.
  • Čvorovi moraju preurediti ključeve u rastućem redoslijedu.

SAVJET

Sljedeće ne vrijedi za algoritam umetanja:

Budući da je čvor pun, zato će se podijeliti, a zatim će se umetnuti nova vrijednost

U gornjem primjeru:

  • Potražite ključ na odgovarajućem položaju u čvoru
  • Umetnite ključ u ciljni čvor i provjerite ima li pravila
  • Nakon umetanja, ima li čvor više nego jednak minimalnom broju ključeva, što je 1? U ovom slučaju, da, ima. Provjerite sljedeće pravilo.
  • Nakon umetanja, ima li čvor više od maksimalnog broja tipki, što je 3? U ovom slučaju ne. To znači da B stablo ne krši nijedno pravilo i da je umetanje završeno.

U gornjem primjeru:

  • Čvor je dosegao maksimalan broj ključeva
  • Čvor će se podijeliti, a srednji će ključ postati korijenski čvor preostala dva čvora.
  • U slučaju parnog broja tipki, srednji čvor odabrat će se lijevom ili desnom pristranošću.

U gornjem primjeru:

  • Čvor ima manje od maksimalnih tipki
  • 1 se umeće pored 3, ali krši se pravilo rastućeg reda
  • Da bi se to popravilo, tipke se sortiraju

Slično tome, 13 i 2 mogu se lako umetnuti u čvor jer ispunjavaju pravilo ključeva manje od maksimuma za čvorove.

U gornjem primjeru:

  • Čvor ima ključeve jednake maksimalnim ključevima.
  • Ključ je umetnut u ciljni čvor, ali krši pravilo maks. Ključeva.
  • Ciljni čvor je podijeljen, a srednji ključ s lijeve pristranosti sada je roditelj novih podređenih čvorova.
  • Novi čvorovi poredani su uzlaznim redoslijedom.

Slično tome, na temelju gornjih pravila i slučajeva, ostale se vrijednosti mogu jednostavno umetnuti u B stablo.

Izbriši operaciju

Operacija brisanja ima više pravila od operacija umetanja i pretraživanja.

Primjenjuje se sljedeći algoritam:

  • Pokrenite operaciju pretraživanja i pronađite ciljni ključ u čvorovima
  • Primijenjena su tri uvjeta na temelju mjesta ciljnog ključa, kao što je objašnjeno u sljedećim odjeljcima

Ako je ciljni ključ u čvoru lista

  • Cilj je u čvoru lista, više od min ključeva.
    • Brisanjem ovoga neće se kršiti svojstvo B Tree
  • Cilj je u čvoru lista, ima najmanje ključnih čvorova
    • Brisanjem ovoga prekršit će se svojstvo B Tree
    • Ciljni čvor može posuditi ključ od neposrednog lijevog čvora ili neposrednog desnog čvora (brata ili sestre)
    • Brat ili sestra će reći da ako ima više od minimalnog broja ključeva
    • Ključ će se posuditi iz nadređenog čvora, maksimalna vrijednost će se prenijeti nadređenom, maksimalna vrijednost nadređenog čvora prenijet će se u ciljni čvor i ukloniti ciljana vrijednost
  • Cilj je u čvoru lista, ali nijedna braća i sestre nemaju više od minimalnog broja ključeva
    • Potražite ključ
    • Spoji se s braćom i sestrama i minimumom roditeljskih čvorova
    • Ukupan broj tipki sada će biti veći od min
    • Ciljni ključ zamijenit će se minimumom nadređenog čvora

Ako je ciljni ključ u unutarnjem čvoru

  • Ili odaberite, prethodnika po redu ili nasljednika po redu
  • U slučaju prethodnika u redoslijedu, bit će odabran maksimalan ključ s njegova lijevog podstabla
  • U slučaju nasljednika po redoslijedu, odabrat će se minimalni ključ s desnog podstabla
  • Ako prethodnik ciljanog ključa u redoslijedu ima više od min ključeva, samo tada može ciljni ključ zamijeniti maksimumom prethodnika u redoslijedu
  • Ako prethodnik ciljanog ključa po redu nema više od min ključeva, potražite minimalni ključ nasljednika po redu.
  • Ako i prethodnik i nasljednik ciljanog ključa imaju manje od min ključeva, spojite prethodnika i nasljednika.

Ako je ciljni ključ u korijenskom čvoru

  • Zamijenite s maksimalnim elementom prethodnog podstabla po redu
  • Ako nakon brisanja cilj ima manje od min ključeva, tada će ciljni čvor posuditi maksimalnu vrijednost od svog brata ili sestre preko roditelja sestre.
  • Cilj će uzeti maksimalnu vrijednost roditelja, ali s čvorovima maksimalne vrijednosti brata i sestre.

Sada, shvatimo operaciju brisanja na primjeru.

Gornji dijagram prikazuje različite slučajeve postupka brisanja u B-stablu. Ovo B-stablo je reda 5, što znači da je najmanji broj podređenih čvorova koji bilo koji čvor može imati 3, a maksimalni broj podređenih čvorova koji bilo koji čvor može imati 5. dok je najmanji i maksimalan broj ključeva bilo kojeg čvora mogu imati su 2, odnosno 4.

U gornjem primjeru:

  • Ciljni čvor ima ciljni ključ za brisanje
  • Ciljni čvor ima ključeve više od minimalnih ključeva
  • Jednostavno izbrišite ključ

U gornjem primjeru:

  • Ciljni čvor ima ključeve jednake minimalnim ključevima, pa ga ne možete izravno izbrisati jer će prekršiti uvjete

Sljedeći dijagram objašnjava kako izbrisati ovaj ključ:

  • Ciljni čvor posudit će ključ od neposrednog brata ili sestre, u ovom slučaju, prethodnika po redu (lijevog brata ili sestre) jer nema nijednog nasljednika po redu (desni brat)
  • Maksimalna vrijednost prethodnika inorder bit će prenesena na roditelja, a roditelj će prenijeti maksimalnu vrijednost na ciljni čvor (vidi dijagram u nastavku)

Sljedeći primjer ilustrira kako izbrisati ključ kojem je potrebna vrijednost iz njegovog nasljednika po redu.

  • Ciljni čvor posudit će ključ od neposrednog brata ili sestre, u ovom slučaju, nasljednika po redu (desnog brata ili sestre) jer njegov prethodnik po redu (lijevi brat ili sestra) ima ključeve jednake minimalnim ključevima.
  • Minimalna vrijednost nasljednika po redoslijedu bit će prenesena na roditelja, a roditelj će prenijeti maksimalnu vrijednost na ciljni čvor.

U primjeru u nastavku, ciljni čvor nema brata ili sestru koji mogu dati svoj ključ ciljnom čvoru. Stoga je potrebno spajanje.

Pogledajte postupak brisanja takvog ključa:

  • Spoji ciljni čvor s bilo kojim od njegovih neposrednih braće i sestara zajedno s roditeljskim ključem
    • Odabran je ključ nadređenog čvora koji se braća i sestre nalaze između dva čvora koja se spajaju
  • Izbrišite ciljni ključ iz spojenog čvora

Izbrišite pseudo kod operacije

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}}

Izlaz :

Najveći se element briše s B-stabla.

Sažetak:

  • B Tree je samobalansirajuća struktura podataka za bolje pretraživanje, umetanje i brisanje podataka s diska.
  • B Stablo je regulirano navedenim stupnjem
  • B Tipke i čvorovi stabla poredani su u rastućem redoslijedu.
  • Operacija pretraživanja B stabla je najjednostavnija, koja uvijek započinje od korijena i započinje provjeru je li ciljni ključ veći ili manji od vrijednosti čvora.
  • Operacija umetanja B stabla prilično je detaljna, koja prvo pronalazi odgovarajući položaj umetanja za ciljni ključ, ubacuje ga, procjenjuje valjanost B stabla u odnosu na različite slučajeve, a zatim restrukturira čvorove B stabla u skladu s tim.
  • Operacija brisanja B stabla prvo traži ciljni ključ koji se želi izbrisati, briše ga, procjenjuje valjanost na temelju nekoliko slučajeva poput minimalnog i maksimalnog ključa ciljnog čvora, braće i sestara i roditelja.