Non tutti gli alberi rosso-neri sono bilanciati?

Question

Intuitivamente, "alberi bilanciati" dovrebbe essere alberi dove sinistra e destra sottoalberi per ogni nodo deve avere "approssimativamente lo stesso" numero di nodi.

Naturalmente, quando si parla di alberi rosso-neri * (vedere la definizione alla fine) viene bilanciato, in realtà significa che essi sono Altezza bilanciati e in questo senso, essi sono bilanciati.

Supponiamo cerchiamo di formalizzare l'intuizione di cui sopra nel seguente modo:

Definizione: un albero binario si chiama $ \ mu $ -balanced, con $ 0 \ le \ mu \ leq \ frac {1} {2} $, se per ogni nodo di $ N $, la disuguaglianza

$$ \ mu \ le \ frac {| N_L | + 1} {| N | + 1} \ le 1 - \ mu $$

detiene e per ogni $ \ mu' \ gt \ mu $, c'è qualche nodo per il quale la dichiarazione di cui sopra non riesce. $ | N_L | $ è il numero di nodi nel sotto-albero sinistro di $ N $ e $ | N |. $ È il numero di nodi sotto l'albero con $ N $ come root (tra cui la radice)

Credo, questi sono chiamati peso-equilibrato alberi nella parte della letteratura su questo argomento.

Si può dimostrare che se un albero binario con $ n $ nodi è $ \ mu $ -balanced (per una costante $ \ mu \ gt 0 $), allora l'altezza dell'albero è di $ \ mathcal {} O ( \ log n) $, mantenendo così le proprietà bello di ricerca.

Quindi la domanda è:

C'è qualche $ \ mu \ gt 0 $ tale albero che ogni abbastanza grande rosso-nero è $ \ mu $ -balanced?

---

La definizione di rosso-nero alberi che usiamo (da Introduzione agli algoritmi da Cormen et al):

Un albero binario di ricerca, in cui ogni nodo è colorato rosso o nero e

• La radice è nera
• Tutti i nodi sono NULL nero
• Se un nodo è rosso, allora entrambi i suoi figli sono neri.
• Per ogni nodo, tutti i percorsi da quel nodo ai nodi NULL discendenti hanno lo stesso numero di nodi neri.

Nota: non contiamo i nodi NULL nella definizione di $ \ mu $ -balanced sopra. (Anche se credo che non importa se facciamo).

Answer 1

Claim :. Alberi rosso-neri possono essere arbitrariamente ONU $ \ mu $ -balanced

Idea prova : Riempire il sottoalbero destro con il maggior numero di nodi possibile e la sinistra con il minor numero di nodi possibili per un dato numero di $ k $ di nodi neri su ogni percorso radice-foglia.

Prova : Definire una sequenza di $ T_k $ di alberi rosso-neri in modo che $ T_k $ ha $ k $ nodi neri su ogni percorso dalla radice ad ogni foglia (virtuale). Definire $ T_k = B (L_k, R_k) $ con

• $ R_k $ l'albero completo di altezza $ 2K - 1 $ con il primo, il terzo, ... livello colorato di rosso, gli altri neri, e
• $ L_k $ l'albero completo di altezza $ k-1 $ con tutti i nodi di colore nero.

Chiaramente, tutto $ T_k $ sono alberi rosso-neri.

Ad esempio, questi sono $ T_1 $ , $ T_2 $ e $ T_3 $ , rispettivamente:

---

^{[ fonte ]}

---

^{[ fonte ]}

---

^{[ fonte ]}

---

Ora lascia a verificare l'impressione visiva del diritto dell'essere lato enorme rispetto alla sinistra. Non voglio contare foglie virtuali; essi non influenzano il risultato.

Il sottoalbero sinistro di $ T_k $ è completo e dispone sempre di altezza $ k-1 $ e contiene quindi $ di 2 ^ k - 1 $ nodi. Il sottoalbero destro, d'altra parte, è completo e dispone altezza $ 2K - 1 $ e contiene questa convenzione $ di 2 ^ {2k } -1 $ nodi. Ora il $ \ mu $ Valore -Saldo per la radice è

$ \ qquad \ displaystyle \ frac {2 ^ k} {2 ^ k + 2 ^ {2k}} = \ frac {1} {1 + 2 ^ k} \ underset {k \ to \ infty} {\ a} 0 $

il che dimostra che non v'è alcuna $ \ mu> 0 $ , come richiesto.

Answer 2

No. Si consideri un albero rosso-nero con la seguente struttura speciale.

• Il sottoalbero sinistro è un albero binario completo con la profondità $ d $, in cui ogni nodo è nero.
• Il sottoalbero destro è un albero binario completo con la profondità $ 2d $, in cui è di colore rosso ogni nodo in profondità dispari, e ogni nodo in profondità ancora è nero.

E 'semplice per verificare che si tratta di un albero rosso-nero valida. Ma il numero di nodi nel sottoalbero destro ($ 2 ^ {2d + 1} -1 $) è più o meno il piazza il numero di nodi nel sottoalbero sinistro ($ 2 ^ {d + 1} - 1 $).