Quando si converte ad un albero rosso-nero, non v'è alcun motivo per scegliere una forma piuttosto che un altro?

Question

Ho una biblioteca di lista collegata / metodi di alberi binari per l'uso quando i contenitori standard non si adattano - per esempio Quando ci sono diversi tipi di nodi, o quando ho bisogno di convertire da albero binario alla lista e viceversa. Esso comprende la gestione albero rosso-nero.

Uno dei metodi converte da una lista doppio collegata ad un semplice albero binario perfettamente bilanciato in tempo O(n) (dato che il numero di elementi è noto in anticipo). L'algoritmo è noto come "folding" - è la seconda metà di un algoritmo di albero di riequilibrio binario che una volta è stato pubblicato in Dr. Dobbs'. I passi sono fondamentalmente ...

• Data la dimensione della struttura, decidere le dimensioni dei sottoalberi sinistro e destro

• Recurse per il sottoalbero di sinistra

• Pop un nodo dall'elenco utilizzare come radice

• Recurse per il sottoalbero destro

• Collegare le sottostrutture alla radice

Ho anche un metodo simile che crea un albero rosso-nero. Il principio è lo stesso, ma la ricorsione registra altezza nodo - altezza pari a zero nodi sono creati rosso, tutti gli altri sono neri. Il calcolo altezza di partenza si basa sul più alto bit impostato nella dimensione dell'albero, ed è suonato il violino in modo che un albero di dimensioni perfettamente bilanciato (2^n)-1 ha solo nodi neri (la ricorsione va solo verso il basso per l'altezza uno).

Il punto qui è che ho solo nodi rossi a livello di foglia, e un massimo di esattamente la metà dei nodi sono di colore rosso.

Il fatto è che, mentre questo è un modo semplice per generare un albero rosso-nero valida, non è l'unica opzione. Evitando di dover tutti foglie rosse in un albero perfettamente bilanciato è stata una scelta arbitraria. Potrei avere strati alternati di nodi rossi e neri. Oppure potrei ridurre il numero di nodi rossi drammaticamente in alcuni casi individuando sottostrutture che sono perfettamente equilibrato e (se ha bisogno di nodi rossi) rendendo la radice sottoalbero rosso al posto di tutte le sue foglie.

La domanda è -? V'è alcuna ragione pratica per scegliere una valida forma di albero red-black su un altro

Questa è pura curiosità - So che non ho alcuna ragione pratica -?, Ma qualcuno sa di un'applicazione specializzata in cui questa scelta è significativa

Answer 1

Nella analisi standard del costo ammortizzato di modificare alberi rosso-neri con il metodo del pysicist, nodi neri con zero o due figli rossi sono assegnate un potenziale positivo di uno, il che significa che essi rappresentano luoghi problematici l'albero dove in più il lavoro può avere bisogno di essere fatto. nodi rossi e nodi neri con esattamente un bambino rosso sono assegnate un potenziale pari a zero.

Quindi, per ridurre il costo di modifiche, dare ogni nodo nero un bambino rosso.

---

Il motivo per cui nodi neri con un bambino rosso sono benedetti è spiegato meglio per analogia ridondanti numeri binari. Voglio prima di spiegare come relazionarsi alberi rosso-neri verso i numeri binari e poi vi spiegherò il motivo per cui i nodi di un rosso-figlio sono utili.

Come forse sapete, alberi rosso-neri sono un modo di rappresentare alberi 2-4, in cui ogni semplice percorso dalla radice ad una foglia ha la stessa lunghezza, ma i nodi hanno 2, 3 o 4 bambini. L'algoritmo semplice per l'aggiunta o la rimozione di un nodo in un albero 2-4 è lo stesso algoritmo aggiungendo o sottraendo uno da un numero binario ridondante .

Un numero binario ridondante è un numero in cui la cifra esimo rappresenta 2 ⁱ , come in un numero binario standard, ma la cifra esimo può essere 0, 1, o 2 . Essi sono chiamati ridondanti perché ci sono diversi modi per scrivere un dato numero. 4 _dec può essere scritto 100 o 20 o 12.

Per aggiungere uno a un numero binario ridondante, si incrementa la cifra meno significativa; se è 3, impostarlo a 1 e incrementare la cifra successiva meno significativa, e così via. L'algoritmo si arresta quando incontra un 0 o 1.

Per aggiungere una foglia di un albero 2-4, aggiungere un bambino al suo genitore previsto. Se il genitore come ha cinque figli, dividerlo in due nodi e renderli figli del suo genitore. Continuare fino a raggiungere un nodo che non ha bisogno di dividere. Così, il percorso verso la radice arresta quando incontra un nodo con due o tre figli.

Per vincolato il costo ammortizzato di incrementare un numero binario ridondante, utilizzare il metodo fisici e assegnare un potenziale di 1 per ogni 2 cifre. Un XALL di incremento che tocca cifre k stampa K-1 potenziale, dandogli un costo ammortizzato di O (1).

Tale analisi è simile al costo ammortizzato di incrementare un numero binario standard, ma un numero binario standard non può supportare sia incremento e decremento in O (1) ammortizzato tempo: considerare 2 ^k - 1. è k 1 cifre. Incremento costa Θ (k). Se questo è seguito da un decremento, la coppia costa Θ (k) e porta il numero al suo stato precedente.

binario ridondante è speciale in quanto 1 cifra fermare le operazioni cascata di entrambi incremento e decremento. 2-4 alberi sono speciali in quanto 3-nodi fermare le operazioni a cascata sia di inserire ed eliminare.

In alberi rosso-neri, un nodo con un bambino rosso è solo una rappresentazione di un nodo 3 in un albero 2-4. Questi nodi sono speciali e robusti contro gli inserti o elimina nei loro sottostrutture, così si dovrebbe favorire loro quando la costruzione di alberi rosso-neri che vedranno un sacco di aggiornamenti.

Se si sa che si vedrà solo inserti, favorire nodi con due figli neri. Se sai che vedrà elimina solo, favorire i nodi con due figli rossi.

Answer 2

La risposta breve è: Dipende

.

In sostanza, ogni albero valida sarà sufficiente. Tuttavia, in termini di ammortizzato analisi - potrebbe molto probabilmente essere che si vuole scegliere il la maggior parte albero corretto che a lungo andare vi darà il comportamento più ottimizzato.

es. se si sceglie sempre un albero valida, ma uno che è incline a un sacco di operazioni di equilibratura, si otterrà cattive prestazioni ammortizzato. Un esempio evidente è un albero completamente nero, che è perfettamente valido, ma esegue male quando modificato.

Dipende, perché questo di solito sarà specifica per l'applicazione.