b tree b tree data structure c
Denne C ++ opplæringen forklarer B-treet og B + -datastrukturene. De brukes til å lagre data på disker når hele dataene ikke kan lagres i hovedminnet:
B-tree er et selvbalansert tre i tillegg til et spesialisert m-way-tre som brukes til disktilgang.
Når datamengden som skal lagres er veldig høy, kan vi ikke lagre hele dataene i hovedminnet. Derfor lagrer vi data på disken. Datatilgang fra disken tar mer tid sammenlignet med hovedminnetilgangen.
Når antallet nøkler til dataene som er lagret på disker er veldig høyt, får du vanligvis tilgang til dataene i form av blokker. Tiden for tilgang til disse blokkene er direkte proporsjonal med høyden på treet.
=> Klikk her for den absolutte C ++ treningsserien.
Hva du vil lære:
B-Tree In C ++
B-treet er et flatt tre, dvs. høyden på B-treet holdes på et minimum. I stedet settes så mange nøkler i hver node på B-treet. Ved å holde høyden på B-treet til et minimum blir tilgangen raskere sammenlignet med andre balanserte trær som AVL-trær.
Et typisk B-tre er vist nedenfor:
nettverksingeniør intervju spørsmål og svar i cisco
Vanligvis holdes nodestørrelsen i B-treet den samme som blokkstørrelsen.
Nedenfor er noen av egenskapene til B-Tree.
- Alle bladene på B-treet er på samme nivå.
- Et B-tre av orden m kan maksimalt ha m-1 nøkler og m barn.
- Hver node i B-treet har høyst m barn.
- Rotnoden må ha minst to noder.
- Hver node unntatt rotnoden og bladnoden inneholder m / 2 barn.
Deretter diskuterer vi noen av de grunnleggende operasjonene til B-treet.
Grunnleggende operasjoner av B-Tree
Nedenfor er noen av de grunnleggende operasjonene til B-Tree.
# 1) Søker
Søking i B-treet ligner på BST. I treet ovenfor, hvis vi vil se etter element 3, vil vi fortsette som følger:
- Sammenlign 3 med rotelementer. Her, 3<6 and 3 <15. So we proceed to the left subtree.
- Sammenlign 3 med 4 i venstre undertreet. Som 3<4, we proceed to the left subtree of node 4.
- Den neste noden har to nøkler, 2 og 3. 3> 2 mens 3 = 3. Så vi har funnet nøkkelen på denne noden. Gå tilbake til stedet du fant.
Søking i B-tre avhenger av høyden på treet. Det tar vanligvis O (log n) tid å søke etter et gitt element.
# 2) Innsetting
Innsettingen av et nytt element i B-treet gjøres på bladnodenivå.
Følgende er trinnsekvensen (algoritme) for å sette inn et nytt element i B-treet.
- Kryss B-treet for å finne et sted ved bladnodene for å sette inn elementet.
- Hvis bladnoden inneholder nøkler
- Ellers hvis bladnodetaster = m-1, så:
- Sett inn et nytt element i et økende antall artikler.
- Ta medianen til nodene og del noden i to noder.
- Skyv medianen til den overordnede noden.
- Hvis foreldrenode nøkkel = m-1, gjenta trinnene ovenfor også for foreldrenoden. Dette gjøres til vi finner riktig bladknute.
- Til slutt setter du inn elementet.
- Ellers hvis bladnodetaster = m-1, så:
Vi har demonstrert innsetting i B-tre som følger.
La oss sette inn element 70 i treet vist nedenfor.
hva brukes c ++ til
Det gitte treet er med minimumsgrad ‘m’ = 3. Derfor kan hver node huse, 2 * m -1 = 5 nøkler inni den.
Nå setter vi inn element 70. Da vi kan ha 5 nøkler i en node, sammenligner vi element 70 med rotelementet 30. Siden 70> 30 vil vi sette inn element 70 i høyre undertrær.
I høyre undertreet har vi en node med nøklene 40, 50, 60. Siden hver node kan ha 5 nøkler, vil vi sette inn elementet 70 i selve denne noden.
Etter innsetting ser B-treet ut som følger.
# 3) Sletting
Akkurat som innsetting, blir sletting av nøkkelen også utført på nivå av bladnoder. Men i motsetning til innsetting er sletting mer komplisert. Nøkkelen som skal slettes kan være enten en bladnode eller en intern node.
For å slette en nøkkel følger vi trinnene nedenfor (algoritme).
1. Finn bladknuten.
to. Hvis antall nøkler i en node> m / 2, så slett den gitte nøkkelen fra noden.
3. Hvis bladnoden ikke har m / 2-nøkler, må vi fullføre nøklene ved å ta nøklene fra høyre eller venstre undertrær for å opprettholde B-treet.
Vi følger disse trinnene:
- Hvis venstre undertre inneholder m / 2-elementer, skyver vi det største elementet til foreldrenoden og flytter deretter det mellomliggende elementet til stedet der nøkkelen ble slettet.
- Hvis det høyre undertreet inneholder m / 2-elementer, skyver vi det minste elementet til foreldrenoden og flytter deretter det mellomliggende elementet til stedet der nøkkelen ble slettet.
Fire. Hvis ingen noder har m / 2 noder, kan ikke trinnene ovenfor utføres, og dermed oppretter vi en ny bladnode ved å forbinde to bladnoder og det mellomliggende elementet i foreldrenoden.
5. Hvis en forelder er uten m / 2 noder, gjentar vi trinnene ovenfor for den aktuelle foreldrenoden. Disse trinnene gjentas til vi får et balansert B-tre.
Nedenfor er en illustrasjon for å slette en node fra B-treet.
Tenk på følgende B-tre igjen.
La oss anta at vi vil slette nøkkelen 60 fra B-treet. Hvis vi sjekker B-treet, kan vi finne at nøkkelen som skal slettes, er til stede i bladnoden. Vi sletter nøkkelen 60 fra denne bladnoden.
Nå vil treet se ut som vist nedenfor:
Vi kan legge merke til at etter å ha slettet nøkkelen 60, tilfredsstiller B-trebladnoden de nødvendige egenskapene, og vi trenger ikke gjøre flere endringer i B-treet.
Men hvis vi måtte slette nøkkel 20, ville bare nøkkel 10 ha blitt igjen i venstre bladnode. I dette tilfellet må vi skifte rot 30 til bladnoden og flytte nøkkel 40 til roten.
Når du sletter en nøkkel fra B-treet, bør du derfor være forsiktig og ikke trekke egenskapene til B-treet.
Traversal In B Tree
Gjennomgang i B-treet ligner også på bestilling i BST. Vi starter rekursivt fra venstre og kommer til roten og fortsetter mot venstre undertre.
Anvendelser av B-trær
- B-trær brukes til å indeksere dataene, spesielt i store databaser, da tilgang til data som er lagret i store databaser på disker er svært tidkrevende.
- Søking av data i større usorterte datasett tar mye tid, men dette kan forbedres betydelig med indeksering ved hjelp av B-treet.
B + Tree In C ++
B + tre er en utvidelse av B treet. Forskjellen i B + tre og B tre er at i B tre kan nøklene og postene lagres så vel interne som bladnoder, mens i B + trær lagres postene som bladnoder og nøklene lagres bare i interne noder.
1nf 2nf 3nf bcnf med eksempel
Postene er knyttet til hverandre på en koblet liste. Denne ordningen gjør søking av B + trær raskere og effektiv. Interne noder i B + -treet kalles indeksnoder.
B + -trærne har to ordrer, dvs. en for interne noder og en for blad- eller eksterne noder.
Et eksempel på B + Tree er vist nedenfor.
Ettersom B + -treet er en utvidelse av B-treet, holder de grunnleggende operasjonene vi diskuterte under emnet B-treet fortsatt.
Mens vi setter inn og sletter, bør vi opprettholde de grunnleggende egenskapene til B + Trees intakte. Sletteoperasjon i B + -treet er imidlertid relativt enklere ettersom dataene bare lagres i bladnodene, og de vil alltid bli slettet fra bladnodene.
Fordeler med B + trær
- Vi kan hente poster i like mange disktilganger.
- Sammenlignet med B-treet er høyden på B + -treet mindre og forblir balansert.
- Vi bruker nøkler til indeksering.
- Data i B + -treet kan nås sekvensielt eller direkte når bladnodene er ordnet i en lenket liste.
- Søk er raskere ettersom data kun er lagret i bladnoder og som en koblet liste.
Forskjellen mellom B-Tree og B + Tree
B-treet | B + tre |
---|---|
Data lagres i bladnoder så vel som interne noder. | Data lagres bare i bladnoder. |
Søking er litt tregere ettersom data lagres i interne så vel som bladnoder. | Søking er raskere ettersom dataene bare lagres i bladnodene. |
Ingen overflødige søketaster er til stede. | Overflødige søketaster kan være til stede. |
Slettingsoperasjonen er kompleks. | Det er enkelt å slette, ettersom data kan slettes direkte fra bladnodene. |
Bladnoder kan ikke kobles sammen. | Bladnoder er koblet sammen for å danne en koblet liste. |
Konklusjon
I denne opplæringen har vi diskutert B-treet og B + treet i detalj. Disse to datastrukturene brukes når det er veldig mye datamengde, og når hele dataene ikke kan lagres i hovedminnet. Dermed for å lagre data på disker, bruker vi B-tre og B + tre.
B-tre-søk er litt tregere ettersom dataene er lagret i interne noder så vel som bladnoder i den. B + -treet er en utvidelse av B-treet, og dataene her lagres bare i bladnoder. På grunn av denne faktoren er det raskere og effektivt å søke i et B + -tre.
=> Besøk her for den komplette C ++ opplæringslisten.
Anbefalt lesing
- AVL Tree and Heap Datastruktur i C ++
- Koblet liste Datastruktur i C ++ med illustrasjon
- Kødatastruktur i C ++ med illustrasjon
- Stakk datastruktur i C ++ med illustrasjon
- Sirkulær sammenkoblet liste Datastruktur i C ++ med illustrasjon
- Introduksjon til datastrukturer i C ++
- Prioritert kødatastruktur i C ++ med illustrasjon
- Dobbeltkoblet listedatastruktur i C ++ med illustrasjon