Imagina un árbol rojo-negro. ¿Hay siempre una secuencia de inserciones y eliminaciones que lo crea?

Supongamos la siguiente definición de un árbol rojo-negro:

Es un árbol de búsqueda binario.
Cada nodo es de color rojo o negro. La raíz es negra.
Dos nodos conectados por un borde no pueden ser rojos al mismo tiempo.
Aquí debería haber una buena definición de una hoja NIL, como en wiki. La hoja NIL es de color negro.
Una ruta desde la raíz a cualquier hoja NIL contiene el mismo número de nodos negros.

Pregunta

Supongamos que ha implementado las operaciones inserty deletepara el árbol rojo-negro. Ahora, si se le da un árbol rojo-negro válido, ¿hay siempre una secuencia inserty deleteoperaciones que lo construyan?

Motivación

Esta pregunta está motivada por esta pregunta y por la discusión de esta pregunta .

Personalmente, creo que si imaginas un árbol rojo-negro válido que consta solo de nodos negros (lo que implica que estás imaginando un árbol perfectamente equilibrado), hay una secuencia inserty deleteoperaciones que lo construyen. Sin embargo,

No sé cómo demostrar con precisión que
También estoy interesado en el caso más general

data-structures search-trees balanced-search-trees alisianoi
fuente

Su pregunta suena un poco circular ... cualquier conjunto de operaciones de inserción y eliminación construirá un árbol rojo-negro ... literalmente cualquier cosa, ya que rojo-negro es solo una definición. ¿Su pregunta se limita a un árbol puramente negro?

JOX

No, creo que lo malinterpretas. Por supuesto, cualquier conjunto de inserciones y eliminaciones construye algún árbol rojo-negro. La pregunta es esta: ¿algún árbol que se ajuste a la definición es construible por alguna secuencia de inserciones y eliminaciones? Si le dan algún árbol, ¿puede recrear una secuencia de inserciones y eliminaciones?

alisianoi

@ all3fox Sí, tienes razón. Hay un algoritmo que utiliza la operación inserty deletepara construir un árbol rojo-negro válido que consta solo de nodos negros . Utiliza inserciones / eliminaciones para crear un árbol de altura . Primero, podemos crear un árbol rojo-negro perfectamente equilibrado en primer lugar usando inserciones, luego usando inserciones y la misma cantidad de eliminaciones repítelo en Un árbol completamente negro. El truco aquí es subir veces la capa roja más baja del árbol hasta que llegue a la raíz.

(h + 2) \cdot 2^{h} - 1

$(h + 2) \cdot 2^h - 1$

h

$h$

2^{h + 1} - 1

$2^{h+1} - 1$

h * 2^{h - 1}

$h * 2^{h-1}$

h

$h$

Anton Trunov

@AntonTrunov gracias, entiendo eso. ¿Qué tal el caso de un árbol rojo-negro general? ¿Qué crees que es posible construir cualquier árbol rojo-negro con inserty deleteoperaciones?

alisianoi

a) La respuesta dependerá de la implementación precisa de inserty delete; Puede haber varias formas de hacer estas operaciones. b) Dado que los árboles RB son esencialmente árboles B de orden 4, se puede buscar inspiración. Los detalles pueden resultar complicados ya que la asignación de RB a B (y / o al revés) no es única.

Raphael

Respuestas:

Las operaciones de inserción y eliminación en un árbol rojo-negro incluyen el equilibrio necesario para mantener las propiedades rojo-negro.

El problema con los árboles negros rojos que no se inclinan (izquierda o derecha) es que hay varias formas de restaurar el rojo-negro después de la eliminación o inserción básica.
No es la inserción o la eliminación lo que transforma el árbol, sino el reequilibrio y la rotación que se producen después para preservar / restaurar la negrura roja del árbol.

La descripción básica del árbol rojo-negro no prescribe cuáles de las posibles rutas tomar.
Puede que no sea posible descubrir cómo reconstruir exactamente un árbol negro rojo dado, porque el reequilibrio no necesita ser determinista.

Esto ha sido 'resuelto' con árboles negros rojos inclinados a la izquierda.
Solo hay una forma de hacer el equilibrio. Por lo tanto, cualquier árbol negro rojo inclinado se puede reconstruir usando inserciones y eliminaciones, porque el reequilibrio / rotaciones se realizan de una manera determinista específica.

Esto no significa que los árboles RB inclinados a la izquierda sean mejores o más eficientes, lo que obtienen por un lado al usar reglas de equilibrio deterministas, por otro pierden por un código de equilibrio más complejo.

Según el comentario de @ Anton:
hay un algoritmo que utiliza la operación insertar y eliminar para construir un árbol rojo-negro válido que consta solo de nodos negros. Utiliza inserciones / eliminaciones para crear un árbol de altura . Primero, podemos crear un árbol rojo-negro perfectamente equilibrado en primer lugar usando inserciones , luego usando inserciones y la misma cantidad de eliminaciones lo vuelven a pintar Un árbol completamente negro. El truco aquí es subir veces la capa roja más baja del árbol hasta que llegue a la raíz. $(h+2)⋅2^{h}−1$ $h$ $2^{h+1}−1$ $h∗2^{h-1}$ $h$

Sin embargo, creo que un algoritmo de equilibrio completo como Day-Stout-Warren sería más eficiente.

Johan
fuente

Usando las operaciones inserty deletedesde el libro CLRS puede construir un árbol RB válido que consista solo de nodos negros . El truco consiste en insertar más nodos de los necesarios y luego eliminar los excesos. El algoritmo será eliminar nodos rojos.

Anton Trunov

@AntonTrunov, ¿tiene un enlace para ese algoritmo? Sería bueno incluirlo en la respuesta. No puedo encontrarlo usando mi google-fu.

Johan

Lamentablemente no tengo un enlace. Traté de responder la pregunta en ese momento y se me ocurrió un algoritmo para el caso especial de todos los árboles RB negros. Lo describí en ese comentario, pero no proporcioné una prueba.

Anton Trunov

¿Qué quiere decir con "Esto ha sido 'resuelto' con árboles negros rojos inclinados a la izquierda". Incluso un árbol rojo negro inclinado hacia la izquierda tiene múltiples formas de almacenar los mismos artículos.

user239558