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

193

¿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?

Denis Gorodetskiy
fuente
26
Aunque todas las implementaciones que he visto usan un árbol RB, tenga en cuenta que esto todavía depende de la implementación.
Thomas
3
@Thomas. Es dependiente de la implementación, entonces ¿por qué es así que toda la implementación usa árboles RB?
Denis Gorodetskiy
1
Realmente me gustaría saber si algún implementador de STL ha pensado en usar una Lista de salto.
Matthieu M.
2
El mapa y el conjunto de C ++ son en realidad un mapa ordenado y un conjunto ordenado. No se implementan utilizando funciones hash. Cada consulta tomaría O(logn)y no O(1), pero los valores siempre se ordenarán. A partir de C ++ 11 (creo), hay unordered_mapy unordered_set, que se implementan utilizando funciones hash y, aunque no están ordenados, la mayoría de las consultas y operaciones son posibles O(1)( en promedio)
SomethingSomething
@Thomas es cierto, pero no tan interesante en la práctica. El estándar ofrece garantías de complejidad con un algoritmo específico o un conjunto de algoritmos en mente.
Justin Meiners

Respuestas:

125

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.

Chris Taylor
fuente
54
haces que parezca que los árboles rojo-negros pueden hacer modificaciones de árbol en el tiempo O (1), lo cual no es cierto. las modificaciones del árbol son O (log n) para los árboles rojo-negro y AVL. eso hace que sea discutible si la parte de equilibrio de la modificación del árbol es O (1) u O (log n) porque la operación principal ya es O (log n). incluso después de todo el trabajo un poco más que hacen los árboles AVL resulta en un árbol más equilibrado que conduce a búsquedas un poco más rápidas. Por lo tanto, es una compensación perfectamente válida y no hace que los árboles AVL sean inferiores a los árboles rojo-negros.
nigromante
35
Debe ver más allá de la complejidad al tiempo de ejecución real para ver la diferencia: los árboles AVL generalmente tienen un tiempo de ejecución total más bajo cuando hay muchas más búsquedas que inserciones / eliminaciones. Los árboles RB tienen un tiempo de ejecución total más bajo cuando hay muchas más inserciones / eliminaciones. La proporción exacta en la que se produce la interrupción depende, por supuesto, de muchos detalles de implementación, hardware y uso exacto, pero dado que los autores de la biblioteca deben admitir una amplia gama de patrones de uso, tienen que tomar una conjetura educada. AVL también es un poco más difícil de implementar, por lo que es posible que desee un beneficio comprobado para usarlo.
Steve Jessop
66
El árbol RB no es una "implementación predeterminada". Cada implementador elige una implementación. Hasta donde sabemos, todos han elegido árboles RB, por lo que presumiblemente esto es por rendimiento o por facilidad de implementación / mantenimiento. Como dije, el punto de ruptura para el rendimiento podría no implicar que piensan que hay más inserciones / eliminaciones que búsquedas, solo que la relación entre los dos está por encima del nivel en el que creen que RB probablemente supera a AVL.
Steve Jessop
9
@Denis: desafortunadamente, la única forma de obtener números es hacer una lista de std::mapimplementaciones, localizar a los desarrolladores y preguntarles qué criterios utilizaron para tomar la decisión, por lo que esto sigue siendo una especulación.
Steve Jessop
44
Falta todo esto es el costo, por nodo, de almacenar la información auxiliar requerida para tomar decisiones de equilibrio. Los árboles rojo-negros requieren 1 bit para representar el color. Los árboles AVL requieren al menos 2 bits (para representar -1, 0 o 1).
SJHowe
46

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.

webbertiger
fuente
1
¿¿¿Estás seguro de eso??? Personalmente, creo que el árbol Rojo-Negro es uno o más complejo, nunca más simple. Lo único, es en el árbol Rd-Black, el reequilibrio ocurre con menos frecuencia que AVL.
Eric Ouellet
1
@Eric Teóricamente, tanto el árbol R / B como el árbol AVL tienen complejidad O (log n)) para inserción y eliminación. Pero una gran parte del costo de operación es la rotación, que es diferente entre estos dos árboles. Consulte discus.fogcreek.com/joelonsoftware/… Cita: "equilibrar un árbol AVL puede requerir rotaciones O (log n), mientras que un árbol negro rojo tomará como máximo dos rotaciones para equilibrarlo (aunque puede tener que examinar los nodos O (log n) para decidir dónde son necesarias las rotaciones) ". Edité mis comentarios en consecuencia.
webbertiger
26

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.

usuario847376
fuente
2
Buena respuesta. Pero si las AVL son las mejores, ¿por qué la biblioteca estándar implementa std :: map como árbol RB?
Denis Gorodetskiy
13
No estoy de acuerdo con que los árboles AVL sean, sin duda, los mejores. Aunque tienen una altura baja, requieren (en total) más trabajo para realizar el reequilibrio que los árboles rojos / negros (O (log n) trabajo de reequilibrio versus O (1) trabajo de reequilibrio amortizado). Los árboles de separación podrían ser mucho, mucho mejores y su afirmación de que la gente les tiene miedo es infundada. No existe un único "mejor" esquema de equilibrio de árboles universal.
templatetypedef
Respuesta casi perfecta. ¿Por qué dijiste que AVL es el mejor? Eso es simplemente incorrecto y es por eso que la implementación más general utiliza el árbol Rojo-Negro. Debe tener una proporción bastante mayor de lectura sobre manipulación para elegir AVL. Además, AVL tiene un poco menos huella de memoria que RB.
Eric Ouellet
Estoy de acuerdo en que AVL tiende a ser mejor en la mayoría de los casos, porque generalmente los árboles se buscan con más frecuencia de lo que se insertan. ¿Por qué se considera que el árbol RB es mejor cuando es el que tiene una ligera ventaja en el caso de escritura en su mayoría y, lo que es más importante, una ligera desventaja en el caso de lectura en su mayoría? ¿Realmente se cree que insertarás más de lo que encontrarás?
doug65536
25

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.

Justin Meiners
fuente
3

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.

Eric Ouellet
fuente
2

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.

nigromante
fuente