Structura de date B Tree și B + Tree în C ++

b tree b tree data structure c

Acest tutorial C ++ explică structurile de date B Tree & B + Tree. Acestea sunt folosite pentru a stoca date pe discuri când datele întregi nu pot fi stocate în memoria principală:

Arborele B este un arbore auto-echilibrat, precum și un arbore specializat în căi m, care este utilizat pentru accesul pe disc.

Când cantitatea de date care trebuie stocată este foarte mare, nu putem stoca întreaga informație în memoria principală. Prin urmare, stocăm date pe disc. Accesul la date de pe disc necesită mai mult timp în comparație cu accesul principal la memorie.

Când numărul de chei al datelor stocate pe discuri este foarte mare, datele sunt de obicei accesate sub formă de blocuri. Timpul pentru accesarea acestor blocuri este direct proporțional cu înălțimea copacului.

=> Faceți clic aici pentru seria Absolute C ++ Training.

Ce veți învăța:

• Arborele B în C ++
  • Operațiuni de bază ale arborelui B.
    • # 1) Căutare
    • # 2) Inserare
    • # 3) Ștergere
  • Aplicații ale copacilor B.
• Arborele B + în C ++
  • Avantajele copacilor B +
• Diferența dintre arborele B și arborele B +
• Concluzie
  • Lectură recomandată

Arborele B în C ++

Arborele B este un arbore plat, adică înălțimea arborelui B este menținută la un nivel minim. În schimb, cât mai multe taste sunt puse în fiecare nod al arborelui B. Menținând înălțimea arborelui B la minimum, accesul este mai rapid în comparație cu alți copaci echilibrați, cum ar fi copacii AVL.

Un copac tipic B este prezentat mai jos:

întrebări și răspunsuri la interviu cu seleniu pdf

În general, dimensiunea nodului în arborele B este păstrată la fel ca dimensiunea blocului.

Mai jos sunt enumerate câteva dintre proprietățile B-Tree.

• Toate frunzele arborelui B sunt la același nivel.
• Un copac B de ordinul m poate avea cel mult m-1 chei și m copii.
• Fiecare nod din arborele B are cel mult m copii.
• Nodul rădăcină trebuie să aibă cel puțin două noduri.
• Fiecare nod, cu excepția nodului rădăcină și a nodului frunzei, conține m / 2 copii.

În continuare, discutăm câteva dintre operațiile de bază ale arborelui B.

Operațiuni de bază ale arborelui B.

Mai jos sunt prezentate câteva dintre operațiile de bază ale B-Tree.

# 1) Căutare

Căutarea în arborele B este similară cu cea din BST. În arborele de mai sus, dacă dorim să căutăm articolul 3, vom proceda după cum urmează:

• Comparați 3 cu elemente rădăcină. Aici, 3<6 and 3 <15. So we proceed to the left subtree.
• Comparați 3 cu 4 în subarborele din stânga. Ca 3<4, we proceed to the left subtree of node 4.
• Următorul nod are două taste, 2 și 3. 3> 2 în timp ce 3 = 3. Deci, am găsit cheia la acest nod. Reveniți la locația găsită.

Căutarea în arborele B depinde de înălțimea arborelui. De obicei, este nevoie de O (jurnal n) mult timp pentru a căuta un anumit articol.

# 2) Inserare

Inserarea unui nou element în arborele B se face la nivelul nodurilor frunzei.

Urmează secvența de pași (algoritm) pentru a insera un element nou în arborele B.

• Parcurgeți arborele B pentru a găsi o locație la nodurile frunzei pentru a insera elementul.
• Dacă nodul frunzei conține chei
• Altfel dacă tastele nodului frunzei = m-1, atunci:
  • Introduceți un element nou într-un număr din ce în ce mai mare de articole.
  • Luați mediana nodurilor și împărțiți nodul în două noduri.
  • Împingeți mediana către nodul părinte.
  • Dacă cheia nodului părinte = m-1, repetați pașii de mai sus și pentru nodul părinte. Acest lucru se face până când găsim nodul frunzei corespunzător.
• În cele din urmă, introduceți elementul.

Am demonstrat inserarea în arborele B după cum urmează.

Să introducem articolul 70 în arborele prezentat mai jos.

la ce se folosește c ++

Arborele dat are un grad minim „m” = 3. Prin urmare, fiecare nod poate găzdui 2 * m -1 = 5 taste în interiorul său.

Acum inserăm elementul 70. Deoarece putem avea 5 taste într-un nod, comparăm elementul 70 cu elementul rădăcină 30. Din moment ce 70> 30, vom introduce elementul 70 în subarborele din dreapta.

În subarborele din dreapta, avem un nod cu tastele 40, 50, 60. Deoarece fiecare nod poate avea 5 chei în el, vom insera elementul 70 în acest nod în sine.

După inserare, arborele B arată după cum urmează.

# 3) Ștergere

La fel ca inserarea, ștergerea cheii se efectuează și la nivelul nodurilor frunzei. Dar, spre deosebire de inserare, ștergerea este mai complicată. Cheia care trebuie ștearsă poate fi fie un nod frunză, fie un nod intern.

Pentru a șterge o cheie, urmăm secvența de pași de mai jos (algoritm).

1. Localizați nodul frunzei.

Două. În cazul în care numărul de taste dintr-un nod> m / 2, apoi ștergeți cheia dată din nod.

3. În cazul în care nodul frunzei nu are chei m / 2, atunci trebuie să completăm tastele luând chei din subarborii din dreapta sau din stânga pentru a menține arborele B.

Urmăm acești pași:

• Dacă subarborele din stânga conține elemente m / 2, atunci împingem cel mai mare element al său către nodul părinte și apoi mutăm elementul intermediar în locul unde a fost ștearsă cheia.
• Dacă subarborele din dreapta conține elemente m / 2, atunci împingem cel mai mic element al acestuia către nodul părinte și apoi mutăm elementul intermediar în locul unde a fost ștearsă cheia.

Patru. Dacă niciun nod nu are m / 2 noduri, atunci pașii de mai sus nu pot fi efectuați, astfel creăm un nou nod frunză prin unirea a două noduri frunze și elementul intermediar al nodului părinte.

5. Dacă un părinte nu are noduri m / 2, atunci repetăm ​​pașii de mai sus pentru nodul părinte în cauză. Acești pași se repetă până când obținem un copac B echilibrat.

Mai jos este o ilustrație pentru ștergerea unui nod din arborele B.

Luați în considerare din nou următorul copac B.

Să presupunem că dorim să ștergem cheia 60 din arborele B. Dacă bifăm arborele B, putem constata că cheia care trebuie ștearsă este prezentă în nodul frunzei. Ștergem cheia 60 din acest nod frunză.

cum se execută fișierul jar în Windows

Acum arborele va arăta așa cum se arată mai jos:

Putem observa că după ștergerea cheii 60, nodul frunzei arborelui B îndeplinește proprietățile cerute și nu trebuie să mai facem alte modificări arborelui B.

Cu toate acestea, dacă ar trebui să ștergem cheia 20, atunci doar cheia 10 ar fi rămas în nodul frunzei stânga. În acest caz, ar trebui să mutăm rădăcina 30 în nodul frunzei și să mutăm tasta 40 în rădăcină.

Astfel, în timp ce ștergeți o cheie din arborele B, trebuie să aveți grijă și nu trebuie încălcate proprietățile arborelui B.

Traversal În Arborele B.

Traversarea în arborele B este, de asemenea, similară cu traversarea în ordine în BST. Începem recursiv de la stânga, apoi venim la rădăcină și continuăm spre subarborele stâng.

Aplicații ale copacilor B.

• Arborii B sunt folosiți pentru indexarea datelor, în special în bazele de date mari, deoarece accesul la datele stocate în baze de date mari pe discuri necesită mult timp.
• Căutarea datelor în seturi de date mai mari nesortate necesită mult timp, dar acest lucru poate fi îmbunătățit semnificativ cu indexarea folosind arborele B.

Arborele B + în C ++

Arborele B + este o extensie a arborelui B. Diferența dintre arborele B + și arborele B este că în arborele B cheile și înregistrările pot fi stocate atât ca noduri interne, cât și ca frunze, în timp ce în arborii B +, înregistrările sunt stocate ca noduri frunze și cheile sunt stocate numai în noduri interne.

Înregistrările sunt legate între ele într-un mod listat. Acest aranjament face căutările copacilor B + mai rapide și mai eficiente. Nodurile interne ale arborelui B + se numesc noduri index.

Arborii B + au două ordine, adică unul pentru noduri interne și altul pentru noduri frunze sau externe.

Un exemplu de copac B + este prezentat mai jos.

Deoarece arborele B + este o extensie a arborelui B, operațiunile de bază pe care le-am discutat la subiectul Arborele B sunt încă valabile.

În timp ce inserăm și ștergem, ar trebui să menținem intacte proprietățile de bază ale copacilor B +. Cu toate acestea, operația de ștergere în arborele B + este relativ mai ușoară, deoarece datele sunt stocate numai în nodurile frunze și vor fi șterse întotdeauna din nodurile frunze.

Avantajele copacilor B +

• Putem prelua înregistrări într-un număr egal de accesări pe disc.
• Comparativ cu arborele B, înălțimea arborelui B + este mai mică și rămâne echilibrată.
• Folosim chei pentru indexare.
• Datele din arborele B + pot fi accesate secvențial sau direct, deoarece nodurile frunzei sunt aranjate într-o listă legată.
• Căutarea este mai rapidă, deoarece datele sunt stocate numai în nodurile frunze și ca o listă legată.

Diferența dintre arborele B și arborele B +

Concluzie

În acest tutorial, am discutat în detaliu arborele B și arborele B +. Aceste două structuri de date sunt utilizate atunci când există o cantitate foarte mare de date și când întreaga informație nu poate fi stocată în memoria principală. Astfel, pentru a stoca date pe discuri, folosim arborele B și arborele B +.

Căutarea în arborele B este ușor mai lentă, deoarece datele sunt stocate în noduri interne, precum și în noduri frunze. Arborele B + este o extensie a arborelui B, iar datele de aici sunt stocate numai în nodurile frunzei. Datorită acestui factor, căutarea într-un copac B + este mai rapidă și eficientă.

=> Vizitați aici pentru lista completă de tutoriale C ++.

Lectură recomandată

• Structura de date AVB Tree și Heap în C ++
• Structura de date a listei legate în C ++ cu ilustrație
• Structura datelor în coadă în C ++ cu ilustrație
• Stivați structura datelor în C ++ cu ilustrație
• Structură de date cu listă circulară legată în C ++ cu ilustrație
• Introducere în structurile de date în C ++
• Structura de date a cozii prioritare în C ++ cu ilustrație
• Structură de date de listă dublă legată în C ++ cu ilustrație