Contenuto

• Contenuto: differenza tra albero B e albero binario
• Tabella di comparazione
• B-tree
• Albero binario
• Differenze chiave
• Conclusione
• Video esplicativo

La differenza tra B-tree e un albero binario è che B-tree è un albero ordinato in cui i nodi sono ordinati in ordine trasversale mentre l'albero binario è un albero ordinato con un puntatore su ciascun nodo.

Le strutture di dati sono i concetti più importanti nella programmazione dei computer e, nelle strutture di dati, i due concetti più importanti sono l'albero B e l'albero binario. Entrambi sono diversi l'uno dall'altro. B-tree è un albero ordinato in cui i nodi sono ordinati in ordine trasversale, mentre l'albero binario è un albero ordinato con un puntatore su ciascun nodo. L'albero B e l'albero binario sono strutture di dati non lineari. Per nome, entrambi i termini sembrano essere gli stessi, ma non sono gli stessi in quanto diversi. Un codice ad albero binario è archiviato nella RAM mentre un codice B-tree è archiviato sul disco.

B-tree è un albero M-way che è bilanciato, B-tree è noto come albero di ordinamento bilanciato. Esiste un attraversamento interno in B-tree. La complessità spaziale di B-tree è O (n). La complessità del tempo di inserimento e cancellazione è O (log n). In B-tree, l'altezza dell'albero dovrebbe essere il minimo possibile. In B-tree, non ci dovrebbero essere sottostrutture vuote. Tutte le foglie dell'albero dovrebbero essere allo stesso livello. Ogni nodo può avere un numero M massimo di figli e un numero M / 2 minimo di figli. Ogni nodo nell'albero B dovrebbe avere meno chiave della chiave figlio. In B-tree, le chiavi nella sottostruttura presente a sinistra della chiave sono i predecessori. Quando un nodo è pieno e si tenta di inserire un nuovo nodo, l'albero viene diviso in due parti. È possibile unire i nodi nell'albero B fino a quando i nodi non vengono eliminati.

Un albero binario ha due puntatori che contengono l'indirizzo dei suoi nodi figlio. Esistono tipi di alberi binari come un albero rigorosamente binario, un albero binario completo, un albero binario esteso, ecc. Nell'albero rigorosamente binario, ci deve essere una sottostruttura sinistra e una sottostruttura destra, in un albero binario completo, ci dovrebbero essere due nodi in ogni livello e nella struttura binaria filettata, dovrebbe esserci da 0 a 2 numero di nodi. Se parliamo di tecniche trasversali, tre tecniche trasversali sono in ordine trasversale, preordine trasversale e post ordine trasversale.

Contenuto: differenza tra albero B e albero binario

• Tabella di comparazione
• B-tree
• Albero binario
• Differenze chiave
• Conclusione
• Video esplicativo

Tabella di comparazione

Base	B-tree	Albero binario
Base	B-tree è un albero ordinato in cui i nodi sono ordinati in ordine trasversale.	Un albero binario è un albero ordinato con un puntatore su ciascun nodo.
Memorizzare	Il codice B-tree è memorizzato nel disco.	Il codice ad albero binario è memorizzato nella RAM
Altezza	L'altezza dell'albero B sarà il log N	L'altezza dell'albero binario sarà log2 N
Applicazione	DBMS è l'applicazione di B-tree.	La codifica di Huffman è un'applicazione di Binary Tree.

B-tree

B-tree è un albero M-way che è bilanciato, B-tree è noto come albero di ordinamento bilanciato. Esiste un attraversamento interno in B-tree. La complessità spaziale di B-tree è O (n). La complessità del tempo di inserimento e cancellazione è O (log n). In B-tree, l'altezza dell'albero dovrebbe essere il minimo possibile.

In B-tree, non ci dovrebbero essere sottostrutture vuote. Tutte le foglie dell'albero dovrebbero essere allo stesso livello. Ogni nodo può avere un numero M massimo di figli e un numero M / 2 minimo di figli. Ogni nodo nell'albero B dovrebbe avere meno chiave della chiave figlio. In B-tree, le chiavi nella sottostruttura presente a sinistra della chiave sono i predecessori. Quando un nodo è pieno e si tenta di inserire un nuovo nodo, l'albero viene diviso in due parti. È possibile unire i nodi nell'albero B fino a quando i nodi non vengono eliminati.

Albero binario

Un albero binario ha due puntatori che contengono l'indirizzo dei suoi nodi figlio. Esistono tipi di alberi binari come un albero rigorosamente binario, un albero binario completo, un albero binario esteso, ecc.

Nell'albero rigorosamente binario, devono essere presenti la sottostruttura sinistra e la sottostruttura destra, in un albero binario completo, ci dovrebbero essere due nodi per ogni livello e nella struttura binaria filettata, dovrebbero esserci da 0 a 2 numero di nodi. Se parliamo di tecniche trasversali, ci sono tre tecniche trasversali che sono in ordine trasversale, preordine trasversale e post ordine trasversale.

Differenze chiave

1. B-tree è un albero ordinato in cui i nodi sono ordinati in ordine trasversale mentre l'albero binario è un albero ordinato con un puntatore su ciascun nodo.
2. Il codice B-tree è archiviato nel disco mentre il codice binario dell'albero è archiviato nella RAM.
3. L'altezza dell'albero B sarà logN mentre l'altezza dell'albero binario sarà log₂ N
4. DBMS è l'applicazione di B-tree mentre la codifica Huffman è un'applicazione di Binary Tree.

Conclusione

In questo articolo sopra vediamo la chiara differenza tra B-tree e Binary tree con la loro implementazione.

Video esplicativo