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

red black tree visualization

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 descritos por 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 por 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, pasa por alto la eliminación en 2-3-4 LLRB con lo siguiente:

El código en la página siguiente es una implementación completa de delete () para árboles LLRB 2-3. 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, pero requiere una rotación adicional cuando el nodo derecho fuera de la ruta de búsqueda es un nodo 4 ) .

Su función delete ():

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 las 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 bola de nieve hacia desequilibrio de árbol y finalmente desreferenciación 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 qué 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 hacia arriba 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, sigo teniendo la misma contradicción invariable .

Aquí están los estados de los árboles 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 invariable 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 la eliminació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 será comprender cómo revertir las violaciones generadas durante la caminata por el árbol hasta el nodo objetivo. 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 de intentar eliminar ''-1'' sin arreglar:

Después de intentar eliminar ''16'' sin fixUp:

Intentar girar a la izquierda en la caminata de regreso cuando el nodo tiene solo un niño rojo derecho parece ser parte de la solución, pero no trata correctamente con dos niños rojos derechos seguidos, 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 gira hacia la izquierda si esto es cierto, solo fallaré una vez, pero en este momento siento que necesito una nueva teoría en lugar de un nuevo epiciclo. .

¿Algunas ideas?

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

Seguir:

Parte de la razón por la que estaba interesado en esto fue para confirmar la afirmación de muchos de que 2-3 árboles LLRB son más eficientes que 2-3-4 árboles 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 en todas las ejecuciones:

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 del banco, la segunda es el número de operaciones, el tercero es el 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 para explicar la diferencia de recuperación (distancia media de raíz a nodo y SD de 1000 árboles cada uno con 10000 insertos aleatorios):

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 probar esto es que la implementación no admite la eliminación de un nodo inexistente o previamente eliminado! 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 parece que Sedgewick haya escrito una eliminación para la eliminación 2-3-4 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 depurar el problema:

Para comenzar, tome el código de Sedgewick y arregle los bits desactualizados. En las diapositivas here (página 31) puede ver que su código todavía usa la representación anterior de 4 nodos donde se hizo teniendo dos rojos de la izquierda en una fila, en lugar de equilibrio. El primer paso para escribir una rutina de eliminación de 2-3-4, entonces, es arreglar esto para que podamos hacer una verificación de cordura que nos ayudará a verificar nuestras correcciones más adelante:

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, sabemos 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. Este es el espejo del caso descrito para insertar en la página 4 del documento.

La corrección de rotación para un nodo 4 que 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 en 2-3-4, y agrega 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 funcione. No tienen que ser los más eficientes, pero como descubrí durante la depuración de esto, tienen que trabajar realmente 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. Probé este método con 100000 nodos y funcionó a la perfección:

 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 completa se puede encontrar here .