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

Realmente depende del uso. AVL tree usualmente 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 AVL tree probablemente sea una buena opción.

std::map utiliza 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 finaliza la inserción. Después de la inserción de una nueva hoja, la actualización de los antepasados de esa hoja tiene que hacerse hasta la raíz, o hasta un punto donde los dos subárboles son de igual profundidad. La probabilidad de tener que actualizar nodos k es 1/3^k. Reequilibrio es O(1). Eliminar un elemento puede implicar más de un reequilibrio (hasta la mitad de la profundidad del árbol).

RB-trees 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 en 2 nodos, para asegurarse de que cualquier inserción no saturará una hoja. Volviendo de la inserción, todos estos nodos tienen que ser analizados 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 la altura, el peso, el color, etc. Solo los árboles Splay están libres de dicha información adicional. Pero la mayoría de la gente tiene miedo de los árboles, debido a la ramdomness de su estructura!

Finalmente, los árboles también pueden llevar información de peso en los nodos, lo que permite equilibrar el 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 de nuevo a través de una rotación simple o doble. Esto significa un peor caso de 2.4 logn. Uno puede salirse con la suya 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 desequilibrado aquí y allá. ¡Tricky!

¿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 las alternativas del árbol y el rojo negro probablemente solo permanece por razones históricas.

¿Por qué no una tabla hash?

En un árbol, un tipo solo requiere un orden parcial (

Diseñar una buena tabla hash requiere conocimiento íntimo 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 caro que evite colisiones, o uno que sea áspero y rápido?

(C++11 agregó tablas hash con unordered_map. Puede ver en la documentación que se requieren políticas de configuración 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. Los árboles "solo funcionan" y escalan muy bien.

¿Qué hay de otros árboles?

Red Black tree ofrece búsqueda rápida y se autoequilibran, a diferencia de BSTs. Otro usuario señaló sus ventajas sobre el árbol de auto-equilibrio AVL.

Alexander Stepanov (El creador de STL) dijo que usaría un árbol B* en lugar de un árbol Rojo-Negro si escribía std::map de nuevo, lo que es más amigable para los cachés de memoria modernos.

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. Estructuras de datos basadas en nodos, que tienen baja localidad de referencia, tiene mucho menos sentido. Si estuviera diseñando STL hoy, tendría un conjunto diferente de contenedores. Por ejemplo, un in-memory B * - tree es una opción mucho mejor que un árbol rojo-negro para implementar un contenedor asociativo. - Alejandro Stepanov

Puedes leer más aquí

¿Es red black tree o B* siempre el mejor?

En otras ocasiones Alex ha declarado que std::vector es casi siempre el mejor contenedor de lista 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 de la mitad de la lista). std::vector es tan rápido que supera esas estructuras para todo menos n grande.

Aplicando ese mismo razonamiento si solo tienes un pequeño número de elementos (¿cientos?) el uso de una búsqueda std::vector y lineal puede ser más eficiente que la implementación en árbol de std::map. Dependiendo de la frecuencia de inserción, un std::vector ordenado combinado con std::binary_search puede ser la opción más rápida.

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

Actualización 2017-06-14: webbertiger editar su respuesta después de que comenté. Debo señalar que su respuesta es ahora mucho mejor para mis ojos. Pero mantuve mi respuesta 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 tenía 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 la memoria es un poco menor que RB (debido al bit requerido para colorear).
• RB : Mejor en los 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 rojo-negro.

La principal diferencia proviene de la coloración. Tienes menos acción de reequilibrio en RB árbol de AVL porque el color le permite a veces saltar o acortar las acciones de reequilibrio que tienen un costo relativo alto. Debido a la coloración, RB tree también tiene un nivel más alto de nodos porque podría aceptar nodos rojos entre los negros (con las posibilidades de ~2x más niveles) haciendo que la búsqueda (lectura) sea un poco menos eficiente... pero debido a que es una constante (2x), permanece en O(log n).

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