Ok, ho intenzione di provare questo, e forse le altre brave persone di SO possono dare una mano. Sapete come un modo di pensare di nodi rossi è come indicatori di
- dove non c'è uno squilibrio/nuovi nodi dell'albero, e
- quanto squilibrio c'è.
Ecco perché tutti i nuovi nodi sono rossi. Quando i nodi (localmente) si equilibrano, subiscono un capovolgimento del colore, e il rossore viene passato al genitore, e ora il genitore può sembrare squilibrato rispetto al fratello.
Come illustrazione, prendere in considerazione una situazione in cui si aggiungono nodi da più grandi a più piccoli. Si inizia con il nodo Z che ora è root ed è nero. Aggiungi il nodo Y, che è rosso ed è un figlio sinistro di Z. Aggiungi una X rossa come figlio di Z, ma ora hai due rossi successivi, quindi ruoti a destra, ricolora e hai un bilanciato, tutto nero (nessun squilibrio/"nuovi nodi"!) albero con radice su Y [primo disegno]. Ora aggiungi W e V, in questo ordine. All'inizio sono entrambi rossi [secondo disegno], ma immediatamente V/X/W vengono ruotati a destra e il colore viene capovolto, in modo che solo X sia rosso [terzo disegno]. Questo è importante: X essendo rosso indica che il sottoalbero sinistro di Y è sbilanciato di 2 nodi, o, in altre parole, ci sono due nuovi nodi nella sottostruttura di sinistra. Quindi l'altezza dei collegamenti rossi è il numero di nuovi nodi potenzialmente sbilanciati: ci sono 2^altezza di nuovi nodi nella sottostruttura rossa.
Nota come quando si aggiungono i nodi, il rossore è sempre lasciato perdere: a sua volta di colore, due figli rossi diventano nero (= localmente bilanciato), mentre la colorazione rossa il loro genitore. Essenzialmente ciò che fa la cancellazione, è invertire questo processo. Proprio come un nuovo nodo è rosso, vogliamo sempre anche eliminare un nodo rosso. Se il nodo non è rosso, vogliamo prima farlo diventare rosso. Questo può essere fatto con un capovolgimento del colore (per inciso, questo è il motivo per cui il capovolgimento del colore nel codice a pagina 3 è in realtà neutrale rispetto al colore). Quindi, se il bambino che vogliamo eliminare è nero, possiamo renderlo rosso colorando il suo genitore. Ora il bambino è garantito per essere rosso.
Il prossimo problema da affrontare è il fatto che quando iniziamo la cancellazione non sappiamo se il nodo di destinazione da eliminare sia rosso o meno. Una strategia sarebbe scoprire prima. Tuttavia, secondo la mia lettura del tuo primo riferimento, la strategia scelta è quella di garantire che il nodo cancellato possa essere reso rosso, "spingendo" un nodo rosso in basso di fronte al nodo di ricerca mentre stiamo cercando nell'albero per il nodo da cancellare. Ciò potrebbe creare nodi rossi non necessari che la procedura fixUp() risolverà durante il backup dell'albero. fixUp() mantiene invariabilmente i soliti invarianti LLRBT: "nessun nodo rosso successivo" e "nessun nodo rosso corretto".
Non sono sicuro se ciò sia di aiuto o se sia necessario approfondire l'esame del codice.
È ... intricato. – Thomas
@Thomas, un sacco di RB o LLRB stanno parlando solo di inserimento, nessuno parla davvero di cancellazione –