algorithm - geeksforgeeks - red black tree simulator

¿Cómo recordar fácilmente Insertar y eliminar árbol rojo-negro? (6)

Cualquier árbol 2-4 (2-3-4) se puede convertir en un árbol Rojo-negro. Y la comprensión de 2-4 árboles es mucho más fácil. Si solo realiza las operaciones de insertar y eliminar en 2-4 árboles, sentirá que no hay necesidad de recordar ninguna regla para lograr lo mismo. Verá una lógica simple y clara que le permite llegar a soluciones para encargarse de diferentes escenarios de inserción y eliminación.

Una vez que tenga una comprensión clara de 2-4 árboles, cuando trate con árboles Rojo-negros, puede mapear mentalmente estos árboles Rojo-negros a 2-4 árboles y obtener una lógica usted mismo.

Encontré el siguiente par de videos que son extremadamente útiles para comprender 2-4 árboles, árboles rojo-negro y mapeo de 2-4 árboles a árboles Rojo-negro. Yo recomendaría revisar estos videos.

1) Para 2-4 árboles: http://www.youtube.com/watch?v=JZhdUb5F7oY&list=PLBF3763AF2E1C572F&index=13

2) Para árboles Red-black: http://www.youtube.com/watch?v=JRsN4Oz36QU&list=PLBF3763AF2E1C572F&index=14

A pesar de que son videos de una hora cada uno, sentí que valía la pena revisarlos.

Es bastante fácil comprender completamente el árbol de búsqueda binaria estándar y sus operaciones. Debido a esa comprensión, ni siquiera necesito recordar las implementaciones de esas operaciones de inserción, eliminación y búsqueda.

Estoy aprendiendo árbol rojo-negro ahora y entiendo sus propiedades para mantener el árbol equilibrado. Sin embargo, me resulta muy difícil entender sus procedimientos de inserción y eliminación.

Entiendo que cuando inserte un nuevo nodo, marcaremos el nodo como rojo (porque el rojo es lo mejor que podemos hacer para evitar que se rompan menos leyes de árboles Rojo-Negro). El nuevo nodo rojo aún puede romper la "ley de nodos rojos continuos". Luego lo solucionamos a través de:

verifique el color de su tío, si es rojo, luego marque a su padre y su tío como negros, y vaya a abuelo.
si es el niño correcto, gire a la izquierda su padre
marque su padre como negro y su abuelo como rojo, luego gire a la derecha a su abuelo.

hecho (básicamente como arriba).

Muchos lugares describen el inserto del árbol Rojo-Negro como se muestra arriba. Simplemente te dicen cómo hacerlo. Pero, ¿por qué esos pasos pueden arreglar el árbol? ¿Por qué girar primero a la izquierda y luego girar a la derecha?

¿Alguien puede explicarme por qué es más claro, incluso más claro que CLRS? ¿Cuál es la magia de la rotación?

Realmente deseo entender que, después de 1 año, puedo implementar el árbol Rojo-Negro yo solo sin revisar un libro.

Gracias

En beneficio de cualquier otra persona que lea este hilo que no tenga acceso al libro mencionado en la respuesta aceptada, aquí está lo que espero que sea una respuesta descriptiva aceptable.

Rotar pone al árbol en un estado donde cumple los criterios para volver a colorear (el nodo hijo tiene un tío rojo). Hay dos diferencias clave:

qué nodo es el "niño" y qué nodo es el "tío" ha cambiado;
en lugar de cambiar el color al padre y al tío, y al abuelo al rojo, se vuelve a colorear al padre al rojo y al abuelo al negro.

Cuando el nodo hijo no tiene un tío rojo, tiene que rotar porque si el nodo tío ya es negro, entonces hacer que el padre sea negro aumentaría la altura negra en 1 solo en un lado del abuelo. Esto violaría la propiedad invariante en altura de los árboles rojo-negros y haría que el árbol se desequilibrara.

Ahora veamos cómo la rotación transforma el árbol para que tengamos un nodo hijo con un tío rojo y podamos usar el rediseño. Recomiendo dibujar esto para entenderlo completamente.

Deje x ser el nodo rojo actual con un elemento primario rojo.
Deje p ser el padre rojo de x antes de la rotación (si el padre era negro, ya habríamos terminado).
Deje que sea el tío negro de x antes de la rotación (si el tío fuera rojo, no necesitaríamos una rotación. Simplemente cambiaríamos el color del padre y el tío al negro y el abuelo al rojo).
Deje g ser el abuelo negro de x antes de la rotación (ya que el padre es rojo, el abuelo debe ser negro, de lo contrario, este no era un árbol rojo-negro para empezar).
Cuando tiene un caso de izquierda a izquierda (LL) o de derecha a derecha (RR) (es decir, x es el hijo izquierdo de p y p es el hijo izquierdo de g OR x es el hijo derecho de p y p es el derecho hijo de g), después de una sola rotación (derecha si LL, izquierda si RR), y se convierte en el niño yx es su tío. Como x es un tío rojo, ahora tienes un caso en el que puedes cambiar el color. Por lo tanto, vuelva a colorear el padre del niño (dado que el niño ahora está y, su padre está g) en rojo, y el abuelo del niño (que ahora es p) en negro.
Cuando tienes un LR (x es el hijo izquierdo op y p es el hijo derecho de g) o RL caso (x es el hijo derecho de p y p es el hijo izquierdo de g), después de una doble rotación (en ese momento izquierda si LR, izquierda y luego derecha si RL), y se convierte en el niño yp su tío. Como p es un tío rojo, nuevamente tiene un caso en el que puede cambiar el color. Por lo tanto, vuelva a colorear el padre (ya que el hijo ahora es y, su padre es g) en rojo, y el abuelo del niño (que ahora es x) en negro.

Antes de la rotación y la recoloración, tenía un abuelo negro con 2 nodos rojos y 0 nodos negros en el lado A (izquierda o derecha) y 0 nodos rojos y 1 nodo negro en el lado B (opuesto al lado A). Después de la rotación y el cambio de color, tiene un abuelo negro con 1 nodo rojo y 0 nodos negros en el lado A y 1 nodo rojo y 1 nodo negro en el lado B. Por lo tanto, básicamente movió uno de los nodos rojos al otro subárbol de el abuelo sin aumentar la altura negra de ninguno de los subárboles.

Esa es la magia de la rotación. Le permite mover el nodo rojo adicional a otra rama sin cambiar la altura del negro, y aún preservar la propiedad transversal cruzada de un árbol de búsqueda binario.

La lógica es bastante simple. Supongamos que z es rojo y el padre de z es rojo: si el tío de z es rojo, haga el paso 1 para empujar el nodo problemático hacia arriba hasta que (1) el padre se convierta en la raíz. Luego simplemente marque la raíz negra. Hecho o (2) el tío de z es negro.

En el caso (2) ya sea que (a) z sea el hijo izquierdo de su elemento primario, entonces el paso 3 será el último paso ya que se cumplen todas las propiedades de BST. Hecho. o (b) z es el hijo correcto de su padre. El paso 2 convertirá el problema en el caso (a). Luego haz step3. Hecho.

Por lo tanto, la lógica es intentar llegar al caso (1) y (2a), lo que ocurra primero. Esas son las situaciones en que conocemos las soluciones.

Quizás vale la pena comenzar con árboles negros rojos de inclinación izquierda . Ofrecen una implementación simplificada interesante.

ignore mi comentario (ahora borrado) - creo que el código de okasaki lo ayudará. si tiene el libro ("estructuras de datos puramente funcionales"), mire el texto en la página 26 y la figura 3.5 (frente, p 27). es difícil ser más claro que eso.

desafortunadamente, la tesis disponible en línea no tiene esa parte.

No voy a copiarlo porque el diagrama es importante, pero muestra que todos los casos diferentes son básicamente lo mismo, y da un código ML muy simple que martilla ese hogar.

[actualización] parece que es posible que puedas ver esto en Amazon. vaya a la página del libro , coloque el mouse sobre la imagen e ingrese "rojo negro" en el cuadro de búsqueda. eso le da resultados que incluyen las páginas 25 y 26, pero debe iniciar sesión para verlos (aparentemente, no he intentado iniciar sesión para verificar).

realmente haces una buena conclusión que tres casos.

después de la inserción en RB-Tree, queda un problema principal que resolver si existe. ¡Hay dos nodos rojos continuos! ¿Cómo podemos hacer que desaparezcan dos nodos rojos continuos sin violar esa regla (cada ruta tiene el mismo nodo negro de conteo) por lo que vemos los dos nodos, solo existe 3 circurm ...

Lo siento, podrías ver el libro de texto de Instrucción a Algoritmos

ningún cuerpo puede ayudarte a pensar a través de rb-tree. solo pueden guiarte en algún punto clave.