Alberi rosso-nero - Cancellazione di un nodo con due bambini non fogliari

Question

Ho implementato la mia versione di un albero rosso-nero, basando principalmente i miei algoritmi su Wikipedia (http://en.wikipedia.org/wiki/Red-black_tree). È abbastanza conciso per la maggior parte, ma c'è una parte su cui vorrei un chiarimento.

Quando si cancella un nodo dall'albero che ha 2 figli non foglia (non NULL), si dice di spostare i figli di entrambi i lati nel nodo cancellabile e rimuovere tale figlio.

Sono un po 'confuso su quale lato rimuovere da, in base a quello. Seleziono il lato in modo casuale, faccio alternare tra i lati, o mi appiccico allo stesso lato per ogni futura cancellazione?

Answer 1

Se non si conoscono i dati di input, non è possibile sapere quale lato è più vantaggioso di essere il nuovo nodo intermedio o il nuovo figlio.

Si può quindi semplicemente applicare la regola che più si adatta a te (è più facile scrivere/calcolare - probabilmente "prendi sempre quello di sinistra"). L'utilizzo di uno schema casuale in genere introduce solo un calcolo non necessario.