¿Por qué los árboles rojo-negros son tan populares?

Parece que donde quiera que mire, las estructuras de datos se están implementando utilizando árboles rojo-negros ( std::seten C ++, SortedDictionaryen C #, etc.)

Después de haber cubierto los árboles (a, b), rojo-negro y AVL en mi clase de algoritmos, esto es lo que obtuve (también de preguntar a los profesores, mirar algunos libros y buscar un poco en Google):

• Los árboles AVL tienen una profundidad promedio menor que los árboles rojo-negros, y por lo tanto, buscar un valor en el árbol AVL es consistentemente más rápido.
• Los árboles rojo-negros hacen menos cambios estructurales para equilibrarse que los árboles AVL, lo que podría hacerlos potencialmente más rápidos para insertar / eliminar. Estoy diciendo potencialmente, porque esto dependería del costo del cambio estructural en el árbol, ya que esto dependerá mucho del tiempo de ejecución y la implementación (¿también podría ser completamente diferente en un lenguaje funcional cuando el árbol es inmutable?)

Hay muchos puntos de referencia en línea que comparan AVL y árboles rojo-negros, pero lo que me llamó la atención es que mi profesor básicamente dijo que, por lo general, harías una de dos cosas:

• O realmente no te importa mucho el rendimiento, en cuyo caso la diferencia del 10-20% de AVL vs Rojo-negro en la mayoría de los casos no importará en absoluto.
• O realmente le importa el rendimiento, en el caso de que abandone los árboles AVL y Rojo-negro, y vaya con los árboles B, que se pueden ajustar para que funcionen mucho mejor (o (a, b) -árboles, I ' Voy a poner todo eso en una canasta.)

La razón de esto es porque un árbol B almacena datos de forma más compacta en la memoria (un nodo contiene muchos valores), habrá muchos menos errores de caché. También puede ajustar la implementación en función del caso de uso y hacer que el orden del árbol B dependa del tamaño de la memoria caché de la CPU, etc.

El problema es que no puedo encontrar casi ninguna fuente que analice el uso en la vida real de diferentes implementaciones de árboles de búsqueda en hardware real moderno. He revisado muchos libros sobre algoritmos y no he encontrado nada que compare diferentes variantes de árboles, aparte de mostrar que uno tiene una profundidad promedio menor que el otro (lo que realmente no dice mucho sobre cómo se comportará el árbol). en programas reales.)

Dicho esto, ¿hay alguna razón particular por la que los árboles rojo-negros se estén utilizando en todas partes, cuando se basa en lo que se dijo anteriormente, los árboles B deberían superarlos? (como el único punto de referencia que pude encontrar también muestra http://lh3lh3.users.sourceforge.net/udb.shtml , pero podría ser solo una cuestión de implementación específica). ¿O es la razón por la que todos usan árboles rojo-negros porque son bastante fáciles de implementar o, en otras palabras, difíciles de implementar mal?

Además, ¿cómo cambia esto cuando uno se mueve al ámbito de los lenguajes funcionales? Parece que tanto Clojure como Scala usan intentos mapeados de matriz Hash , donde Clojure usa un factor de ramificación de 32.

Para citar de la respuesta a la pregunta " Recorridos desde la raíz en árboles AVL y árboles rojos negros "

Para algunos tipos de árboles de búsqueda binarios, incluidos los árboles rojo-negros pero no los árboles AVL, las "correcciones" al árbol pueden predecirse con bastante facilidad en el camino hacia abajo y realizarse durante un solo pase de arriba hacia abajo, haciendo innecesario el segundo pase. Tales algoritmos de inserción generalmente se implementan con un bucle en lugar de recurrencia, y a menudo se ejecutan un poco más rápido en la práctica que sus contrapartes de dos pasos.

Por lo tanto, una inserción de árbol RedBlack se puede implementar sin recursividad, en algunas CPU la recursividad es muy costosa si se sobrepasa el caché de llamadas de función (por ejemplo, SPARC debido al uso de la ventana de Registro )

(He visto que el software se ejecuta más de 10 veces más rápido en Sparc al eliminar una llamada de función, lo que resultó en una ruta de código a menudo demasiado profunda para la ventana de registro. Como no sabe qué tan profunda será la ventana de registro) el sistema de su cliente, y usted no sabe qué tan lejos de la pila de llamadas se encuentra en la "ruta de código activo", no usar la recursividad hace que sea más predecible)

Además, no correr el riesgo de quedarse sin pila es un beneficio.

También he estado investigando este tema recientemente, así que aquí están mis hallazgos, ¡pero tenga en cuenta que no soy un experto en estructuras de datos!

Hay algunos casos en los que no puedes usar árboles B en absoluto.

Un caso destacado es std::mapde C ++ STL. El estándar requiere que insertno invalide los iteradores existentes

No se invalidan iteradores ni referencias.

http://en.cppreference.com/w/cpp/container/map/insert

Esto descarta el árbol B como una implementación porque la inserción se movería alrededor de los elementos existentes.

Otro caso de uso similar son las estructuras de datos intrusivas. Es decir, en lugar de almacenar sus datos dentro del nodo del árbol, almacena punteros a hijos / padres dentro de su estructura:

// non intrusive
struct Node<T> {
    T value;
    Node<T> *left;
    Node<T> *right;
};
using WalrusList = Node<Walrus>;

// intrusive
struct Walrus {
    // Tree part
    Walrus *left;
    Walrus *right;

    // Object part
    int age;
    Food[4] stomach;
};

Simplemente no puede hacer que un árbol B sea intrusivo, porque no es una estructura de datos de solo puntero.

Se usan árboles intrusivos rojo-negros, por ejemplo, en jemalloc para administrar bloques de memoria libres. Esta es también una estructura de datos popular en el kernel de Linux.

También creo que la implementación "recursiva de cola de paso único" no es la razón de la popularidad del árbol negro rojo como una estructura de datos mutable .

En primer lugar, la profundidad de la pila es irrelevante aquí, porque (dada la altura de ) se quedaría sin memoria principal antes de quedarse sin espacio de pila. Jemalloc está contento de preasignar la peor profundidad de caso en la pila.$\log{n}$

Hay una serie de sabores de implementación de árbol rojo-negro. Robert Sedgewick deja unos árboles rojos rojos inclinados famosos ( ¡PRECAUCIÓN! Hay otras variantes que también se denominan "inclinación izquierda", pero utilizan un algoritmo diferente). De hecho, esta variante permite realizar rotaciones en el camino hacia abajo del árbol, pero carece de la propiedad importante de número amortiguado de arreglos, y esto lo hace más lento ( según lo medido por el autor de jemalloc ). O, como dice opendatastrutures$O(1)$

La variante de Andersson de los árboles rojo-negro, la variante de Sedgewick de los árboles rojo-negro y los árboles AVL son todos más simples de implementar que la estructura RedBlackTree definida aquí. Desafortunadamente, ninguno de ellos puede garantizar que el tiempo amortizado dedicado al reequilibrio sea por actualización.$O(1)$

La variante descrita en opendatastructures utiliza punteros principales, un paso descendente recursivo para la inserción y un paso iterativo hacia arriba para las reparaciones. Las llamadas recursivas están en una posición de cola y los compiladores optimizan esto en un bucle (lo he comprobado en Rust).

Es decir, puede obtener una implementación de bucle de memoria constante de un árbol de búsqueda mutable sin ninguna magia rojo-negra si utiliza punteros principales. Esto también funciona para los árboles B. Necesita magia para la variante inmutable recursiva de la cola de un solo paso, y de todos modos se romperá la reparación .$O(1)$

Bueno, esta no es una respuesta autorizada, pero cada vez que tengo que codificar un árbol de búsqueda binario equilibrado, es un árbol rojo-negro. Hay algunas razones para esto:

1) El costo promedio de inserción es constante para los árboles rojo-negros (si no tiene que buscar), mientras que es logarítmico para los árboles AVL. Además, implica como máximo una reestructuración complicada. Sigue siendo O (log N) en el peor de los casos, pero eso es simplemente una nueva coloración.

2) Requieren solo 1 bit de información adicional por nodo, y a menudo puede encontrar una forma de obtenerla de forma gratuita.

3) No tengo que hacer esto muy a menudo, así que cada vez que lo hago tengo que descubrir cómo hacerlo de nuevo. Las reglas simples y la correspondencia con 2-4 árboles hacen que parezca fácil cada vez , a pesar de que el código resulta complicado cada vez . Todavía espero que algún día el código resulte simple.

4) La forma en que el árbol rojo-negro divide el nodo del árbol 2-4 correspondiente e inserta la clave del medio en el nodo 2-4 padre simplemente volviendo a colorear es súper elegante. Me encanta hacerlo

Los árboles rojo-negro o AVL tienen una ventaja sobre los árboles B y similares cuando la clave es larga o por alguna otra razón mover una clave es costosa.

Creé mi propia alternativa std::setdentro de un proyecto importante, por varias razones de rendimiento. Elegí AVL sobre rojo-negro por razones de rendimiento (pero esa pequeña mejora de rendimiento no fue la justificación para rodar la mía en lugar de std :: set). La "clave" que era complicada y difícil de mover fue un factor significativo. ¿Los árboles (a, b) todavía tienen sentido si necesita otro nivel de indirección frente a las teclas? AVL y los árboles rojo-negros se pueden reestructurar sin mover las teclas, por lo que tienen esa ventaja cuando las teclas son caras de mover.