¿Por qué se implementa std :: map como un árbol rojo-negro?

¿Por qué se std::mapimplementa como un árbol rojo-negro ?

Hay varios árboles de búsqueda binarios equilibrados (BST) por ahí. ¿Cuáles fueron las compensaciones de diseño al elegir un árbol rojo-negro?

Probablemente los dos algoritmos de árbol de equilibrio automático más comunes son los árboles Rojo-Negros y los á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 giran para realizar el reequilibrio.

Mientras que en ambos algoritmos las operaciones de inserción / eliminació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 esta es una operación O (log n) , lo que hace que 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 más comúnmente.

Los árboles rojo-negros 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 usa el árbol Rojo-Negro, ya que obtiene una compensación razonable entre la velocidad de inserción / eliminación de nodos y la búsqueda.

Los árboles AVL tienen una altura máxima de 1,44 logn, mientras que los árboles RB tienen un máximo de 2logn. Insertar un elemento en un AVL puede implicar un reequilibrio en un punto del árbol. El reequilibrio termina la inserción. Después de insertar una nueva hoja, la actualización de los antepasados ​​de esa hoja debe realizarse 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 1/3 ^ k. El reequilibrio es O (1). Eliminar 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 4-nodo 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 de la raíz.

Bajando desde la raíz hasta el punto de inserción, uno tiene que cambiar 4 nodos a 2 nodos, para asegurarse de que cualquier inserción no 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 tiene miedo a los árboles Splay, debido a lo ramificado 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 debe reequilibrar cuando un subárbol contiene más de 3 veces el número de elementos del otro subárbol. El reequilibrio se realiza nuevamente mediante una rotación simple o doble. Esto significa un 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 de 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 cercana a 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 dependiendo de la relación.

Hay muchas otras variables: aleatoriedad, proporción de adiciones, eliminaciones, búsquedas, etc.

Las respuestas anteriores solo abordan alternativas de árbol y el rojo negro probablemente solo permanezca por razones históricas.

¿Por qué no una tabla hash?

Un tipo solo requiere que el <operador (comparación) se use como clave en un árbol. Sin embargo, las tablas hash requieren que cada tipo de clave tenga una hashfunción definida. Mantener los requisitos de tipo al mínimo es muy importante para la programación genérica, por lo que puede usarlo con una amplia variedad de tipos y algoritmos.

Diseñar una buena tabla hash requiere un conocimiento profundo del contexto en el que se utilizará. ¿Debería usar direccionamiento abierto o encadenamiento vinculado? ¿Qué niveles de carga debe aceptar antes de cambiar el tamaño? ¿Debería usar un hash costoso que evite colisiones, o uno que sea áspero y rápido?

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. Los árboles "simplemente funcionan" y escalan muy bien.

(C ++ 11 sí agregó tablas hash unordered_map. Puede ver en la documentación que requiere establecer políticas para configurar muchas de estas opciones).

¿Qué hay de otros árboles?

Los árboles Red Black ofrecen una búsqueda rápida y se equilibran automáticamente, a diferencia de los BST. Otro usuario señaló sus ventajas sobre el árbol AVL de equilibrio automático.

Alexander Stepanov (El creador de STL) dijo que usaría un árbol B * en lugar de un árbol Rojo-Negro si std::mapvolviera a escribir , porque es más amigable para las memorias caché modernas.

Uno de los mayores cambios desde entonces ha sido el crecimiento de cachés. Los errores de caché son muy costosos, por lo que la localidad de referencia es mucho más importante ahora. Las estructuras de datos basadas en nodos, que tienen una 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

¿Deben los mapas usar siempre árboles?

Otra posible implementación de mapas sería un vector ordenado (clasificación por inserción) y búsqueda binaria. Esto funcionaría bien para contenedores que no se modifican con frecuencia pero se consultan con frecuencia. A menudo hago esto en C como qsorty estoy bsearchintegrado.

¿Necesito incluso usar el mapa?

Consideraciones de caché significa que rara vez tiene sentido usar std::listo std::dequemás std:vector, incluso para aquellas situaciones que nos enseñaron en la escuela (tales como la eliminación de un elemento de la mitad de la lista). Aplicando el mismo razonamiento, usar un bucle for para la búsqueda lineal en una lista es a menudo más eficiente y más limpio que construir un mapa para algunas búsquedas.

Por supuesto, elegir un contenedor legible suele ser más importante que el rendimiento.

Actualización 2017-06-14: webbertiger edita su respuesta después de comentar. Debo señalar que su respuesta ahora es mucho mejor para mis ojos. 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 incorrecta. Siento que tuve 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 el índice de consulta (lectura) es mayor que la manipulación (modificación). La huella de la memoria es un poco menor que RB (debido al bit requerido para colorear).
• RB: Mejor en casos generales donde hay un equilibrio entre consulta (lectura) y manipulación (modificación) o más modificación sobre consulta. Una huella de memoria ligeramente mayor debido al almacenamiento de la bandera roja-negra.

La principal diferencia proviene de la coloración. 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 relativamente alto. Debido a la coloración, el árbol RB también tiene un mayor nivel de nodos porque podría aceptar nodos rojos entre los negros (con la posibilidad de ~ 2x más niveles) haciendo que la búsqueda (lectura) sea un poco menos eficiente ... pero porque es un constante (2x), permanece en O (log n).

Si considera el impacto de rendimiento para una modificación de un árbol (significativo) VS el impacto de rendimiento de la consulta de un árbol (casi insignificante), se vuelve natural preferir RB sobre AVL para un caso general.

Es solo la elección de su implementación: podrían implementarse como cualquier árbol equilibrado. Las diversas opciones son comparables con pequeñas diferencias. Por lo tanto, cualquiera es tan bueno como cualquiera.