B Tree og B + Tree Datastruktur i C ++

b tree b tree data structure c

Denne C ++ -vejledning forklarer B Tree & B + Tree-datastrukturer. De bruges til at gemme data på diske, når de samlede data ikke kan gemmes i hovedhukommelsen:

B-tree er et selvbalanceret træ såvel som et specialiseret m-way træ, der bruges til diskadgang.

Når mængden af ​​data, der skal lagres, er meget høj, kan vi ikke gemme hele dataene i hovedhukommelsen. Derfor lagrer vi data på disken. Dataadgang fra disken tager mere tid sammenlignet med hovedhukommelsesadgangen.

Når antallet af nøgler til de data, der er gemt på diske, er meget højt, er der normalt adgang til dataene i form af blokke. Tiden til adgang til disse blokke er direkte proportional med træets højde.

=> Klik her for den absolutte C ++ træningsserie.

Hvad du lærer:

• B-Tree I C ++
  • Grundlæggende funktioner i B-Tree
    • # 1) Søgning
    • # 2) Indsættelse
    • # 3) Sletning
  • Anvendelser af B-træer
• B + træ i C ++
  • Fordele ved B + træer
• Forskellen mellem B-Tree og B + Tree
• Konklusion
  • Anbefalet læsning

B-Tree I C ++

B-træet er et fladt træ, dvs. B-træets højde holdes på et minimum. I stedet placeres så mange nøgler i hver node i B-træet. Ved at minimere B-træets højde er adgangen hurtigere sammenlignet med andre afbalancerede træer som AVL-træer.

Et typisk B-træ er vist nedenfor:

bedste videospilvirksomheder til at arbejde i 2018

Generelt holdes nodestørrelsen i B-træet den samme som blokstørrelsen.

Nedenfor er nogle af egenskaberne ved B-Tree.

• Alle blade af B-træet er på samme niveau.
• Et B-træ af ordren m kan højst have m-1 nøgler og m børn.
• Hver knude i B-træet har højst m børn.
• Rodknudepunktet skal have mindst to noder.
• Hver knude undtagen rodknudepunktet og bladknudepunktet indeholder m / 2 børn.

Dernæst diskuterer vi nogle af de grundlæggende operationer af B-tree.

Grundlæggende funktioner i B-Tree

Nedenfor er nogle af de grundlæggende operationer i B-Tree.

# 1) Søgning

Søgning i B-træ svarer til det i BST. I ovenstående træ, hvis vi vil kigge efter element 3, fortsætter vi som følger:

• Sammenlign 3 med rodelementer. Her, 3<6 and 3 <15. So we proceed to the left subtree.
• Sammenlign 3 med 4 i venstre undertræ. Som 3<4, we proceed to the left subtree of node 4.
• Den næste node har to nøgler, 2 og 3. 3> 2, mens 3 = 3. Så vi har fundet nøglen ved denne node. Gå tilbage til det fundne sted.

Søgning i B-træ afhænger af træets højde. Det tager normalt O (log n) tid at søge efter en given vare.

# 2) Indsættelse

Indsættelsen af ​​et nyt element i B-træet sker på bladnoderniveau.

Følgende er rækkefølgen af ​​trin (algoritme) for at indsætte et nyt element i B-træet.

• Kryds B-træet for at finde en placering ved bladknudepunkterne for at indsætte elementet.
• Hvis bladnoden indeholder nøgler
• Ellers hvis bladknudetaster = m-1, så:
  • Indsæt et nyt emne i et stigende antal emner.
  • Tag medianen af ​​knudepunkterne og del knuden i to knudepunkter.
  • Skub median til dets overordnede knude.
  • Hvis overordnet knudepunktnøgle = m-1, gentages ovenstående trin også for overordnet knudepunkt. Dette gøres, indtil vi finder den rette bladknude.
• Indsæt endelig elementet.

Vi har demonstreret indsættelse i B-træ som følger.

Lad os indsætte punkt 70 i træet vist nedenfor.

hvad bruges c ++ til

Det givne træ er med minimumsgraden 'm' = 3. Derfor kan hver node rumme, 2 * m -1 = 5 nøgler inde i den.

Nu indsætter vi element 70. Da vi kan have 5 nøgler i en node, sammenligner vi element 70 med rodelementet 30. Siden 70> 30 indsætter vi element 70 i det rigtige undertræ.

I det højre undertræ har vi en node med nøglerne 40, 50, 60. Da hver node kan have 5 nøgler i sig, indsætter vi elementet 70 i selve denne node.

Efter indsættelse ser B-træet ud som følger.

# 3) Sletning

Ligesom indsættelse udføres sletningen af ​​nøglen også på niveau med bladnoder. Men i modsætning til indsættelse er sletning mere kompliceret. Den nøgle, der skal slettes, kan enten være en bladknude eller en intern knude.

For at slette en nøgle følger vi nedenstående rækkefølge af trin (algoritme).

1. Find bladknuden.

2. Hvis antallet af nøgler i en node> m / 2 skal du slette den givne nøgle fra noden.

3. Hvis bladknudepunktet ikke har m / 2-nøgler, skal vi udfylde tasterne ved at tage nøgler fra højre eller venstre undertræ for at opretholde B-træet.

Vi følger disse trin:

• Hvis det venstre undertræ indeholder m / 2-elementer, skubber vi dets største element til den overordnede knude og flytter derefter det mellemliggende element til det sted, hvor nøglen blev slettet.
• Hvis det rigtige undertræ indeholder m / 2-elementer, skubber vi det mindste element til den overordnede knude og flytter derefter det mellemliggende element til det sted, hvor nøglen blev slettet.

Fire. Hvis ingen node har m / 2 noder, kan ovenstående trin ikke udføres, og vi opretter således en ny bladnode ved at forbinde to bladnoder og det mellemliggende element i den overordnede node.

5. Hvis en forælder er uden m / 2 noder, gentager vi ovenstående trin for den pågældende forældrenode. Disse trin gentages, indtil vi får et afbalanceret B-træ.

Nedenfor er en illustration til at slette en node fra B-træet.

Overvej følgende B-træ igen.

Lad os antage, at vi vil slette nøglen 60 fra B-træet. Hvis vi kontrollerer B-træet, kan vi finde ud af, at nøglen, der skal slettes, findes i bladnoden. Vi sletter nøglen 60 fra denne bladknude.

Nu ser træet ud som vist nedenfor:

Vi kan bemærke, at B-træbladknudepunktet efter sletning af nøglen 60 opfylder de krævede egenskaber, og vi behøver ikke foretage flere ændringer af B-træet.

Men hvis vi skulle slette nøgle 20, ville kun nøgle 10 være tilbage i venstre bladknude. I dette tilfælde bliver vi nødt til at skifte rod 30 til bladnoden og flytte nøgle 40 til roden.

Når man sletter en nøgle fra B-træet, skal man derfor være forsigtig, og B-træets egenskaber bør ikke krænkes.

Traversal In B Tree

for at generere et tilfældigt tal kan du bruge funktionen rand i headerfilen

Traversal i B-træ svarer også til inorder traversal i BST. Vi starter rekursivt fra venstre og kommer derefter til rod og fortsætter mod venstre undertræ.

Anvendelser af B-træer

• B-træer bruges til at indeksere dataene, især i store databaser, da adgang til data, der er gemt i store databaser på diske, er meget tidskrævende.
• Søgning efter data i større usorterede datasæt tager meget tid, men dette kan forbedres betydeligt med indeksering ved hjælp af B-træ.

B + træ i C ++

B + træ er en udvidelse af B-træet. Forskellen i B + -træ og B-træ er, at i B-træ kan nøglerne og optegnelserne gemmes såvel interne som bladnoder, mens i B + -træer opbevares posterne som bladnoder, og nøglerne kun gemmes i interne noder.

Optegnelserne er knyttet til hinanden på en sammenkædet liste måde. Dette arrangement gør søgninger på B + træer hurtigere og effektiv. Interne noder i B + -træet kaldes indeksnoder.

B + træerne har to ordrer, dvs. en for interne noder og en for blade eller eksterne noder.

Et eksempel på B + Tree er vist nedenfor.

Da B + træ er en udvidelse af B-træ, holder de grundlæggende operationer, som vi diskuterede under emnet B-træ, stadig.

Mens vi indsætter såvel som sletning, skal vi opretholde de grundlæggende egenskaber for B + Trees intakte. Sletning i B + -træet er dog forholdsvis lettere, da dataene kun er gemt i bladknudepunkterne, og de slettes altid fra bladknudepunkterne.

Fordele ved B + træer

• Vi kan hente poster i et lige antal diskadgange.
• Sammenlignet med B-træet er B + -træets højde mindre og forbliver afbalanceret.
• Vi bruger nøgler til indeksering.
• Data i B + -træet kan tilgås sekventielt eller direkte, når bladknudepunkterne er arrangeret på en sammenkædet liste.
• Søgning er hurtigere, da data kun er gemt i bladnoder og som en sammenkædet liste.

Forskellen mellem B-Tree og B + Tree

Konklusion

I denne vejledning har vi diskuteret B-træ og B + træ i detaljer. Disse to datastrukturer bruges, når der er en meget stor mængde data, og når hele data ikke kan lagres i hovedhukommelsen. For at gemme data på diske bruger vi således B-træ og B + træ.

B-træ-søgning er lidt langsommere, da dataene er gemt i interne noder såvel som bladnoder i det. B + træ er en udvidelse af B-træ, og dataene her er kun gemt i bladnoder. På grund af denne faktor er søgning i et B + træ hurtigere og effektiv.

=> Besøg her for den komplette C ++ tutorials liste.

Anbefalet læsning

• AVL-træ- og bunndatastruktur i C ++
• Sammenkædet liste datastruktur i C ++ med illustration
• Kø Datastruktur i C ++ med illustration
• Stak datastruktur i C ++ med illustration
• Cirkulær sammenkædet liste Datastruktur i C ++ med illustration
• Introduktion til datastrukturer i C ++
• Prioriteret kø datastruktur i C ++ med illustration
• Dobbelt sammenkædet liste Datastruktur i C ++ med illustration