std :: map Conosciuto-Position Erase ammortizzato complessità e il numero di Red-Black Tree Recolorings

Question

La complessità del std::map::erase(iterator) è ammortizzato O (1) (vedi here, per esempio). Sebbene la libreria standard non imponga implementazioni, questo di fatto significa che il numero di operazioni di riequilibrio necessarie per un albero rosso-nero è ammortizzato O (1). In effetti, la voce di Wikipedia su alberi rosso-neri seems to confirm this:

Ripristino dell'impermeabilità rosso-nero richiede un numero piccolo (O (log n) o O ammortizzato (1)), di cambiamenti di colore (che sono molto veloci in pratica) e non più di tre rotazioni dell'albero (due per l'inserimento).

ma apparentemente senza un collegamento (e non ho potuto trovarlo in altri posti).

Poiché il numero di rotazioni è costante, l'ammortamento è sul numero di ricolorazioni necessarie sul percorso del nodo radice. Mentre la maggior parte dei nodi in un albero bilanciato sono verso il fondo dell'albero (e quindi il percorso medio è logaritmico), apparentemente viene ammortizzato O (1), che è sorprendente e interessante. Come si può dimostrare il costo costante ammortizzato?

Answer 1

In questa risposta presumo che tu abbia familiarità con l'analisi ammortizzata e sia a tuo agio con il metodo del banchiere. Immagino anche che tu conosca le invarianti dell'albero rosso-nero.

La risposta breve è per alcune piccole costanti k, mettere k monete su ogni nodo nero che non ha esattamente un bambino rosso.

Si noti che esiste un numero di algoritmi diversi per la cancellazione in un albero rosso-nero. Cancellare con un iteratore richiede ovviamente uno degli algoritmi bottom-up. L'analisi considera come l'algoritmo esegue o meno come segue:

1. Traverse verso l'alto fino a quando viene trovato un nodo nero. Questo è sempre possibile, poiché la radice è nera e non richiede mai più di due salti poiché i nodi rossi non possono avere figli rossi.

2. Eseguire un'operazione di "correzione" in tempo O (1) sul sottoalbero con radice su quel nodo nero. Se il fixup riduce l'altezza del sottostruttura o cambia il colore della radice dal nero al rosso, attraversa un ulteriore passaggio verso la radice e torna al # 1.

Ci vuole del lavoro per vedere che il n. 2 è possibile. In realtà, la complessità di questo è una delle motivazioni per gli alberi rosso-neri di sinistra di Sedgewick. Si tratta principalmente di elencare tutti i casi, eseguire una rotazione singola o doppia, quindi controllare attentamente che non siano stati violati gli invarianti.

Una variante del funzionamento correzione (che non è difficile da trovare se si dispone già di un'altra variante valido) conserva due invarianti supplementari durante il corso della attraversamento sull'albero:

1. Quando l'altezza della sottostruttura diminuisce di 1, la radice della sottostruttura (a) originariamente aveva due bambini neri (b) ora ha esattamente un bambino rosso.

2. Il sottostruttura non cambia mai il colore dal nero al rosso.

Così, ad ogni passo del attraversamento, sia

1. La radice della sottostruttura ha uno o due figli rossi. Eseguiamo O (1) lavoro, aggiungiamo al massimo O (1) monete e fermiamo

2. Eseguiamo lavoro O (1), indietro O (1) monete trasformando un nodo con due bambini neri in un nodo con un bambino rosso, e continuare

caso # 2 è ammortizzati libera, a condizione che il numero di monete è sufficiente a coprire i costi di ristrutturazione e ricolorazione in caso # 2. In quanto tale, il costo ammortizzato totale di un'eliminazione è il numero di volte in cui si verifica il caso n. 1 in una singola operazione di cancellazione, che è al massimo una, dal momento che dopo averla colpita ci fermiamo. O

---

Anche se questo riguarda la meccanica della aritmetica della spiegazione, in realtà non spiega il motivo per cui eliminare è ammortizzato (1).

Uno dei casi in cui agli studenti viene insegnato a volte il costo ammortizzato è il caso di incrementare un numero binario. Il costo è Ω (lg n) nel peggiore dei casi, ma O (1) nel senso ammortizzato, mettendo un numero costante di monete su ogni cifra '1'.

Analogamente, il decremento è O (1) ammortizzato ponendo un numero costante di monete su ciascuna cifra "0". Tuttavia, la miscelazione dei due rende ogni costo Ω (lg n), anche in un'impostazione ammortizzata, poiché l'analisi ammortizzata dipende da tutte le fasi di attraversamento eccetto l'ultima che restituisce un numero costante di monete indietro.

Questo tema di attraversamento è libero fino al punto di arresto è simile all'analisi dell'albero rosso-nero sopra riportata. Le cifre su cui devono essere messe le monete sono le cifre che rappresentano le regolazioni strutturali che stanno per essere fatte. Usando il metodo del fisico, l'energia potenziale viene aggiunta alla struttura per ogni cifra come questa.

Considerare una diversa rappresentazione di numeri binari in cui le cifre possono essere 0, 1, o 2 (ma la cifra d_i rappresenta ancora d_i * 2^i). Questo è chiamato binario ridondante. Ora è possibile posizionare un numero costante di monete su tutte le 0 o 2 cifre e ottenere un incremento e un decremento a tempo costante ammortizzati. Il motivo è che un incremento o decremento a cascata cambia da 0s o 2s a 1s, e quindi recupera sempre le monete.

Quindi, con due cifre, l'incremento o il decremento è O (1) ammortizzato, ma non entrambi e con tre, entrambi possono essere ammortizzati O (1). O

Allo stesso modo, sia l'inserimento o la cancellazione (ma non entrambi) è ammortizzato (1) in tutti:

alberi

1. rosso-nero in cui i nodi neri possono avere solo un figlio rosso

2. AA-alberi

3. 2-3 alberi

4. (a, 2a-1) alberi, per qualsiasi a> 1.

Mentre sia inserimento e cancellazione sono O (1) ammortizzati alberi rosso-nero, (2,4) alberi, e (a, 2a) alberi per ogni a> 1.