I den følgende opplæringen vil vi lære om B Tree-datastrukturen og vurdere å visualisere den.
Så la oss komme i gang.
Hva er et B-tre?
De B tre er en spesiell type flerveis søketre , ofte kjent som M-veis tre, som balanserer seg selv. På grunn av deres balanserte struktur, blir disse trærne ofte brukt til å drive og administrere enorme databaser og forenkle søk. I et B-tre kan hver node ha maksimalt n underordnede noder. B Tree er et eksempel på Multilevel Indexing i et Database Management System (DBMS). Blad- og interne noder vil begge ha postreferanser. B Tree er kjent som Balanced Stored Tree fordi alle bladnodene er på samme nivå.
Følgende diagram er et eksempel på et B-tre:
Figur 1. A B-tre med rekkefølge 3
Forstå reglene for B-treet
Følgende er de viktige egenskapene til et B-tre:
- Alle bladnodene er på samme nivå.
- B-treets datastruktur er definert av begrepet minimumsgrad 'd'. Verdien av 'd' avhenger av størrelsen på diskblokken.
- Hver node, unntatt roten, må bestå av minst d-1-nøkler. Rotnoden kan bestå av minimum 1 nøkkel.
- Alle noder (inkludert rotnoden) kan maksimalt bestå av (2d-1) nøkler.
- Antall barn til en node er lik tillegg av antall nøkler som finnes i den og .
- Alle nøklene til en node er sortert i stigende rekkefølge. Barnet mellom to nøkler, k1 og k2, består av alle nøklene som strekker seg mellom henholdsvis k1 og k2.
- I motsetning til det binære søketreet, vokser B-treets datastruktur og krymper fra roten. Mens det binære søketreet vokser nedover og krymper nedover.
- I likhet med andre selvbalanserte binære søketrær, er tidskompleksiteten til B-treets datastruktur for operasjoner som søking, innsetting og sletting O(log?n) .
- Innsetting av en node i B-treet skjer bare ved bladnoden.
La oss vurdere følgende eksempel på et B-tre med minimumsrekkefølge 5.
nummerering av alfabetet
Figur 2. A B Ordenstre 5
Merk: Verdien av minimumsbestillingen er mye mer enn 5 i en praktisk B-trær.
I diagrammet ovenfor kan vi observere at alle bladnodene er på samme nivå, og alle ikke-bladnodene har ingen tomt undertre og består av nøkler en mindre enn antall barn.
Den angitte formuleringen av B Tree-reglene:
Hvert B-tre er avhengig av et positivt konstant heltall kjent som MINIMUM , som brukes for å bestemme antall dataelementer som kan holdes i en enkelt node.
Regel 1: Roten kan ha så få som bare ett dataelement (eller til og med ingen dataelementer hvis den heller ikke er underordnede); annenhver node har minst MINIMUM dataelementer.
Regel 2: Maksimalt antall dataelementer som er lagret i en node er to ganger verdien av MINIMUM .
Regel 3: Dataelementene til hver node i B-treet er lagret i en delvis fylt matrise, sortert fra det minste dataelementet (ved indeks 0 ) til det største dataelementet (ved den endelige brukte posisjonen til matrisen).
Regel 4: Det totale antallet undertrær under en node uten blader er alltid én mer enn antallet dataelementer i den noden.
- undertre 0, undertre 1,...
Regel 5: Med hensyn til enhver node uten blader:
- Et dataelement ved indeks er større enn alle dataelementene i undertrenummer Jeg av noden, og
- Et dataelement ved indeks er mindre enn alle dataelementene i undertrenummer i+1 av noden.
Regel 6: Hvert blad i et B-tre har samme dybde. Dermed sikrer det at et B-tre forhindrer problemet med et ubalansert tre.
Operasjoner på en B-tre-datastruktur
For å sikre at ingen av egenskapene til en B-tre-datastruktur blir krenket under operasjonene, kan B-treet deles eller slås sammen. Følgende er noen operasjoner som vi kan utføre på et B-tre:
- Søke etter et dataelement i B Tree
- Innsetting av et dataelement i B Tree
- Sletting av et dataelement i B Tree
Søkeoperasjon på et B-tre
Å søke etter et element i et B-tre ligner på det i et binært søketre. Men i stedet for å ta en toveis avgjørelse (venstre eller høyre) som et binært søketre, tar et B-tre en m-veis avgjørelse ved hver node der m er antall barn til noden.
Trinn for å søke etter et dataelement i et B-tre:
vba
Trinn 1: Søket starter fra rotnoden. Sammenlign søkeelementet, k, med roten.
Trinn 1.1: Hvis rotnoden består av elementet k, vil søket være fullført.
Trinn 1.2: Hvis elementet k er mindre enn den første verdien i roten, vil vi flytte til barnet lengst til venstre og søke barnet rekursivt.
Trinn 1.3.1: Hvis roten bare har to barn, flytter vi til barnet lengst til høyre og søker rekursivt i barnenodene.
Trinn 1.3.2: Hvis roten har mer enn to nøkler, søker vi i resten.
Steg 2: Hvis elementet k ikke blir funnet etter å ha krysset hele treet, er søkeelementet ikke til stede i B-treet.
La oss visualisere trinnene ovenfor ved hjelp av et eksempel. Anta at vi ønsket å søke etter en nøkkel k=34 i følgende B-tre:
Figur 3.1. Et gitt B-tre
- Først vil vi sjekke om nøkkelen k = 34 er ved rotnoden. Siden nøkkelen ikke er ved roten, vil vi gå videre til dens underordnede noder. Vi kan også observere at rotnoden har to barn; derfor vil vi sammenligne den nødvendige verdien mellom de to tastene.
Figur 3.2. Nøkkelen k er ikke til stede ved roten - Nå som vi kan legge merke til at nøkkelen k er større enn rotnoden, dvs. 30, vil vi fortsette med det riktige barnet til roten.
Figur 3.3. Tasten k > 30, flytt til høyre barn - Vi vil nå sammenligne nøkkelen k med verdiene som er tilstede på noden, dvs. henholdsvis 40 og 50. Siden nøkkelen k er mindre enn venstre nøkkel, dvs. 40, vil vi flytte til venstre underordnede av noden.
Figur 3.4. Nøkkelen k<40, move to left child< li> - Siden verdien i det venstre barnet på 40 er 34, som er den nødvendige verdien, kan vi konkludere med at nøkkelen er funnet, og søkeoperasjonen er fullført.
Figur 3.4. Nøkkelen k = 34, venstre barn på 40
Vi sammenlignet nøkkelen med fire forskjellige verdier i eksemplet ovenfor til vi fant den. Dermed er tidskompleksiteten som kreves for søkeoperasjonen i et B-tre O(log?n) .
Sette inn operasjon på et B-tre
Når vi setter inn et dataelement i et B-tre, må vi først sjekke om det elementet allerede er til stede i treet eller ikke. Hvis dataelementet finnes i B-treet, skjer ikke innsettingsoperasjonen. Men hvis det ikke er tilfelle, går vi videre med innsettingen. Det er to scenarier som må tas vare på mens du setter inn et element i bladnoden:
Trinn for å sette inn et dataelement i et B-tre:
Trinn 1: Vi vil starte med å beregne maksimalt antall nøkler i noden på grunnlag av rekkefølgen til B-treet.
Steg 2: Hvis treet er tomt, tildeles en rotnode, og vi vil sette inn nøkkelen som fungerer som rotnoden.
Trinn 3: Vi vil nå søke i den aktuelle noden for innsetting.
.net veiledning
Trinn 4: Hvis noden er full:
Trinn 4.1: Vi vil sette inn dataelementene i stigende rekkefølge.
Trinn 4.2: Hvis dataelementene er større enn maksimalt antall nøkler, deler vi hele noden ved medianen.
Trinn 4.3: Vi vil skyve mediantasten oppover og dele venstre og høyre tast som venstre og høyre barn.
Trinn 5: Hvis noden ikke er full, vil vi sette inn noden i stigende rekkefølge.
La oss visualisere trinnene ovenfor ved hjelp av et eksempel. Anta at vi må lage et B-tre av orden 4. Dataelementene som må settes inn i B-treet er 5,3,21,11,1,16,8,13,4 og 9 .
- Siden m er lik 3, er det maksimale antall nøkler for en node = m-1 = 3-1 = 2 .
- Vi starter med å sette inn 5 i det tomme treet.
Figur 4.1. Setter inn 5 - Vi skal nå sette inn 3 i treet. Siden 3 er mindre enn 5, vil vi sette inn 3 til venstre for 5 i samme node.
Figur 4.2. Setter inn 3 - Vi skal nå sette inn 21 i treet, og siden 21 er større enn 5, vil den settes inn til høyre for 5 i samme node. Men siden vi vet at maksimalt antall nøkler i noden er 2, vil en av disse nøklene bli flyttet til en node ovenfor for å dele den. Dermed vil 5, det midterste dataelementet, bevege seg opp, og 3 og 21 vil bli henholdsvis venstre og høyre noder.
Figur 4.3. Setter inn 21 - Nå er det på tide å sette inn det neste dataelementet, dvs. 11, som er større enn 5 men mindre enn 21. Derfor vil 11 bli satt inn som en nøkkel til venstre for noden som består av 21 som en nøkkel.
Figur 4.4. Setter inn 11 - På samme måte vil vi sette inn neste dataelement 1 i treet, og som vi kan observere, er 1 mindre enn 3; derfor vil den settes inn som en nøkkel til venstre for noden bestående av 3 som en nøkkel.
Figur 4.5. Setter inn 1 - Nå vil vi sette inn dataelement 16 i treet, som er større enn 11 men mindre enn 21. Imidlertid overskrider antallet nøkler i den noden det maksimale antallet nøkler. Derfor vil noden dele seg og flytte den midterste nøkkelen til roten. Derfor vil 16 bli satt inn til høyre for de 5, og dele 11 og 21 i to separate noder.
Figur 4.6. Setter inn 16 - Dataelementet 8 vil bli satt inn som en nøkkel til venstre for 11.
Figur 4.7. Setter inn 8 - Vi vil sette inn 13 i treet, som er mindre enn 16 og større enn 11. Derfor bør dataelement 13 settes inn til høyre for noden som består av 8 og 11. Men siden maksimalt antall nøkler i treet kan bare være 2, vil en splitt finne sted som flytter det midtre dataelementet 11 til noden ovenfor og 8 og 13 til to separate noder. Nå vil noden ovenfor bestå av 5, 11 og 16, som igjen overskrider det maksimale nøkkelantallet. Derfor vil det være en annen splittelse, som gjør dataelementet 11 til rotnoden med 5 og 16 som underordnede.
Figur 4.8. Setter inn 13 - Siden dataelementet 4 er mindre enn 5, men større enn 3, vil det settes inn til høyre for noden som består av 1 og 3, som vil overskride maksimalt antall nøkler i en node igjen. Derfor vil et utslipp oppstå igjen, og flytte 3-en til den øvre noden ved siden av 5.
Figur 4.9. Setter inn 4 - Til slutt vil dataelementet 9, som er større enn 8 men mindre enn 11, settes inn til høyre for noden som består av 8 som en nøkkel.
Figur 4.10. Setter inn 9
I eksemplet ovenfor har vi utført forskjellige sammenligninger. Den første verdien ble satt direkte inn i treet; etter det måtte hver verdi sammenlignes med nodene tilgjengelig i det treet. Tidskompleksiteten for innsettingsoperasjonen i et B-tre avhenger av antall noder og .
Slette operasjon på et B-tre
Sletting av et dataelement på et B-tre inneholder tre primære hendelser:
- Søker på noden der nøkkelen som skal slettes finnes,
- Sletting av nøkkel, og
- Balansere treet, om nødvendig.
Når du sletter et element fra treet, kan det oppstå en tilstand kjent som underflyt. Underflyt oppstår når en node består av mindre enn minimumsantallet av nøkler; det skal holde.
Følgende er noen begreper som kreves for å bli forstått før du visualiserer slettings-/fjerningsoperasjonen:
Følgende er tre fremtredende tilfeller av sletteoperasjonen i et B-tre:
Tilfelle 1: Sletting/fjerning av nøkkelen ligger i Leaf-noden - Denne saken er videre delt inn i to forskjellige saker:
1. Sletting/fjerning av nøkkelen bryter ikke egenskapen til minimumsantallet av nøkler en node skal inneholde.
La oss visualisere dette tilfellet ved å bruke et eksempel hvor vi vil slette nøkkel 32 fra følgende B-tre.
Figur 4.1: Sletting av en bladnodenøkkel (32) fra B-treet
Som vi kan observere, bryter sletting av 32 fra dette treet ikke egenskapen ovenfor.
2. Sletting/fjerning av nøkkelen bryter egenskapen til minimum antall nøkler en node skal inneholde. I dette tilfellet må vi låne en nøkkel fra dens nærmeste søskennode i rekkefølgen fra venstre til høyre.
Først skal vi besøke den nærmeste venstresøsken. Hvis den venstre søskennoden har mer enn et minimum antall nøkler, vil den låne en nøkkel fra denne noden.
koblet liste java
Ellers vil vi sjekke for å låne fra den nærmeste høyre søskennoden.
La oss nå visualisere dette tilfellet ved hjelp av et eksempel hvor vi vil slette 31 fra B-treet ovenfor. Vi vil låne en nøkkel fra venstre søskennode i dette tilfellet.
Figur 4.2: Sletting av en bladnodenøkkel (31) fra B-treet
Hvis begge de nærliggende søskennodene allerede består av et minimum antall nøkler, vil vi slå sammen noden med enten den venstre søskennoden eller den høyre. Denne sammenslåingsprosessen gjøres gjennom den overordnede noden.
La oss visualisere igjen ved å slette nøkkelen 30 fra B-treet ovenfor.
streng i char java
Figur 4.3: Sletting av en bladnodenøkkel (30) fra B-treet
Tilfelle 2: Sletting/fjerning av nøkkelen ligger i non-Leaf-noden - Denne saken er videre delt inn i forskjellige saker:
1. Noden som ikke er blad/intern, som fjernes, erstattes av en forgjenger i rekkefølge hvis den venstre underordnede noden har mer enn minimum antall nøkler.
La oss visualisere dette tilfellet ved å bruke et eksempel der vi vil slette nøkkelen 33 fra B-treet.
Figur 4.4: Sletting av en bladnodenøkkel (33) fra B-treet
2. Den ikke-blad/interne noden, som fjernes, erstattes av en etterfølger i rekkefølge hvis den høyre underordnede noden har mer enn minimum antall nøkler.
Hvis et av barna har et minimum antall nøkler, vil vi slå sammen venstre og høyre barnenoder.
La oss visualisere dette tilfellet ved å slette nøkkelen 30 fra B-treet.
Figur 4.5: Sletting av en bladnodenøkkel (30) fra B-treet
Etter sammenslåing, hvis foreldrenoden har mindre enn minimumsantallet av nøkler, kan man se etter søsken, som i Sak 1 .
Tilfelle 3: I det følgende tilfellet krymper treets høyde. Hvis målnøkkelen ligger i en intern node, og fjerning av nøkkelen fører til færre nøkler i noden (som er mindre enn minimum som er nødvendig), så se etter forgjengeren i rekkefølge og etterfølgeren i rekkefølge. Hvis begge barna har et minimum antall nøkler, kan ikke lånes skje. Dette leder til Sak 2(3) , dvs. slå sammen barnenodene.
Vi skal igjen se etter søsken for å låne nøkkel. Men hvis søsken også består av et minimum antall nøkler, vil vi slå sammen noden med søsken sammen med overordnet node og ordne barnenodene i henhold til kravene (stigende rekkefølge).
La oss visualisere dette tilfellet ved hjelp av et eksempel hvor vi vil slette dataelementet 10 fra det gitte B-treet.
Figur 4.6: Sletting av en bladnodenøkkel (10) fra B-treet
Tidskompleksiteten i eksemplene ovenfor varierer avhengig av stedet der nøkkelen må slettes. Dermed er tidskompleksiteten for sletteoperasjonen i et B-tre O(log?n) .
Konklusjonen
I denne opplæringen har vi lært om B-treet og visualisert dets forskjellige operasjoner med forskjellige eksempler. Vi har også forstått noen grunnleggende egenskaper og regler for B-treet.