b tree b tree data structure c
Aquest tutorial de C ++ explica les estructures de dades de l'arbre B i B + Tree. S'utilitzen per emmagatzemar dades en discos quan no es poden emmagatzemar totes les dades a la memòria principal:
L’arbre B és un arbre autoequilibrat, així com un arbre especial de m-way que s’utilitza per accedir al disc.
Quan la quantitat de dades a emmagatzemar és molt elevada, no podem emmagatzemar la totalitat de les dades a la memòria principal. Per tant, emmagatzemem dades al disc. L’accés a les dades des del disc requereix més temps si es compara amb l’accés a la memòria principal.
Quan el nombre de claus de les dades emmagatzemades als discos és molt elevat, normalment s’accedeix a les dades en forma de blocs. El temps per accedir a aquests blocs és directament proporcional a l’alçada de l’arbre.
=> Feu clic aquí per obtenir la sèrie de formació Absolute C ++.
Què aprendreu:
Arbre B a C ++
L’arbre B és un arbre pla, és a dir, l’alçada de l’arbre B es redueix al mínim. En canvi, es posen tantes tecles a cada node de l'arbre B. En mantenir l’alçada de l’arbre B al mínim, l’accés és més ràpid en comparació amb altres arbres equilibrats com els arbres AVL.
A continuació es mostra un arbre B típic:
quin és el millor proveïdor de correu electrònic
Generalment, la mida del node a l'arbre B es manté igual que la mida del bloc.
A continuació es detallen algunes de les propietats de B-Tree.
- Totes les fulles de l'arbre B estan al mateix nivell.
- Un arbre B d’ordre m pot tenir com a màxim m-1 tecles i m fills.
- Tots els nodes de l'arbre B tenen com a màxim m fills.
- El node arrel ha de tenir almenys dos nodes.
- Tots els nodes, excepte el node arrel i el node fulla, contenen m / 2 fills.
A continuació, comentem algunes de les operacions bàsiques de l'arbre B.
Operacions bàsiques de B-Tree
A continuació es detallen algunes de les operacions bàsiques de B-Tree.
# 1) Cerca
La cerca a l’arbre B és similar a la de BST. A l'arbre anterior, si volem cercar l'element 3, procedirem de la següent manera:
- Compareu 3 amb elements arrel. Aquí, 3<6 and 3 <15. So we proceed to the left subtree.
- Compareu 3 amb 4 al subarbre esquerre. Com a 3<4, we proceed to the left subtree of node 4.
- El següent node té dues tecles, 2 i 3. 3> 2 mentre que 3 = 3. Per tant, hem trobat la clau en aquest node. Torneu a la ubicació trobada.
La cerca a l’arbre B depèn de l’alçada de l’arbre. Normalment es necessita O (registre n) de temps per cercar un element determinat.
# 2) Inserció
La inserció d’un element nou a l’arbre B es fa a nivell de nodes de fulles.
A continuació es mostra la seqüència de passos (algorisme) per inserir un element nou a l’arbre B.
- Travesseu l'arbre B per trobar una ubicació als nodes de la fulla per inserir l'element.
- Si el node fulla conté claus
- En cas contrari, si les claus del node de fulla = m-1, llavors:
- Inseriu un element nou en un nombre creixent d'elements.
- Agafeu la mediana dels nodes i dividiu-lo en dos nodes.
- Introduïu la mediana fins al seu node pare.
- Si la clau del node pare = m-1, repetiu també els passos anteriors per al node pare. Això es fa fins que trobem el node de fulla adequat.
- Finalment, inseriu l’element.
- En cas contrari, si les claus del node de fulla = m-1, llavors:
Hem demostrat la inserció a l’arbre B de la següent manera.
Inserim l'element 70 a l'arbre que es mostra a continuació.
per a què s’utilitza c ++
L’arbre donat té un grau mínim ‘m’ = 3. Per tant, cada node pot allotjar-hi 2 * m -1 = 5 tecles al seu interior.
Ara inserim l’element 70. Com que podem tenir 5 claus en un node, comparem l’element 70 amb l’element arrel 30. Des de 70> 30, inserirem l’element 70 al subarbre dret.
Al subarbre dret, tenim un node amb les claus 40, 50, 60. Com que cada node pot tenir 5 claus, inserirem l’element 70 en aquest mateix node.
Després de la inserció, l'arbre B té el següent aspecte.
# 3) Supressió
Igual que la inserció, la supressió de la clau també es duu a terme a nivell de nodes de fulla. Però, a diferència de la inserció, la supressió és més complicada. La clau que cal esborrar pot ser un node fulla o un node intern.
Per suprimir una clau, seguim la següent seqüència de passos (algorisme).
1. Localitzeu el node de la fulla.
2. En cas que el nombre de claus d’un node> m / 2, suprimiu la clau donada del node.
3. En cas que el node fulla no tingui claus m / 2, hem de completar les claus agafant les claus dels subarbres dret o esquerre per mantenir l'arbre B.
Seguim aquests passos:
- Si el subarbre esquerre conté elements m / 2, empenyem el seu element més gran fins al node pare i, a continuació, traslladem l'element que hi ha intervingut al lloc on s'ha suprimit la clau.
- Si el subarbre dret conté elements m / 2, empenyem el seu element més petit fins al node pare i, a continuació, traslladem l’element que hi ha intervingut al lloc on s’ha suprimit la clau.
4. Si cap node no té m / 2 nodes, no es poden realitzar els passos anteriors, de manera que creem un nou node full unint dos nodes fulls i l'element intermedi del node pare.
5. Si un pare no té m / 2 nodes, repetim els passos anteriors per al node pare en qüestió. Aquests passos es repeteixen fins obtenir un arbre B equilibrat.
A continuació es mostra una il·lustració per eliminar un node de l’arbre B.
Penseu en el següent arbre B.
Suposem que volem suprimir la clau 60 de l’arbre B. Si comprovem l’arbre B, podem trobar que la clau a suprimir està present al node de fulla. Eliminem la clau 60 d’aquest node de fulla.
Ara l'arbre es veurà com es mostra a continuació:
Podem notar que després d’eliminar la clau 60, el node de fulla de l’arbre B compleix les propietats requerides i no hem de fer cap modificació més a l’arbre B.
Tanmateix, si haguéssim d’esborrar la clau 20, només la clau 10 hauria quedat al node de la fulla esquerra. En aquest cas, hauríem de desplaçar l'arrel 30 al node fulla i moure la clau 40 a l'arrel.
Per tant, mentre esborra una clau de l’arbre B, s’ha de tenir precaució i no s’ha de vulnerar les propietats de l’arbre B.
Traversal a l'arbre B.
La travessia a l'arbre B també és similar a la travessia inorder a BST. Comencem recursivament per l'esquerra i després arribem a l'arrel i avancem cap al subarbre esquerre.
Aplicacions dels arbres B.
- Els arbres B s’utilitzen per indexar les dades, especialment en bases de dades grans, ja que l’accés a les dades emmagatzemades en bases de dades grans en discos requereix molt de temps.
- La cerca de dades en conjunts de dades sense classificar més grans requereix molt de temps, però es pot millorar significativament amb la indexació mitjançant l’arbre B.
Arbre B + a C ++
L’arbre B + és una extensió de l’arbre B. La diferència entre l’arbre B + i l’arbre B és que a l’arbre B es poden emmagatzemar les claus i els registres tant com a nodes interns com a fulles, mentre que als arbres B + els registres s’emmagatzemen com a nodes de fulles i les claus només s’emmagatzemen als nodes interns.
Els registres estan enllaçats entre si de manera llista. Aquesta disposició fa que les cerques d’arbres B + siguin més ràpides i eficients. Els nodes interns de l’arbre B + s’anomenen nodes índex.
Els arbres B + tenen dos ordres, és a dir, un per a nodes interns i un altre per a nodes de fulla o externs.
A continuació es mostra un exemple d’arbre B +.
diferència entre les proves de caixa negra i de caixa blanca
Com que l’arbre B + és una extensió de l’arbre B, encara es mantenen les operacions bàsiques que hem comentat sota el tema.
Tot i inserir i suprimir, hem de mantenir intactes les propietats bàsiques dels arbres B +. Tot i això, l'operació de supressió a l'arbre B + és relativament més senzilla, ja que les dades només s'emmagatzemen als nodes de fulla i sempre se suprimiran dels nodes de fulla.
Avantatges dels arbres B +
- Podem obtenir registres en un nombre igual d’accessos al disc.
- En comparació amb l’arbre B, l’alçada de l’arbre B + és menor i es manté equilibrada.
- Utilitzem claus per indexar.
- Es pot accedir a les dades de l’arbre B + seqüencialment o directament, ja que els nodes de la fulla es disposen en una llista enllaçada.
- La cerca és més ràpida ja que les dades s’emmagatzemen només als nodes fulls i com a llista enllaçada.
Diferència entre l'arbre B i l'arbre B +
| B-Tree | B + Tree |
|---|---|
| Les dades s’emmagatzemen en nodes fulla, així com en nodes interns. | Les dades només s’emmagatzemen als nodes fulls. |
| La cerca és una mica més lenta, ja que les dades s’emmagatzemen tant als nodes interns com als fulls. | La cerca és més ràpida, ja que les dades només s’emmagatzemen als nodes fulls. |
| No hi ha cap tecla de cerca redundant. | És possible que hi hagi claus de cerca redundants. |
| L'operació de supressió és complexa. | L'operació de supressió és senzilla, ja que les dades es poden esborrar directament dels nodes fulls. |
| Els nodes de fulles no es poden enllaçar. | Els nodes de fulla s’uneixen entre si per formar una llista enllaçada. |
Conclusió
En aquest tutorial, hem debatut detalladament sobre l'arbre B i l'arbre B +. Aquestes dues estructures de dades s’utilitzen quan hi ha una quantitat molt elevada de dades i quan no es poden emmagatzemar totes les dades a la memòria principal. Per emmagatzemar dades en discs, fem ús de l'arbre B i l'arbre B +.
La cerca a l’arbre B és una mica més lenta, ja que les dades s’emmagatzemen als nodes interns i també als nodes fulls. L'arbre B + és una extensió de l'arbre B i les dades aquí només s'emmagatzemen als nodes de fulles. A causa d’aquest factor, la cerca en un arbre B + és més ràpida i eficaç.
=> Visiteu aquí la llista completa de tutorials de C ++.
Lectura recomanada
- Arbre AVL i estructura de dades de Heap a C ++
- Estructura de dades de la llista enllaçada en C ++ amb il·lustració
- Estructura de dades de la cua en C ++ amb il·lustració
- Estructura de dades de pila en C ++ amb il·lustració
- Estructura de dades de llistes enllaçades circulars en C ++ amb il·lustració
- Introducció a les estructures de dades en C ++
- Estructura de dades de la cua de prioritat en C ++ amb il·lustració
- Estructura de dades de llistes doblement enllaçades en C ++ amb il·lustració