data-structures - negro - balancear arbol binario java
En los árboles rojo-negro, ¿la eliminación de arriba hacia abajo es más rápida y más eficiente desde el punto de vista del espacio que la eliminación de abajo hacia arriba? (2)
Por lo que veo: "eliminación de arriba hacia abajo" evita atravesar el mismo nodo en una ruta más de una vez durante la operación. Entonces, dado el camino simple desde la raíz hasta un nodo dado, si de todos modos vas a hacer algo con un nodo que está en esa ruta, ¿por qué no hacerlo en el camino de descenso? Evita tener que atravesar partes del camino más de una vez. Por lo tanto, esto ahorra tiempo.
Se emplea un principio similar para operaciones múltiples (incluido el inserto) en 2-3-4 árboles (un sub-caso especial de a, b-trees)
¿La eliminación de arriba hacia abajo minimiza el número de operaciones de reequilibrio?
Piensa que, en el caso promedio, sí. Debido a que hace que sea potencialmente más fácil insertar algo después con pocas operaciones de reequilibrio.
¿Podría ser posible que la supresión de arriba hacia abajo de manera proactiva haga demasiados re-colorantes y reequilibrios en el camino hacia abajo?
Tal vez, pero eso depende del conjunto de datos. Sin embargo, como se mencionó anteriormente. Esto puede reducir el número de re-coloraciones y reequilibrios en general.
En esta página, http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx "Eliminación vertical" es una implementación de una eliminación de nodo de árbol rojo-negro que equilibra de forma proactiva un árbol presionando un nodo rojo hacia abajo a través del árbol para garantizar que el nodo de la hoja que se está eliminando sea rojo. Como se garantiza que el nodo hoja es rojo, no tiene que preocuparse por volver a equilibrar el árbol, porque eliminar un nodo hoja roja no infringe ninguna regla y no tiene que realizar ninguna operación adicional para volver a equilibrarlo. equilibrar y restaurar el rojo-negro''ness.
"Eliminación ascendente" implica realizar una búsqueda binaria normal en el árbol para encontrar el nodo que se eliminará, intercambiando en el nodo hoja (si el nodo encontrado no es un nodo hoja) y luego restaurando las propiedades del árbol rojo-negro subiendo por el árbol mientras se arreglan las infracciones de reglas rojas y negras.
¿La eliminación de arriba hacia abajo minimiza el número de operaciones de reequilibrio? ¿Podría ser posible que la supresión de arriba hacia abajo de manera proactiva haga demasiados re-colorantes y reequilibrios en el camino hacia abajo?
¿Qué pasa con este escenario: (x) denota un nodo rojo
8
_____/ /____
/ /
4 12
/ / / /
2 6 10 14
/ / / / / / / /
1 3 5 7 9 11 13 15
/
(16)
Si deseo eliminar 16, una eliminación de abajo hacia arriba no haría ningún reequilibrio, pero una eliminación de arriba hacia abajo vuelve a colorear los nodos hasta el fondo, antes de descubrir que las operaciones de re-edición no eran necesarias:
iteración 1:
(8)
_____/ /____
/ /
4 12
/ / / /
2 6 10 14
/ / / / / / / /
1 3 5 7 9 11 13 15
/
(16)
iteración 2:
8
_____/ /____
/ /
(4) (12)
/ / / /
2 6 10 14
/ / / / / / / /
1 3 5 7 9 11 13 15
/
(16)
iteración 3:
8
_____/ /____
/ /
(4) 12
/ / / /
2 6 (10) (14)
/ / / / / / / /
1 3 5 7 9 11 13 15
/
(16)
Luego, en la iteración 4, descubres que no necesitas presionar hacia abajo porque 16 ya está en rojo. Entonces, ¿la eliminación de arriba hacia abajo es más eficiente en tiempo y espacio?
¿Es de arriba hacia abajo más eficiente en el uso del espacio que de abajo hacia arriba?
En una palabra, sí. El algoritmo de arriba hacia abajo presentado eternamente confundido no necesita punteros padres en los nodos. Los algoritmos de abajo hacia arriba se presentan con una compensación entre el tiempo y el espacio: los punteros de los padres permiten algunos cortocircuitos cuando se reequilibran después de la inserción y la eliminación.
Por ejemplo, la implementación de OpenJdk-7 de árboles Rojo-negro tiene punteros padres, lo que le permite elegir si es necesario o no volver a equilibrar después de una eliminación (como en su escenario).
¿Es descendente el tiempo más eficiente que el ascendente?
En general, sí: el enfoque descendente solo debe atravesar el árbol una vez por operación, mientras que el enfoque inferior debe atravesar el árbol dos veces por operación. Como mencioné anteriormente, los enfoques de abajo hacia arriba pueden reducir el tiempo usando punteros de los padres. Pero definitivamente no es un cruce de árboles completo cada vez.
Ambas implementaciones también pueden optar por utilizar el subprocesamiento para mejorar el tiempo o el espacio requerido para iterar a través de todo el árbol. Esto requiere la sobrecarga de una bandera o dos por nodo. Esto también se puede lograr usando punteros padres, pero no de manera tan eficiente. NB: el enlace de enhebrado dice que el enhebrado no es tan eficiente como los punteros de los padres, pero esto solo se aplica a los árboles de abajo hacia arriba (que cubre el libro).
Evidencia anecdótica
De vuelta a la universidad, implementamos eternamente confuzzled el árbol rojo-negro de arriba hacia abajo en C ++ e hicimos una comparación con la implementación de std :: map de nuestro STL (de abajo hacia arriba). Nuestro enfoque de arriba hacia abajo fue definitivamente más rápido; quiero decir que fue fácilmente 2 veces más rápido en todas las operaciones de mutación. La búsqueda también fue más rápida, pero no puedo decir si se debió a un árbol más equilibrado o a un código menos complejo.
Lamentablemente, ya no tengo el código ni la descripción.