Struttura dati B Tree e B + Tree in C ++

b tree b tree data structure c

Questo tutorial C ++ spiega le strutture dati B Tree e B + Tree. Vengono utilizzati per archiviare i dati nei dischi quando non è possibile archiviare tutti i dati nella memoria principale:

B-tree è un albero autobilanciato e un albero m-way specializzato utilizzato per l'accesso al disco.

Quando la quantità di dati da memorizzare è molto alta, non è possibile memorizzare tutti i dati nella memoria principale. Quindi memorizziamo i dati nel disco. L'accesso ai dati dal disco richiede più tempo rispetto all'accesso alla memoria principale.

Quando il numero di chiavi dei dati archiviati nei dischi è molto elevato, l'accesso ai dati avviene solitamente sotto forma di blocchi. Il tempo per accedere a questi blocchi è direttamente proporzionale all'altezza dell'albero.

=> Fare clic qui per la serie di formazione Absolute C ++.

Cosa imparerai:

• B-Tree in C ++
  • Operazioni di base di B-Tree
    • # 1) Ricerca
    • # 2) Inserimento
    • # 3) Cancellazione
  • Applicazioni degli alberi B.
• B + Albero in C ++
  • Vantaggi degli alberi B +
• Differenza tra B-Tree e B + Tree
• Conclusione
  • Lettura consigliata

B-Tree in C ++

Il B-Tree è un albero piatto, cioè l'altezza dell'albero B è ridotta al minimo. Al contrario, altrettante chiavi vengono inserite in ogni nodo dell'albero B. Mantenendo l'altezza dell'albero B al minimo, l'accesso è più veloce rispetto ad altri alberi bilanciati come gli alberi AVL.

Di seguito è mostrato un tipico albero B:

server privati ​​vaniglia di world of warcraft

Generalmente, la dimensione del nodo in B-tree viene mantenuta uguale alla dimensione del blocco.

Di seguito sono elencate alcune delle proprietà di B-Tree.

• Tutte le foglie dell'albero B sono allo stesso livello.
• Un B-tree di ordine m può avere al massimo m-1 chiavi e m figli.
• Ogni nodo in B-tree ha al massimo m figli.
• Il nodo radice deve avere almeno due nodi.
• Ogni nodo eccetto il nodo radice e il nodo foglia contengono m / 2 figli.

Successivamente, discuteremo alcune delle operazioni di base di B-tree.

Operazioni di base di B-Tree

Di seguito sono riportate alcune delle operazioni di base di B-Tree.

# 1) Ricerca

La ricerca nell'albero B è simile a quella in BST. Nell'albero sopra se vogliamo cercare l'elemento 3, procederemo come segue:

• Confronta 3 con gli elementi radice. Qui, 3<6 and 3 <15. So we proceed to the left subtree.
• Confronta 3 con 4 nella sottostruttura di sinistra. Come 3<4, we proceed to the left subtree of node 4.
• Il nodo successivo ha due chiavi, 2 e 3. 3> 2 mentre 3 = 3. Quindi abbiamo trovato la chiave in questo nodo. Ritorna alla posizione trovata.

La ricerca nell'albero B dipende dall'altezza dell'albero. Di solito occorre una quantità di tempo O (log n) per cercare un dato elemento.

# 2) Inserimento

L'inserimento di un nuovo elemento nell'albero B viene fatto a livello dei nodi foglia.

Di seguito è riportata la sequenza di passaggi (algoritmo) per inserire un nuovo elemento nell'albero B.

• Attraversa l'albero B per trovare una posizione nei nodi foglia in cui inserire l'elemento.
• Se il nodo foglia contiene chiavi
• Altrimenti se le chiavi del nodo foglia = m-1, allora:
  • Inserisci un nuovo elemento in un numero crescente di elementi.
  • Prendi la mediana dei nodi e dividi il nodo in due nodi.
  • Spingere la mediana al suo nodo genitore.
  • Se la chiave del nodo padre = m-1, ripetere i passaggi precedenti anche per il nodo padre. Questo viene fatto finché non troviamo il nodo foglia appropriato.
• Infine, inserisci l'elemento.

Abbiamo dimostrato l'inserimento nell'albero B come segue.

Inseriamo l'elemento 70 nell'albero mostrato sotto.

come guardare netflix con VPN

L'albero dato è con un grado minimo 'm' = 3. Quindi, ogni nodo può contenere 2 * m -1 = 5 chiavi al suo interno.

Ora inseriamo l'elemento 70. Poiché possiamo avere 5 chiavi in ​​un nodo, confrontiamo l'elemento 70 con l'elemento radice 30. Poiché 70> 30, inseriremo l'elemento 70 nella sottostruttura destra.

Nella sottostruttura di destra, abbiamo un nodo con le chiavi 40, 50, 60. Poiché ogni nodo può contenere 5 chiavi, inseriremo l'elemento 70 in questo nodo stesso.

Dopo l'inserimento, il B-Tree appare come segue.

# 3) Cancellazione

Come per l'inserimento, anche la cancellazione della chiave viene eseguita a livello dei nodi foglia. Ma a differenza dell'inserimento, la cancellazione è più complicata. La chiave da eliminare può essere un nodo foglia o un nodo interno.

Per eliminare una chiave, seguiamo la seguente sequenza di passaggi (algoritmo).

1. Individua il nodo foglia.

2. Nel caso in cui il numero di chiavi in ​​un nodo> m / 2, quindi eliminare la chiave data dal nodo.

3. Nel caso in cui il nodo foglia non abbia chiavi m / 2, è necessario completare le chiavi prendendo le chiavi dalle sottostrutture destra o sinistra per mantenere l'albero B.

Seguiamo questi passaggi:

• Se la sottostruttura sinistra contiene m / 2 elementi, inseriamo il suo elemento più grande nel nodo genitore e quindi spostiamo l'elemento intermedio nel punto in cui è stata eliminata la chiave.
• Se la sottostruttura destra contiene m / 2 elementi, inseriamo il suo elemento più piccolo nel nodo genitore e quindi spostiamo l'elemento intermedio nel punto in cui è stata eliminata la chiave.

Quattro. Se nessun nodo ha m / 2 nodi, i passaggi precedenti non possono essere eseguiti, quindi creiamo un nuovo nodo foglia unendo due nodi foglia e l'elemento intermedio del nodo padre.

5. Se un genitore è senza m / 2 nodi, ripetiamo i passaggi precedenti per il nodo genitore in questione. Questi passaggi vengono ripetuti fino a ottenere un albero B equilibrato.

Di seguito è riportata un'illustrazione per eliminare un nodo dall'albero B.

Considera ancora una volta il seguente albero B.

Supponiamo di voler eliminare la chiave 60 dall'albero B. Se controlliamo l'albero B, possiamo scoprire che la chiave da eliminare è presente nel nodo foglia. Eliminiamo la chiave 60 da questo nodo foglia.

Ora l'albero apparirà come mostrato di seguito:

Possiamo notare che dopo aver cancellato la chiave 60, il nodo foglia dell'albero B soddisfa le proprietà richieste e non è necessario apportare ulteriori modifiche all'albero B.

come aprire il file json in Windows 10

Tuttavia, se dovessimo eliminare la chiave 20, solo la chiave 10 sarebbe rimasta nel nodo foglia sinistro. In questo caso, dovremmo spostare la radice 30 sul nodo foglia e spostare la chiave 40 sulla radice.

Pertanto, durante l'eliminazione di una chiave dall'albero B, è necessario prestare attenzione e le proprietà dell'albero B non dovrebbero essere violate.

Traversata in B albero

Anche l'attraversamento nell'albero B è simile all'attraversamento inordine in BST. Iniziamo ricorsivamente da sinistra, quindi arriviamo alla radice e procediamo verso la sottostruttura sinistra.

Applicazioni degli alberi B.

• Gli alberi B vengono utilizzati per indicizzare i dati, soprattutto nei database di grandi dimensioni, poiché l'accesso ai dati archiviati nei database di grandi dimensioni sui dischi richiede molto tempo.
• La ricerca di dati in set di dati non ordinati più grandi richiede molto tempo, ma può essere migliorata in modo significativo con l'indicizzazione utilizzando l'albero B.

B + Albero in C ++

L'albero B + è un'estensione dell'albero B. La differenza nell'albero B + e nell'albero B è che nell'albero B le chiavi e i record possono essere memorizzati come nodi interni e foglia mentre negli alberi B +, i record vengono memorizzati come nodi foglia e le chiavi sono archiviate solo nei nodi interni.

I record sono collegati tra loro in un modo di elenco collegato. Questa disposizione rende le ricerche degli alberi B + più veloci ed efficienti. I nodi interni dell'albero B + sono chiamati nodi indice.

Gli alberi B + hanno due ordini, cioè uno per i nodi interni e l'altro per i nodi foglia o esterni.

Di seguito è mostrato un esempio di albero B +.

Poiché B + tree è un'estensione di B-tree, le operazioni di base che abbiamo discusso sotto l'argomento B-tree sono ancora valide.

Durante l'inserimento e l'eliminazione, dovremmo mantenere intatte le proprietà di base di B + Trees. Tuttavia, l'operazione di eliminazione nell'albero B + è relativamente più semplice poiché i dati vengono memorizzati solo nei nodi foglia e verranno sempre eliminati dai nodi foglia.

Vantaggi degli alberi B +

• Possiamo recuperare i record in un numero uguale di accessi al disco.
• Rispetto all'albero B, l'altezza dell'albero B + è minore e rimane equilibrata.
• Usiamo le chiavi per l'indicizzazione.
• È possibile accedere ai dati nell'albero B + in sequenza o direttamente poiché i nodi foglia sono disposti in un elenco collegato.
• La ricerca è più veloce poiché i dati vengono archiviati solo nei nodi foglia e come elenco collegato.

Differenza tra B-Tree e B + Tree

Conclusione

In questo tutorial, abbiamo discusso in dettaglio B-tree e B + tree. Queste due strutture di dati vengono utilizzate quando la quantità di dati è molto elevata e quando non è possibile archiviare tutti i dati nella memoria principale. Pertanto, per memorizzare i dati nei dischi, utilizziamo B-tree e B + tree.

La ricerca dell'albero B è leggermente più lenta poiché i dati vengono archiviati nei nodi interni e nei nodi foglia. B + tree è un'estensione di B-tree ei dati qui sono memorizzati solo nei nodi foglia. A causa di questo fattore, la ricerca in un albero B + è più veloce ed efficiente.

=> Visita qui per l'elenco completo dei tutorial C ++.

Lettura consigliata

• Struttura dei dati ad albero e heap AVL in C ++
• Struttura Dati Elenco Collegato In C ++ Con Illustrazione
• Struttura dei dati della coda in C ++ con illustrazione
• Stack Struttura Dati In C ++ Con Illustrazione
• Struttura Dati Elenco Collegato Circolare In C ++ Con Illustrazione
• Introduzione alle strutture dati in C ++
• Priorità Struttura Dati Coda In C ++ Con Illustrazione
• Struttura dei dati della lista doppiamente collegata in C ++ con illustrazione