Prima di comprendere il Albero rosso-nero e albero AVL differenze, dovremmo conoscere l'albero Rosso-Nero e l'albero AVL separatamente.
Cos'è un albero rosso-nero?
L'albero rosso-nero è un auto-equilibrato albero di ricerca binario in cui ogni nodo contiene un bit di informazione in più che denota il colore del nodo. Il colore del nodo potrebbe essere rosso o nero, a seconda delle informazioni sui bit memorizzate dal nodo.
Proprietà
Di seguito sono riportate le proprietà associate ad un albero Rosso-Nero:
- Il nodo radice dell'albero dovrebbe essere nero.
- Un nodo rosso può avere solo figli neri. Oppure possiamo dire che due nodi adiacenti non possono essere di colore rosso.
- Se il nodo non ha un figlio sinistro o destro, allora quel nodo si dice che sia un nodo foglia. Quindi, mettiamo i bambini sinistro e destro sotto il nodo foglia noto come zero
La profondità del nero o l'altezza del nero di un nodo foglia può essere definita come il numero di nero che incontriamo quando ci spostiamo dal nodo foglia al nodo radice. Una delle proprietà chiave dell'albero Rosso-Nero è che ogni nodo foglia dovrebbe avere la stessa profondità di nero.
Capiamo questa proprietà attraverso un esempio.
Nell'albero sopra ci sono cinque nodi, di cui uno è rosso e gli altri quattro nodi sono neri. Ci sono tre nodi foglia nell'albero sopra. Ora calcoliamo la profondità del nero di ciascun nodo foglia. Come possiamo osservare che la profondità del nero di tutti e tre i nodi foglia è 2; quindi è un albero Rosso-Nero.
Se l'albero non obbedisce a nessuna delle tre proprietà precedenti, allora non è un albero Rosso-Nero.
Altezza di un albero rosso-nero
Consideriamo h l'altezza dell'albero avente n nodi. Quale sarebbe il valore più piccolo di n?. Il valore di n è il più piccolo quando tutti i nodi sono neri. Se l'albero contenesse tutti i nodi neri, allora l'albero sarebbe un albero binario completo. Se l'altezza di un albero binario completo è h, allora il numero di nodi in un albero è:
n = 2h -1
Quale sarebbe il valore più grande di n?
arraylist java
Il valore di n è maggiore quando ogni nodo nero ha due figli rossi, ma il nodo rosso non può avere figli rossi, quindi avrà figli neri. In questo modo ci sono strati alternati di bambini neri e rossi. Quindi, se il numero di strati neri è h, allora anche il numero di strati rossi è h; quindi l'altezza totale dell'albero diventa 2h. Il numero totale di nodi è:
n = 2*2h-1
sottolineare il testo con i css
Cos'è l'albero AVL?
UN Albero AVL è un albero di ricerca binario autobilanciante se osserviamo il caso seguente, che è un albero di ricerca binario e un albero bilanciato.
Nell'albero precedente, la complessità temporale nel caso peggiore per la ricerca di un elemento è O(h), ovvero l'altezza dell'albero. Nel caso precedente, il numero di confronti effettuati per cercare 17 elementi è 4 e anche l'altezza dell'albero è 4.
Se consideriamo l'albero binario distorto, come mostrato di seguito:
Nell'albero inclinato a destra in alto, il numero di confronti effettuati per cercare 17 elementi è 5, e anche il numero di elementi presenti nell'albero è 5. Pertanto, possiamo dire che se l'albero è un albero binario inclinato allora la complessità temporale sarebbe O(n).
Ora dobbiamo bilanciare questi alberi distorti in modo che abbiano complessità temporale O(h). Esiste un termine noto come a fattore di equilibrio , che viene utilizzato per autobilanciare l'albero di ricerca binario. Il fattore di equilibrio può essere calcolato come:
Fattore di equilibrio = altezza del sottoalbero sinistro-altezza del sottoalbero destroIl valore del fattore di equilibrio può essere 1, 0 o -1. Se ciascun nodo nell'albero binario ha un valore di 1, 0 o -1, allora quell'albero si dice che sia un albero bilanciato albero binario o albero AVL.
L'albero è noto come albero perfettamente bilanciato se il fattore di equilibrio di ciascun nodo è 0. L'albero AVL è un albero quasi bilanciato perché ogni nodo nell'albero ha il valore del fattore di equilibrio 1, 0 o -1.
Differenze tra l'albero Rosso-Nero e l'albero AVL.
Di seguito sono riportate le differenze tra l'albero Rosso-Nero e l'albero AVL:
L'albero Rosso-Nero è un albero di ricerca binario e anche l'albero AVL è un albero di ricerca binario.
In un albero rosso-nero vengono applicate le seguenti regole:
- Il nodo in un albero Rosso-Nero è di colore rosso o nero.
- Il colore del nodo radice dovrebbe essere nero.
- I nodi adiacenti non dovrebbero essere rossi. In altre parole, possiamo dire che il nodo rosso non può avere figli rossi, ma il nodo nero può avere figli neri.
- Dovrebbe esserci lo stesso numero di nodi neri in ogni percorso; quindi solo un albero può essere considerato un albero Rosso-Nero.
- I nodi esterni sono i nodi nulli, che sono sempre di colore nero.
Regola dell'albero AVL:
Ogni nodo dovrebbe avere il fattore di equilibrio come -1, 0 o 1.
Nella figura sopra, dobbiamo verificare se l'albero è un albero Rosso-Nero o meno. Per verificarlo, dobbiamo innanzitutto verificare se l'albero è un albero di ricerca binario o meno. Come possiamo osservare nella figura sopra, soddisfa tutte le proprietà dell'albero di ricerca binario; pertanto, è un albero di ricerca binario. In secondo luogo bisogna verificare se soddisfa o meno le regole sopra indicate. L'albero di cui sopra soddisfa tutte le cinque regole precedenti; pertanto, si conclude che l'albero sopra è un albero Rosso-Nero.
Nella figura sopra, dobbiamo verificare se l'albero è un albero AVL o meno. Poiché ciascun nodo ha un valore del fattore di equilibrio come -1, 0 o 1, quindi è un albero AVL.
Nel caso di un albero Rosso-Nero, se tutte le regole di cui sopra sono soddisfatte, a condizione che l'albero sia un albero di ricerca binario, allora l'albero si dice che sia un albero Rosso-nero.
Nel caso dell'albero AVL, se il fattore di equilibrio è -1, 0 o 1, allora l'albero sopra è detto albero AVL.
Se l'albero non è bilanciato, vengono utilizzati due strumenti per bilanciare l'albero in un albero Rosso-Nero:
Se l'albero non è bilanciato, viene utilizzato uno strumento per bilanciare l'albero nell'albero AVL:
Nel caso dell'albero Rosso-Nero le operazioni di inserimento e cancellazione sono efficienti. Se l'albero viene bilanciato attraverso la ricolorazione, allora le operazioni di inserimento e cancellazione sono efficaci nell'albero Rosso-Nero.
Linux modificare un file
Nel caso dell'albero AVL, l'operazione di ricerca è efficiente poiché richiede un solo strumento per bilanciare l'albero.
Nel caso dell'albero Rosso-Nero, la complessità temporale per tutte le operazioni, ovvero inserimento, cancellazione e ricerca è O(logn).
Nel caso dell'albero AVL, la complessità temporale per tutte le operazioni, ovvero inserimento, cancellazione e ricerca è O(logn).
Capiamo le differenze nella forma tabellare.
| Parametro | Albero rosso nero | Albero AVL |
|---|---|---|
| Ricerca | L'albero Rosso Nero non fornisce una ricerca efficiente poiché gli alberi Rosso Nero sono approssimativamente bilanciati. | Gli alberi AVL forniscono una ricerca efficiente poiché sono alberi rigorosamente bilanciati. |
| Inserimento e cancellazione | L'inserimento e l'eliminazione sono più semplici nell'albero Rosso Nero poiché richiede meno rotazioni per bilanciare l'albero. | L'inserimento e l'eliminazione sono complessi nell'albero AVL poiché richiedono più rotazioni per bilanciare l'albero. |
| Colore del nodo | Nell'albero Rosso-Nero, il colore del nodo è Rosso o Nero. | Nel caso degli alberi AVL, non esiste alcun colore del nodo. |
| Fattore di equilibrio | Non contiene alcun fattore di equilibrio. Memorizza solo un bit di informazione che denota il colore rosso o nero del nodo. | Ogni nodo ha un fattore di equilibrio nell'albero AVL il cui valore può essere 1, 0 o -1. Richiede spazio aggiuntivo per memorizzare il fattore di equilibrio per nodo. |
| Rigorosamente equilibrato | Gli alberi rosso-neri non sono strettamente bilanciati. | Gli alberi AVL sono strettamente bilanciati, ovvero l'altezza del sottoalbero sinistro e l'altezza del sottoalbero destro differiscono al massimo di 1. |