c++ - ventajas - eliminacion arbol rojo negro
¿Por qué se implementa std:: map como un árbol rojo-negro? (6)
Actualización 2017-06-14: webbertiger edita su respuesta después de que comencé. Debo señalar que su respuesta ahora es mucho mejor para mí. Pero mantuve mi respuesta solo como información adicional ...
Debido al hecho de que creo que la primera respuesta es incorrecta (corrección: ya no ambas) y la tercera tiene una afirmación equivocada. Siento que tengo que aclarar las cosas ...
Los 2 árboles más populares son AVL y Red Black (RB). La principal diferencia radica en la utilización:
- AVL: Mejor si la relación de consulta (lectura) es mayor que la manipulación (modificación). La huella de memoria es un poco menor que RB (debido a la broca requerida para colorear).
- RB: Mejor en los casos generales donde hay un equilibrio entre la consulta (lectura) y la manipulación (modificación) o más modificaciones durante la consulta. Una huella de memoria ligeramente mayor debido al almacenamiento de la bandera roja-negra.
La principal diferencia proviene del color. Tiene menos acción de reequilibrio en el árbol RB que AVL porque el color le permite a veces omitir o acortar las acciones de reequilibrio que tienen un costo relativo alto. Debido a la coloración, el árbol RB también tiene un nivel más alto de nodos porque podría aceptar nodos rojos entre los negros (con posibilidades de ~ 2x niveles más) haciendo que la búsqueda (lectura) sea un poco menos eficiente ... pero porque es una constante (2x), permanece en O (log n).
Si considera el rendimiento alcanzado para una modificación de un árbol (significativo) VS el resultado de la consulta de un árbol (casi insignificante), es natural preferir el RB sobre el AVL para un caso general.
¿Por qué se implementa std :: map como un árbol rojo-negro ?
Existen varios árboles de búsqueda binaria equilibrados (BST). ¿Cuáles fueron las ventajas y desventajas del diseño al elegir un árbol rojo-negro?
Es solo la elección de su implementación: podrían implementarse como cualquier árbol equilibrado. Las diversas opciones son todas comparables con diferencias menores. Por lo tanto, cualquiera es tan bueno como cualquier otro.
Las respuestas anteriores solo abordan las alternativas de árbol y el rojo negro probablemente solo permanezca por razones históricas.
¿Por qué no una tabla hash?
En una estructura de árbol, un tipo solo requiere un orden parcial (<comparación) para poder usarse como clave en el mapa. Por el contrario, las tablas hash requieren que el tipo tenga definida una función hash. Dado que un enfoque principal de STL es la programación genérica, es muy importante mantener estos requisitos de tipo al mínimo.
Diseñar una buena tabla hash requiere un conocimiento profundo del contexto en el que se utilizará ¿Debería usar un direccionamiento abierto o un encadenamiento vinculado? ¿Qué niveles de carga debería aceptar antes de cambiar el tamaño? ¿Debería usar un hash caro pero uno que evita colisiones, o algo áspero y rápido?
(C ++ 11 agregó tablas hash con unordered_map . Puede ver en la documentation que requiere establecer políticas para configurar muchas de estas opciones).
Dado que el STL no puede anticipar cuál es la mejor opción para su aplicación, el valor predeterminado debe ser más flexible. Las estructuras de árbol "solo funcionan" y se escalan muy bien.
¿Qué hay de otros árboles?
La búsqueda rápida del árbol rojo negro y el auto equilibrio a diferencia de las BST. Otro usuario señaló sus ventajas sobre el árbol AVL autoequilibrante.
Alexander Stepanov (El creador de STL) dijo que debería haber usado un árbol B * en lugar de un árbol rojo-negro si volvía a escribir std::map . Esto se debe a que los nodos pueden almacenar un número arbitrario de elementos contiguos, que es más compatible con la caché para las computadoras modernas.
Uno de los mayores cambios desde entonces ha sido el crecimiento de los cachés. Las fallas de caché son muy costosas, por lo que la ubicación de referencia es mucho más importante ahora. Las estructuras de datos basadas en nodo, que tienen baja localidad de referencia, tienen mucho menos sentido. Si estuviera diseñando STL hoy, tendría un conjunto diferente de contenedores. Por ejemplo, un árbol B * en memoria es una opción mucho mejor que un árbol rojo-negro para implementar un contenedor asociativo. - Alexander Stepanov
Puedes leer más here
¿Es el árbol rojo negro o B * siempre el mejor?
En otras ocasiones, Alex ha declarado que std::vector es casi siempre el mejor contenedor de listas por razones similares. Rara vez tiene sentido usar std::list o std::deque incluso para aquellas situaciones que nos enseñaron en la escuela (como eliminar un elemento del medio de la lista). std::vector es tan rápido que supera esas estructuras para todo menos para n grande.
Aplicar el mismo razonamiento si solo tiene una pequeña cantidad de elementos (¿cientos?) Usando std::vector y búsqueda lineal puede ser más eficiente que la implementación en árbol de std::map .
Los árboles AVL tienen una altura máxima de 1.44logn, mientras que los árboles RB tienen un máximo de 2logn. Insertar un elemento en una AVL puede implicar un reequilibrio en un punto del árbol. El reequilibrio termina la inserción. Después de la inserción de una nueva hoja, la actualización de los antepasados de esa hoja debe hacerse hasta la raíz, o hasta un punto donde los dos subárboles tengan la misma profundidad. La probabilidad de tener que actualizar k nodos es de 1/3 ^ k. El reequilibrio es O (1). La eliminación de un elemento puede implicar más de un reequilibrio (hasta la mitad de la profundidad del árbol).
Los árboles RB son árboles B de orden 4 representados como árboles de búsqueda binarios. Un nodo 4 en el árbol B da como resultado dos niveles en el BST equivalente. En el peor de los casos, todos los nodos del árbol son 2 nodos, con solo una cadena de 3 nodos hasta una hoja. Esa hoja estará a una distancia de 2logn desde la raíz.
Al bajar desde la raíz hasta el punto de inserción, uno tiene que cambiar 4 nodos en 2 nodos, para asegurarse de que ninguna inserción sature una hoja. Volviendo de la inserción, todos estos nodos deben analizarse para asegurarse de que representan correctamente 4 nodos. Esto también se puede hacer bajando en el árbol. El costo global será el mismo. ¡No hay almuerzo gratis! Eliminar un elemento del árbol es del mismo orden.
Todos estos árboles requieren que los nodos lleven información sobre altura, peso, color, etc. Solo los árboles Splay están libres de dicha información adicional. ¡Pero la mayoría de la gente le teme a los árboles de Splay, debido a la complejidad de su estructura!
Finalmente, los árboles también pueden transportar información de peso en los nodos, lo que permite el equilibrio de peso. Se pueden aplicar varios esquemas. Uno debería reequilibrarse cuando un subárbol contiene más de 3 veces el número de elementos del otro subárbol. El reequilibrio se realiza nuevamente a través de una rotación simple o doble. Esto significa el peor caso de 2.4logn. Uno puede salirse con 2 veces en lugar de 3, una proporción mucho mejor, pero puede significar dejar un poco menos que el 1% de los subárboles desequilibrados aquí y allá. ¡Difícil!
¿Qué tipo de árbol es el mejor? AVL seguro. Son los más simples de codificar, y tienen su peor altura más próxima al logn. Para un árbol de 1000000 elementos, un AVL tendrá una altura máxima de 29, un RB 40 y un peso equilibrado de 36 o 50 según la proporción.
Hay muchas otras variables: aleatoriedad, proporción de adiciones, eliminaciones, búsquedas, etc.
Probablemente los dos algoritmos de árbol de autoequilibrio más comunes son árboles Rojo-Negros y árboles AVL . Para equilibrar el árbol después de una inserción / actualización, ambos algoritmos usan la noción de rotaciones donde los nodos del árbol se rotan para realizar el reequilibrio.
Mientras que en ambos algoritmos, las operaciones de inserción / supresión son O (log n), en el caso del árbol rojo-negro la rotación de reequilibrio es una operación O(1) mientras que con AVL es una operación O(1) , haciendo El árbol rojo-negro es más eficiente en este aspecto de la etapa de reequilibrio y una de las posibles razones por las que se usa con mayor frecuencia.
Los árboles rojo-negro se usan en la mayoría de las bibliotecas de colecciones, incluidas las ofertas de Java y Microsoft .NET Framework.
Realmente depende del uso. El árbol AVL generalmente tiene más rotaciones de reequilibrio. Entonces, si su aplicación no tiene demasiadas operaciones de inserción y eliminación, pero pesa mucho en la búsqueda, entonces el árbol AVL probablemente sea una buena opción.
std::map utiliza un árbol Rojo-Negro ya que ofrece una compensación razonable entre la velocidad de inserción / eliminación de nodos y la búsqueda.