b tree b tree data structure c
Ovaj vodič za C ++ objašnjava strukture podataka B Tree & B + Tree. Koriste se za pohranu podataka na diskove kada se cjelokupni podaci ne mogu pohraniti u glavnu memoriju:
B-stablo je samobalansirano stablo, kao i specijalizirano m-stablo koje se koristi za pristup disku.
Kada je količina podataka za pohranu vrlo velika, ne možemo pohraniti cijele podatke u glavnu memoriju. Stoga podatke pohranjujemo na disk. Pristup podacima s diska oduzima više vremena u usporedbi s pristupom glavnoj memoriji.
Kada je broj ključeva podataka pohranjenih na diskovima vrlo velik, podacima se obično pristupa u obliku blokova. Vrijeme pristupa tim blokovima izravno je proporcionalno visini stabla.
=> Kliknite ovdje za apsolutnu seriju C ++ treninga.
Što ćete naučiti:
B-stablo u C ++
B-drvo je ravno stablo, tj. Visina B-drveta je minimalna. Umjesto toga, u svaki čvor B-stabla stavlja se toliko ključeva. Držeći visinu B-drveta na minimumu, pristup je brži u usporedbi s ostalim uravnoteženim stablima poput AVL stabala.
Tipično B-stablo prikazano je u nastavku:
proslijediti niz u metodu java
Općenito, veličina čvora u B-stablu zadržava se jednaka veličini bloka.
U nastavku su navedena neka svojstva B-Treea.
- Svi listovi B-stabla su na istoj razini.
- B-stablo reda m može imati najviše m-1 ključeva i m djece.
- Svaki čvor u B-stablu ima najviše m djece.
- Korijenski čvor mora imati najmanje dva čvora.
- Svaki čvor, osim korijenskog i lisnatog, sadrži m / 2 djece.
Zatim ćemo raspraviti neke od osnovnih operacija B-stabla.
Osnovne operacije B-stabla
Slijede neke od osnovnih operacija B-Tree-a.
# 1) Pretraživanje
Pretraživanje u B stablu slično je pretraživanju u BST. Ako želimo potražiti stavku 3 u gornjem stablu, postupit ćemo na sljedeći način:
- Usporedite 3 s korijenskim elementima. Evo, 3<6 and 3 <15. So we proceed to the left subtree.
- Usporedite 3 s 4 u lijevom podstablu. Kao 3<4, we proceed to the left subtree of node 4.
- Sljedeći čvor ima dva ključa, 2 i 3. 3> 2 dok je 3 = 3. Dakle, pronašli smo ključ na ovom čvoru. Vratite se na pronađeno mjesto.
Traženje u B stablu ovisi o visini stabla. Obično treba O (log n) vremena za traženje određene stavke.
# 2) Umetanje
Umetanje nove stavke u stablo B vrši se na razini lisnih čvorova.
Slijedi slijed koraka (algoritam) za umetanje nove stavke u B stablo.
- Pređite drvo B da biste pronašli mjesto na čvorovima listova za umetanje predmeta.
- Ako čvor lista sadrži ključeve
- Inače ako su ključevi čvora lista = m-1, onda:
- Umetnite novu stavku u sve veći broj stavki.
- Uzmite medijanu čvorova i podijelite čvor na dva čvora.
- Gurnite medijan na njegov roditeljski čvor.
- Ako je ključ nadređenog čvora = m-1, ponovite gornje korake i za nadređeni čvor. To se radi sve dok ne pronađemo odgovarajući čvor lišća.
- Na kraju umetnite element.
- Inače ako su ključevi čvora lista = m-1, onda:
Demonstrirali smo umetanje u B stablo kako slijedi.
Umetnimo stavku 70 u dolje prikazano stablo.
Windows 10 zadani pristupnik nije dostupan
Dano je stablo s minimalnim stupnjem 'm' = 3. Dakle, svaki čvor može primiti 2 * m -1 = 5 ključeva unutar njega.
Sada ubacujemo stavku 70. Kako u čvoru možemo imati 5 ključeva, uspoređujemo element 70 s korijenskim elementom 30. Budući da je 70> 30, stavit ćemo stavku 70 u desno podstablo.
U desnom podstablu imamo čvor s ključevima 40, 50, 60. Kako svaki čvor može imati 5 ključeva, umetnut ćemo stavku 70 u sam čvor.
Nakon umetanja, B-stablo izgleda kako slijedi.
# 3) Brisanje
Baš kao i umetanje, brisanje ključa također se vrši na razini čvorova lista. No, za razliku od umetanja, brisanje je složenije. Ključ koji treba izbrisati može biti ili čvor lista ili interni čvor.
Da bismo izbrisali ključ, slijedimo donji slijed koraka (algoritam).
1. Pronađite čvor lišća.
dva. U slučaju da je broj ključeva u čvoru> m / 2, izbrišite dani ključ iz čvora.
3. U slučaju da lisni čvor nema m / 2 ključa, tada moramo dovršiti ključeve uzimajući ključeve s desnog ili lijevog podstabla kako bismo održavali B stablo.
Slijedimo ove korake:
- Ako lijevo podstablo sadrži m / 2 elementa, tada njegov najveći element guramo u nadređeni čvor, a zatim premještamo intervenirajući element na mjesto gdje je ključ izbrisan.
- Ako desno poddrvo sadrži m / 2 elementa, tada njegov najmanji element guramo u nadređeni čvor, a zatim premještamo intervenirajući element na mjesto gdje je ključ izbrisan.
Četiri. Ako niti jedan čvor nema m / 2 čvora, gornji koraci se ne mogu izvesti, pa stoga stvaramo novi čvor čvorišta spajanjem dva čvora čvora i interventnog elementa nadređenog čvora.
5. Ako je roditelj bez m / 2 čvorova, ponavljamo gornje korake za dotični nadređeni čvor. Ovi se koraci ponavljaju sve dok ne dobijemo uravnoteženo B stablo.
Dolje je ilustracija brisanja čvora s B stabla.
Razmotrite još jednom sljedeće B stablo.
najbolji softver za izradu igara za početnike
Pretpostavimo da želimo izbrisati ključ 60 s B stabla. Ako provjerimo stablo B, možemo utvrditi da je ključ koji se želi izbrisati prisutan u čvoru lista. Iz ovog lisnog čvora brišemo ključ 60.
Sada će stablo izgledati kako je prikazano dolje:
Možemo primijetiti da nakon brisanja ključa 60, čvor lista B stabla zadovoljava potrebna svojstva i ne trebamo više mijenjati B stablo.
Međutim, da smo morali izbrisati ključ 20, tada bi samo ključ 10 ostao u lijevom čvoru lista. U ovom bismo slučaju morali pomaknuti korijen 30 na čvor lista i premjestiti ključ 40 na korijen.
Stoga, prilikom brisanja ključa s B stabla, treba biti oprezan i ne bi trebalo kršiti svojstva B stabla.
Prijelaz u B stablu
Prijelaz u B stablu također je sličan prijelazu u BST. Počinjemo rekurzivno s lijeve strane, zatim dolazimo do korijena i nastavljamo prema lijevom podstablu.
Primjene B drveća
- B stabla koriste se za indeksiranje podataka, posebno u velikim bazama podataka, jer je pristup podacima pohranjenim u velikim bazama podataka na diskovima vrlo dugotrajan.
- Traženje podataka u većim nerazvrstanim skupovima podataka oduzima puno vremena, ali to se može značajno poboljšati indeksiranjem pomoću B stabla.
B + stablo u C ++
B + stablo je produžetak B stabla. Razlika u B + stablu i B stablu je u tome što se u B stablu ključevi i zapisi mogu pohraniti kao unutarnji, kao i čvorovi lista, dok se u B + stablima zapisi pohranjuju kao čvorovi lista, a ključevi samo u unutarnje čvorove.
Zapisi su međusobno povezani na način povezanog popisa. Ovaj aranžman čini pretrage stabala B + bržim i učinkovitijim. Interni čvorovi stabla B + nazivaju se indeksni čvorovi.
Stabla B + imaju dva reda, tj. Jedan za unutarnje čvorove, a drugi za lisne ili vanjske čvorove.
Primjer stabla B + prikazan je u nastavku.
Kako je B + stablo produžetak B-stabla, osnovne operacije o kojima smo razgovarali u temi B-stablo i dalje vrijede.
Tijekom umetanja i brisanja trebali bismo održavati osnovna svojstva B + drveća netaknutima. Međutim, operacija brisanja u stablu B + relativno je lakša jer se podaci pohranjuju samo u čvorovima lista i uvijek će se brisati iz čvorova lista.
Prednosti stabala B +
- Zapise možemo dohvatiti u jednakom broju pristupa disku.
- U usporedbi s B stablom, visina B + stabla je manja i ostaje uravnotežena.
- Za indeksiranje koristimo ključeve.
- Podacima u stablu B + može se pristupiti sekvencijalno ili izravno dok su čvorići lista poredani na povezanom popisu.
- Pretraživanje je brže jer se podaci pohranjuju samo u čvorovima listova i kao povezani popis.
Razlika između B-stabla i B + stabla
| B-drvo | B + stablo |
|---|---|
| Podaci se pohranjuju u čvorovima lista, kao i unutarnjim čvorovima. | Podaci se pohranjuju samo u čvorovima lista. |
| Pretraživanje je nešto sporije jer se podaci pohranjuju u unutarnje, kao i u čvorište lista. | Pretraživanje je brže jer se podaci pohranjuju samo u čvorovima lista. |
| Nema suvišnih tipki za pretraživanje. | Možda su prisutne suvišne tipke za pretraživanje. |
| Operacija brisanja je složena. | Brisanje je jednostavno jer se podaci mogu izravno izbrisati iz čvorova lista. |
| Lisni čvorovi ne mogu se međusobno povezati. | Lisni čvorovi povezani su zajedno kako bi stvorili povezani popis. |
Zaključak
U ovom uputstvu detaljno smo razgovarali o B-stablu i B + stablu. Ove se dvije podatkovne strukture koriste kada postoji velika količina podataka i kada se cjelokupni podaci ne mogu pohraniti u glavnu memoriju. Stoga za pohranu podataka na diskove koristimo B-stablo i B + stablo.
Pretraživanje B-stabla nešto je sporije jer se podaci pohranjuju u unutarnje čvorove, kao i u čvorove u njima. B + stablo je produžetak B-stabla i ovdje se podaci pohranjuju samo u čvorovima listova. Zbog ovog čimbenika pretraživanje u B + stablu je brže i učinkovitije.
=> Posjetite ovdje za cjelovit popis tutorijala za C ++.
Preporučena literatura
- Struktura podataka AVL stabla i hrpe u C ++
- Povezana struktura podataka popisa na C ++ s ilustracijom
- Struktura podataka u redu čekanja u C ++ s ilustracijom
- Složite strukturu podataka u C ++ s ilustracijom
- Kružno povezana struktura podataka popisa na C ++ s ilustracijom
- Uvod u strukture podataka na C ++
- Struktura podataka prioritetnog reda u C ++ s ilustracijom
- Dvostruko povezana struktura podataka popisa na C ++ s ilustracijom