¿Cómo recordar fácilmente el inserto de árbol rojo-negro y eliminar?

Question

Es bastante fácil comprender completamente el árbol de búsqueda binario estándar y sus operaciones. Debido a esa comprensión, incluso no necesito recordar las implementaciones de esos insertos, eliminar, operaciones de búsqueda.

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

Entiendo al insertar un nuevo nodo, marcamos el nodo como rojo (porque el rojo es lo mejor que podemos hacer para evitar romper las leyes de árboles de negro menos rojo). El nuevo nodo rojo todavía puede romper la "Ley de nodos de rojo continuo". Luego lo arreglamos a través de:

1. Revisa el color de su tío, si está en rojo, luego marca su padre y tío como negro, y vaya al abuelo.

2. Si es el niño correcto, izquierda gire su padre

3. Marque su padre como negro y su abuelo como rojo, y luego gire a su abuelo.

   hecho (básicamente como arriba).

   Muchos lugares describen el inserto de árbol rojo rojo como el anterior. Solo te dicen cómo hacerlo. ¿Pero por qué esos pasos pueden arreglar el árbol? ¿Por qué girar por primera vez, y luego girar a la derecha?

   ¿Alguien puede explicar por qué más claramente, aún más claro que CLRS? ¿Cuál es la magia de la rotación?

   Realmente deseo entenderlo después de 1 año, puedo implementar el árbol rojo negro solo sin revisar un libro.

   gracias

Answer 1

ignorar mi comentario (ahora eliminado): creo que el código de Okasaki te va a ayudar. Si tiene el libro ("Estructuras de datos puramente funcionales"), mire el texto en la página 26 y la Figura 3.5 (orientada, P 27). Es difícil ser más claro que eso.

Lamentablemente La tesis disponible en línea no tener esa parte.

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

[Actualizar] Parece que puede ver esto en Amazon. Vaya a la página del libro , mouse sobre la imagen e ingrese "rojo negro" en el cuadro de búsqueda. Eso le brinda resultados que incluyen las páginas 25 y 26, pero debe iniciar sesión para verlas (aparentemente, no he intentado iniciar sesión para verificar).

Answer 2

Para el beneficio de cualquier otra persona que lee este hilo que no tiene acceso al libro mencionado en la respuesta aceptada, aquí es lo que espero que sea una respuesta descriptiva aceptable.

Rotating pone el árbol en un estado donde cumple con los criterios a la recolección (el nodo secundario 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 recolorar el padre y el tío a negro y al abuelo a rojo, recolore al padre a rojo, y el abuelo a negro.

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

  Ahora veamos cómo la rotación transforma el árbol para que tengamos un nodo secundario con un tío rojo y pueda usar la recolorización. Recomiendo sacar esto para entenderlo completamente.

  • Sea x el nodo rojo actual con un padre rojo.
  • Sea P el padre rojo de X antes de la rotación (si el padre era negro, ya lo haríamos).
  • Sea y 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 recoloraríamos a los padres y el tío a Black y el abuelo a rojo).
  • Sea g el abuelo negro de X antes de la rotación (ya que el padre es rojo, el abuelo debe ser negro; De lo contrario, esto no era un árbol rojo negro para comenzar.)
  • Cuando tiene una caja izquierda (LL) o derecha derecha (RR) (es decir, X es el niño izquierdo de P y P es el niño izquierdo de G o X es el niño derecho de P y P es el hijo correcto de G), después de una sola rotación (derecha si está, se fue si RR), Y se convierte en el niño y x su tío. Dado que X es un tío rojo, ahora tiene un caso en el que puede recolir. Entonces, recolora al padre del niño (ya que el niño es ahora, su padre es G) a rojo, y el abuelo del niño (que es ahora P) a Black.
  • Cuando tiene un LR (X es el niño izquierdo o P y P es el niño derecho de g) o la caja RL (x es el niño derecho de P y P es el niño izquierdo de G), después de una doble rotación (A la derecha se deja si LR, se fue, entonces derecha si RL), Y se convierte en el niño y P su tío. Como P es un tío rojo, usted nuevamente tiene un caso en el que pueda recolorar. Entonces, recolore a los padres (ya que el niño es ahora y, su padre es G) a rojo, y el abuelo del niño (que ahora es x) a negro.

    Antes de la rotación y la recoloración, tuvo 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 (lo opuesto al lado A). Después de la rotación y la recolorización, 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. para que esencialmente movió uno de los nodos rojos del otro sub-árbol de El abuelo sin aumentar la altura negra del sub-árbol.

    Esa es la magia de la rotación. Le permite mover el nodo rojo adicional a otra rama sin cambiar la altura negra, y aún conservar la propiedad de recorrido ordenado de un árbol de búsqueda binario.

Answer 3

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

en el caso (2) O (a) Z es el niño izquierdo de su padre, entonces el paso 3 será el último paso ya que se cumplen todas las propiedades de BST.Hecho. o (b) z es el niño derecho de su padre.Paso 2 convertirá el problema en caso (a).Entonces haz el paso 3.Hecho.

Por lo tanto, la lógica es tratar de alcanzar el caso (1) y (2a), lo que ocurra primero.Esas son las situaciones que conocemos las soluciones.

Answer 4

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

Una vez que tenga una comprensión clara de 2-4 árboles, cuando se ocupe de los árboles negros rojos, puede multicer a estos árboles negros rojos a 2-4 árboles y llegar a una lógica por sí mismo.

Encontré después de un par de videos que son extremadamente útiles para comprender 2-4 árboles, árboles rojos y negros y mapeo de 2-4 árboles a árboles negros rojos. Recomendaría pasar por estos videos.

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

2) Para árboles rojos y negros: http://www.youtube. com / watch? v= jrsn4oz36qu & list= plbf3763af2e1c572f & index= 14

Aunque son videos de una hora y largos, sentí que valía la pena atravesarlos.

Answer 5

Tal vez valga la pena comenzar con árboles negros rojos que se inclinan a la izquierda .Ofrecen una implementación simplificada interesante.

Answer 6

Realmente haces una buena conclusión de que tres casos.

Después de la inserción en RB-árbol, dejó un problema principal para resolver si hay. ¡Hay dos nodos rojos continuos! ¿Cómo podríamos hacer que desaparezcan dos nodos rojos continuos sin violar esa regla (cada camino tiene el mismo nodo negro con conteo) Así que vemos los dos nodos, solo existe 3 circurm ...

Lo siento, podría ver el libro de texto de instrucciones a los algoritmos

Ningún cuerpo puede ayudarlo a pensar a través de RB-TREE.Solo pueden guiarlo en algún punto clave.