5
He venido implementando mi propia versión de un árbol rojo-negro, sobre todo basando mis algoritmos de Wikipedia (http://en.wikipedia.org/wiki/Red-black_tree). Es bastante conciso en su mayor parte, pero hay una parte que me gustaría aclarar.árboles rojo-Negro - Borrado de un nodo con dos hijos que no son hojas
Al borrar un nodo del árbol que tiene 2 hijos no hoja (no NULL), dice mover los secundarios de cualquiera de los lados al nodo eliminable y eliminar ese elemento secundario.
Estoy un poco confundido en cuanto a qué lado va a quitar de, en base a eso. ¿Escojo el lado al azar, alterno entre lados o me pego al mismo lado para cada eliminación futura?
1 - evitar introducir deliberadamente comportamiento aleatorio; en algún momento, habrá un error en alguna parte, y el comportamiento al azar hará que los efectos del fallo más desconcertante, más difícil de reproducir consistentemente, etc. –
De acuerdo. La única situación en la que vale la pena introducir el comportamiento aleatorio es hacer que el peor de los casos patológicos ocurra con baja probabilidad e imprevisiblemente, en lugar de ocurrir de manera predecible en ciertas entradas. Por lo tanto, la elección del pivote aleatorio en qsort antes de la invención de introsort. No creo que el peor comportamiento de un árbol rojo oscuro sea lo suficientemente malo como para justificarlo aquí. Existe una conocida estructura aleatoria de árbol "probablemente equilibrada", pero no recuerdo el nombre por el momento. –
¡Gracias por su rápida respuesta! – Salami