¿Qué rotación adicional se requiere para la eliminación de un árbol rojo negro Top-Down 2-3-4 de inclinación a la izquierda?

Question

He estado implementando un paquete LLRB que debería poder funcionar en cualquiera de los dos modos, Bottom-Up 2-3 o Top-Down 2-3-4 described by Sedgewick (code - código mejorado, aunque solo se trata de 2- 3 árboles here, gracias a RS para el puntero).

Sedgewick proporciona una descripción muy clara de las operaciones de árbol para el modo 2-3, aunque pasa mucho tiempo hablando del modo 2-3-4. También muestra cómo una simple alteración del orden de cambio de color durante la inserción puede alterar el comportamiento del árbol (dividir en el camino hacia abajo para 2-3-4 o dividir en el camino hacia arriba para 2-3):

private Node insert(Node h, Key key, Value value) 
{ 
    if (h == null) 
     return new Node(key, value); 

    // Include this for 2-3-4 trees 
    if (isRed(h.left) && isRed(h.right)) colorFlip(h); 

    int cmp = key.compareTo(h.key); 

    if (cmp == 0)  h.val = value; 
    else if (cmp < 0) h.left = insert(h.left, key, value); 
    else    h.right = insert(h.right, key, value); 

    if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); 
    if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); 

    // Include this for 2-3 trees 
    if (isRed(h.left) && isRed(h.right)) colorFlip(h); 

    return h; 
} 

Sin embargo, se pasa por alto en la eliminación 2-3-4 LLRBs con lo siguiente:

el código de la página siguiente es una implementación completa de delete() para LLRB 2-3 árboles. Se basa en el reverso del enfoque utilizado para insertar en árboles de arriba a abajo 2-3-4: realizamos rotaciones y volteos de color en el camino de búsqueda para garantizar que la búsqueda no finalice en un nodo 2, para que podamos simplemente eliminar el nodo en la parte inferior. Utilizamos el método fixUp() para compartir el código para el cambio de color y las rotaciones después de las llamadas recursivas en el código insert(). Con fixUp(), podemos dejar enlaces rojos de inclinación correcta y nodos desequilibrados a lo largo de la ruta de búsqueda, asegurándonos de que estas condiciones se solucionarán en el camino hacia arriba del árbol. (El enfoque también es eficaz 2-3-4 árboles, sino que requiere una rotación adicional cuando el nodo de la derecha de la ruta de búsqueda es un 4-nodo.)

Su función de borrado():

private Node delete(Node h, Key key) 
{ 
    if (key.compareTo(h.key) < 0) 
     { 
      if (!isRed(h.left) && !isRed(h.left.left)) 
      h = moveRedLeft(h); 
      h.left = delete(h.left, key); 
     } 
    else 
     { 
      if (isRed(h.left)) 
       h = rotateRight(h); 
      if (key.compareTo(h.key) == 0 && (h.right == null)) 
       return null; 
      if (!isRed(h.right) && !isRed(h.right.left)) 
       h = moveRedRight(h); 
      if (key.compareTo(h.key) == 0) 
       { 
        h.val = get(h.right, min(h.right).key); 
        h.key = min(h.right).key; 
        h.right = deleteMin(h.right); 
       } 
      else h.right = delete(h.right, key); 
     } 
    return fixUp(h); 
} 

Mi implementación mantiene correctamente invariantes LLRB 2-3 para todas las operaciones de árbol en 2-3 árboles, pero falla para una subclase de eliminaciones del lado derecho en 2-3-4 árboles (estas eliminaciones fallidas dan como resultado nodos rojos con inclinación hacia la derecha , pero desequilibrio bola de nieve a árbol y finalmente eliminación de referencias de puntero nulo). A partir de una encuesta del código de ejemplo que analiza árboles LLRB e incluye opciones para la construcción de árboles en cualquier modo, parece que ninguno implementa correctamente la eliminación de un LLRB 2-3-4 (es decir, ninguno tiene la rotación adicional aludida, por ejemplo, Sedgewick's java arriba y here).

Tengo problemas para entender exactamente lo que quiere decir con "rotación extra cuando el nodo derecho fuera de la ruta de búsqueda es un nodo 4"; presumiblemente este es un giro a la izquierda, pero ¿dónde y cuándo?

Si giro hacia la izquierda pasando más allá de un nodo de 4 nodos (es decir, nodo RR) o un nodo de 3 nodos con inclinación hacia la derecha (nodo BR) antes de llamar a fixUp() o al final de la función fixUp todavía me aparece la misma contradicción invariante.

Aquí están los estados del árbol de los ejemplos de fallas más pequeños que he encontrado (generados por la inserción secuencial de elementos desde 0 hasta el valor máximo respectivo).

El primer par de árboles muestra la transición del estado de conformidad invariante antes de la eliminación del elemento 15 al estado obviamente roto después.

El segundo es esencialmente el mismo que el anterior, pero con una deleción de 16 de 0 ..16 (eliminación de 15 resultados en la misma topología). Tenga en cuenta que la contradicción invariante se las arregla para cruzar el nodo raíz.

La clave va a ser la comprensión de cómo revertir las violaciónes generados durante el paseo por el árbol hasta el nodo de destino. Los dos árboles siguientes muestran cómo se ve el primer árbol de arriba después de una caminata hacia la izquierda y hacia la derecha respectivamente (sin eliminación y antes de volver a caminar con fixUp()).

Después intento de eliminar '-1' sin corrección:

Después intento de eliminar '16' sin corrección:

Tratando Girar a la izquierda en el camino de vuelta cuando el nodo tiene solamente un niño rojo derecho parece ser parte de la solución, pero no trata correctamente con dos niños rojos derechos consecutivos, precediendo esto con un flipColor cuando ambos niños son rojos parece mejorar la situación aún más, pero aún deja algunas invariantes violadas .

Si además verifico si el hijo correcto de un hijo derecho es rojo cuando su hermano es negro y gire a la izquierda si esto es cierto, solo fallaré una vez, pero en este momento siento que necesito una nueva teoría que un nuevo epiciclo

¿Alguna idea?

Como referencia, mi implementación está disponible here (No, no es Java).

Seguimiento:

Parte de la razón por la que estaba interesado en esta era confirmar la reclamación por muchos que LLRB 2-3 árboles son más eficientes que los árboles 2-3-4 LLRB. Mi evaluación comparativa ha confirmado esto para la inserción y la eliminación (2-3 son aproximadamente un 9% más rápido), pero creo que la recuperación es muy ligeramente más rápida para 2-3-4 árboles.

Los siguientes tiempos son representativos y consistentes a través de carreras:

BU23: 
BenchmarkInsert  1000000  1546 ns/op 
BenchmarkDelete  1000000  1974 ns/op 
BenchmarkGet   5000000   770 ns/op 

TD234: 
BenchmarkInsert  1000000  1689 ns/op 
BenchmarkDelete  1000000  2133 ns/op 
BenchmarkGet   5000000   753 ns/op 

La primera columna es el nombre de banco, segundo es el número de las operaciones, tercero es resultado. Benchmark en i5M 2.27.

He echado un vistazo a las longitudes de rama para 2-3 árboles y 2-3-4 árboles y hay poco que explicar la diferencia de recuperación (distancia media de raíz a nodo y SD de 1000 árboles cada uno con 10000 inserciones aleatorias):

Means: 
TD234 leafs BU23 leafs 
12.88940  12.84681 
TD234 all BU23 all 
11.79274  11.79163 

StdDev: 
TD234 leafs BU23 leafs 
1.222458  1.257344 
TD234 all BU23 all 
1.874335  1.885204 

Answer 1

actualizado y verificado

de importancia clave para la prueba de esto es que la aplicación no es compatible con la eliminación de un nodo existente o previamente eliminada! Pasé demasiado tiempo tratando de descubrir por qué mi solución de trabajo estaba "rota". Esto se puede solucionar haciendo una búsqueda preliminar de la clave y devolviendo el valor falso si no está en el árbol, y esa solución se empleó en el código vinculado en la parte inferior.

No aparece Sedgewick escribió una eliminación para 2-3-4 eliminación que está disponible públicamente.Sus resultados se refieren específicamente a 2-3 árboles (solo hace una breve mención de 2-3-4 árboles en el sentido de que su longitud de camino promedio (y por lo tanto el costo de búsqueda), así como la de otros árboles rojo-negro, es indistinguible de la 2-3 casos). Nadie parece tener uno fácilmente encontrado, entonces, esto es lo que encontré después de eliminar el problema:

Para comenzar, tome el código de Sedgewick y corrija los bits desactualizados. En las diapositivas here (pg 31) puede ver que su código todavía usa la representación anterior de 4 nodos donde se hizo teniendo dos rojos izquierdos en una fila, en lugar de equilibrio. El primer bit en escribir una rutina de eliminación 2-3-4 es, entonces, para solucionar este problema para que podamos hacer una comprobación de validez que le ayudará a verificar nuestras correcciones más tarde:

private boolean is234(Node x) 
{   
    if (x == null) 
     return true; 
    // Note the TD234 check is here because we also want this method to verify 2-3 trees 
    if (isRed(x.right)) 
     return species == TD234 && isRed(x.left); 

    if (!isRed(x.right)) 
     return true; 

    return is234(x.left) && is234(x.right); 
} 

Una vez que tenemos esto, saber un par de cosas Uno, del documento vemos que 4 nodos no se deben romper en el camino ascendente cuando se usa un árbol 2-3-4. Dos, hay un caso especial para un nodo 4 derecho en la ruta de búsqueda. Hay un tercer caso especial que no se menciona, y es cuando vuelves a subir un árbol, puedes terminar donde tienes h.right.left ser rojo, lo que te dejará inválido con solo girarlo a la izquierda. Este es el espejo del caso descrito para insertar en la página 4 del documento.

El arreglo de rotación para un 4-nodo que se necesita es la siguiente:

private Node moveRedLeft(Node h) 
    { // Assuming that h is red and both h.left and h.left.left 
     // are black, make h.left or one of its children red. 
     colorFlip(h); 
     if (isRed(h.right.left)) 
     { 
      h.right = rotateRight(h.right); 

      h = rotateLeft(h); 
      colorFlip(h); 

      if (isRed(h.right.right)) 
      h.right = rotateLeft(h.right); 
     } 
     return h; 
    } 

Y esto elimina la división de 2-3-4, así como añade la solución para el tercer caso especial

private Node fixUp(Node h) 
{ 
    if (isRed(h.right)) 
    {  
     if (species == TD234 && isRed(h.right.left)) 
     h.right = rotateRight(h.right); 
     h = rotateLeft(h); 
    } 

    if (isRed(h.left) && isRed(h.left.left)) 
     h = rotateRight(h); 

    if (species == BU23 && isRed(h.left) && isRed(h.right)) 
     colorFlip(h); 

    return setN(h); 
} 

Finalmente, tenemos que probar esto y asegurarnos de que funciona. No tienen que ser los más eficientes, pero como descubrí durante la depuración de esto, tienen que trabajar con el comportamiento esperado del árbol (es decir, no insertar/eliminar datos duplicados). Hice esto con un método de prueba de ayuda. Las líneas comentadas estaban allí para cuando estaba depurando, rompería y verificaría el árbol por un desequilibrio evidente. He probado este método con 100000 nodos, y es realizado sin problemas:

public static boolean Test() 
    { 
     return Test(System.nanoTime()); 
    } 
    public static boolean Test(long seed) 
    { 
     StdOut.println("Seeding test with: " + seed); 
     Random r = new Random(seed); 
     RedBlackBST<Integer, Integer> llrb = new RedBlackBST<Integer,Integer>(TD234); 
     ArrayList<Integer> treeValues = new ArrayList<Integer>(); 
     for (int i = 0; i < 1000; i++) 
     { 
     int val = r.nextInt(); 
     if (!treeValues.contains(val)) 
     { 
      treeValues.add(val); 
      llrb.put(val, val); 
     } 
     else 
      i--; 
     } 
     for (int i = 0; i < treeValues.size(); i++) 
     { 
     llrb.delete(treeValues.get(i)); 
     if (!llrb.check()) 
     { 
      return false; 
     } 
//   StdDraw.clear(Color.GRAY); 
//   llrb.draw(.95, .0025, .008); 
     } 
     return true; 
    } 

La fuente completo se puede encontrar here.