¿Qué rotación adicional se requiere para la eliminación de un árbol Rojo Negro de arriba hacia abajo 2-3-4 inclinado hacia la izquierda?
He estado implementando un paquete LLRB que debería ser capaz de operar en cualquiera de los dos modos, Bottom-Up 2-3 o Top-Down 2-3-4 descrito por Sedgewick (code - código mejorado, aunque tratando solo con 2-3 árboles aquí, gracias a RS para 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 el cambio de color durante la inserción puede alterar el comportamiento del árbol (ya sea 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, pasa por alto la eliminación en 2-3-4 LLRBs con lo siguiente:
El código de 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 2-3-4 árboles de arriba hacia abajo: realizamos rotaciones y volteos de color en el camino hacia abajo de la ruta de búsqueda para garantizar que la búsqueda no termina en un nodo 2, por lo que solo podemos eliminar el nodo en la parte inferior. Usamos 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 inclinados a la derecha y 4 nodos desequilibrados a lo largo de la ruta de búsqueda, asegurando que estas condiciones se arreglarán en el camino hacia el árbol. ( El enfoque también es efectivo 2-3-4 árboles, pero requiere una rotación adicional cuando el nodo derecho la ruta de búsqueda es de 4 nodos.)
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 resultan en nodos rojos inclinados hacia la derecha, pero bola de nieve al desequilibrio del árbol y finalmente desreferenciación de puntero nulo). De un estudio de código de ejemplo que analiza los árboles LLRB e incluye opciones para la construcción de árboles en cualquiera de los dos mode, parece que ninguno implementa correctamente la eliminación de un LLRB 2-3-4 (es decir, ninguno tiene la rotación adicional a la que se alude, por ejemplo, java de Sedgewick arriba y aquí).
Estoy teniendo problemas para averiguar exactamente lo que quiere decir con "rotación adicional cuando el nodo derecho fuera de la ruta de búsqueda es un nodo de 4"; presumiblemente esto es una rotación a la izquierda, pero ¿dónde y cuándo?
Si giro hacia la izquierda pasando hacia arriba más allá de un equivalente de 4 nodos (es decir, nodo RR) o un equivalente de 3 nodos inclinado hacia la derecha (nodo BR) ya sea antes de llamar a fixUp () o al final de la función fixUp todavía obtengo la misma contradicción invariante.
Aquí están los estados de árbol de los ejemplos fallidos 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 la supresión de 16 de 0..16 (la supresión de 15 resulta en la misma topología). Nótese que la contradicción invariante logra cruzar el nodo raíz.
La clave va a ser entender cómo revertir las violaciones generadas durante la caminata por el árbol al nodo de destino. Los siguientes dos árboles muestran cómo el primer árbol de arriba se ve después de una caminata por la izquierda y la derecha respectivamente (sin eliminación y antes volver a subir con fixUp()).
Después de intentar eliminar '-1' sin reparación:
Después de intentar eliminar '16' sin reparación:
Intentar girar a la izquierda en la caminata hacia arriba cuando el nodo tiene solo un hijo derecho rojo parece ser parte de la solución, pero no trata correctamente con dos hijos derechos rojos en una fila, precediendo esto con un flipColor cuando ambos hijos son rojos parece mejorar la situación aún más, pero aún deja algunas invariantes violado.
Si compruebo más si el hijo correcto de un hijo correcto es rojo cuando su hermano es negro y rotar a la izquierda si esto es cierto solo fallo una vez, pero en este punto siento que estoy necesitando una nueva teoría en lugar de un nuevo epiciclo.
¿Alguna idea?
Como referencia, mi implementación está disponible aquí (No, no es Java).
Seguimiento:
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 eliminación (2-3 son aproximadamente 9% más rápido), pero encuentro que la recuperación es muy ligeramente más rápida para 2-3-4 árboles.
Los siguientes tiempos son representativos y consistentes entre corridas:
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, la tercera es el resultado. Benchmark en i5M 2.27.
He echado un vistazo a la longitud de las ramas para 2-3 árboles y 2-3-4 árboles y hay poco en que para explicar la diferencia de recuperación (distancia media de la raíz al 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
1 answers
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 averiguar por qué mi solución de trabajo estaba "rota". Esto se puede arreglar haciendo una búsqueda preliminar de la clave y devolviendo false si no está en el árbol en absoluto, 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 2-3-4 eliminación que está a disposición del público. Sus resultados tratan específicamente de 2-3 árboles (solo hace una mención superficial de 2-3-4 árboles en que su longitud promedio de camino (y por lo tanto el costo de búsqueda), así como la de otros árboles rojo-negro, es indistinguible del caso 2-3). Nadie más parece tener uno fácilmente encontrado, tampoco, así que esto es lo que encontré después de depurar el problema:
Para empezar, toma el código de Sedgewick y arregla los bits obsoletos. En las diapositivas aquí (pg 31) usted puede vea que su código todavía utiliza la antigua representación de 4 nodos donde se hizo al tener dos rojos izquierdos en una fila, en lugar de equilibrar. El primer bit para escribir una rutina de borrado 2-3-4, entonces, es arreglar esto para que podamos hacer una comprobación de cordura que nos 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, sabemos un par de cosas. Uno, del papel vemos que 4 nodos no deben romperse en el camino hacia arriba cuando se usa un árbol 2-3-4. Dos, hay un caso especial para un 4-nodo derecho en el ruta de búsqueda. Hay un tercer caso especial que no se menciona, y es que cuando regresas a un árbol, puedes terminar donde tienes h.right.left ser rojo, lo que te dejaría inválido con solo girar a la izquierda. Este es el espejo del caso descrito para insertar en la página 4 del documento.
La solució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, así como 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, necesitamos prueba esto y asegúrate de que funciona. No tienen que ser los más eficientes, pero como encontré 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 una prueba de métodos de ayuda. Las líneas comentadas estaban allí para cuando estaba depurando, rompería y revisaba el árbol en busca de un desequilibrio obvio. He probado este método con 100000 nodos, y funcionó perfectamente:
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;
}
Se puede encontrar la fuente completa aquí.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-07-11 06:07:21