Diferencia entre árboles rojo-negro y árboles AVL

¿Alguien puede explicar cuáles son las principales diferencias entre estas dos estructuras de datos? He estado tratando de encontrar una fuente en línea que destaque las diferencias / similitudes, pero no he encontrado nada demasiado informativo. ¿En qué casos se preferiría uno sobre el otro? ¿Qué situaciones prácticas hacen que uno sea "mejor" de usar que el otro?

Los árboles AVL mantienen un equilibrio más rígido que los árboles rojo-negros. El camino desde la raíz hasta la hoja más profunda en un árbol AVL es como máximo ~ 1,44 lg (n + 2), mientras que en los árboles negros rojos es como máximo ~ 2 lg (n + 1).

Como resultado, la búsqueda en un árbol AVL suele ser más rápida, pero esto tiene el costo de una inserción y eliminación más lentas debido a más operaciones de rotación. Por lo tanto, use un árbol AVL si espera que el número de búsquedas domine el número de actualizaciones del árbol.

Para datos pequeños :

insert : RB tree & avl tree tiene un número constante de rotación máxima, pero el árbol RB será más rápido porque, en promedio, el árbol RB usa menos rotación.

búsqueda : el árbol AVL es más rápido, porque el árbol AVL tiene menos profundidad.

eliminar : el árbol RB tiene un número constante de rotación máxima, pero el árbol AVL puede tener tiempos de rotación O (log N) como peores. y en promedio, el árbol RB también tiene menos número de rotación, por lo que el árbol RB es más rápido.

para datos grandes :

insertar : el árbol AVL es más rápido. porque necesita buscar un nodo en particular antes de la inserción. a medida que tenga más datos, la diferencia de tiempo al buscar el nodo en particular aumentará proporcionalmente a O (log N). pero el árbol AVL y el árbol RB solo necesitan un número constante de rotación en el peor de los casos. Por lo tanto, el cuello de la botella se convertirá en el momento en que busque ese nodo en particular.

búsqueda : el árbol AVL es más rápido. (igual que en el caso de datos pequeños)

eliminar : el árbol AVL es más rápido en promedio, pero en el peor de los casos el árbol RB es más rápido. porque también necesita buscar un nodo muy profundo para intercambiar antes de la eliminación (similar al motivo de la inserción). en promedio, ambos árboles tienen un número constante de rotación. pero el árbol RB tiene un límite superior constante para la rotación.

Citando de esto: Diferencia entre AVL y árboles rojo-negro

Los árboles RB son, al igual que los árboles AVL, autoequilibrantes. Ambos proporcionan rendimiento de inserción y búsqueda O (log n). La diferencia es que RB-Trees garantizan O (1) rotaciones por operación de inserción. Eso es lo que realmente cuesta rendimiento en implementaciones reales. Simplificado, los RB-Trees obtienen esta ventaja al ser conceptualmente 2-3 árboles sin llevar la sobrecarga de las estructuras dinámicas de los nodos. Físicamente, los árboles RB se implementan como árboles binarios, las banderas rojas / negras simulan un comportamiento 2-3.

por definición, cada AVL es, por tanto, subconjuntos de Rojo-Negro. Uno debería poder colorear cualquier árbol AVL, sin reestructuración ni rotación, para transformarlo en un árbol rojo-negro.

Los árboles AVL a menudo se comparan con árboles rojo-negro porque ambos admiten el mismo conjunto de operaciones y toman O(log n)tiempo para las operaciones básicas. Para aplicaciones de búsqueda intensiva, los árboles AVL son más rápidos que los árboles rojo-negro porque están más rígidamente equilibrados. Al igual que los árboles rojo-negro, los árboles AVL tienen un equilibrio de altura. En general, ambos no están equilibrados en peso ni en μ equilibrados para cualquier μ ≤ ½; es decir, los nodos hermanos pueden tener un número enormemente diferente de descendientes.

Del artículo de Wikipedia sobre árboles AVL

La altura máxima de los árboles es de suma importancia para mantener el equilibrio. Casi es igual 1.44 * log(n)para AVL, pero para RB tree, lo es 2 * log(n). Por tanto, podemos llegar a la conclusión de que es mejor utilizar AVL cuando el problema es el incentivo de búsqueda. Lo que importa es otra pregunta para AVL y RB tree. El árbol RB es mejor que AVL cuando se enfrenta a la inserción aleatoria al menor costo de la rotación pero el AVL que es bueno para insertar los datos ascendentes o descendentes. Entonces, si el problema es el incentivo de inserción, podemos usar el árbol RB.

Para tener una idea de cómo funciona un árbol AVL, esta visualización interactiva ayuda.

Tanto AVL como RedBlack Trees son estructuras de datos de árboles de altura equilibrada. Son bastante similares, y la diferencia real consiste en el número de operaciones de rotación realizadas en cualquier operación de agregar / quitar, mayor en el caso de AVL, para preservar un equilibrio general más homogéneo.

Ambas implementaciones escalan como a O(lg N), donde N es el número de hojas, pero en la práctica, un árbol AVL es más rápido en tareas de búsqueda intensivas: aprovechando el mejor equilibrio, los recorridos del árbol son más cortos en promedio. Por otro lado, en cuanto a la inserción y eliminación, un árbol AVL es más lento: se necesita un mayor número de rotaciones para reequilibrar correctamente la estructura de datos tras la modificación.

Para implementaciones de propósito general (es decir, a priori, no está claro si las búsquedas son las operaciones predominantes), se prefieren los árboles RedBlack: son más fáciles de implementar y más rápidos en los casos comunes, siempre que la estructura de datos se modifique con la frecuencia de búsqueda. . Un ejemplo, TreeMapy TreeSeten Java hacer uso de un RedBlack Tree de respaldo.

Sin embargo, el hecho de que los árboles RedBlack tengan menos rotaciones puede hacerlos más rápidos en inserciones / eliminaciones ... Como suelen ser un poco más profundos, también pueden ser más lentos en inserciones y eliminaciones. Cada vez que pasa de un nivel en el árbol al siguiente, hay un gran cambio en el sentido de que la información solicitada no está en la caché y debe recuperarse de la RAM. Por lo tanto, el tiempo ganado con menos rotaciones ya se puede perder, ya que tiene que navegar más profundo y, por lo tanto, debe actualizar su caché con más frecuencia. Poder operar desde caché o no hace una gran diferencia. Si la información relevante está en la caché, entonces puede realizar múltiples operaciones de rotación, en el tiempo necesario para navegar por un nivel adicional y la información del siguiente nivel no está en la caché. Por lo tanto, en los casos en que RedBlack es en teoría más rápido, mirando solo las operaciones necesarias, podría ser más lento en la práctica,

Por lo que he visto, parece que los árboles AVL hacen tantas rotaciones (a veces recursivamente hacia arriba del árbol) como sea necesario para obtener la altura deseada del árbol AVL (Log n). Esto lo hace más rígidamente equilibrado.

Para los árboles rojos y negros, hay 5 conjuntos de reglas que debe asegurarse de permanecer durante la inserción y la eliminación que puede encontrar aquí http://en.wikipedia.org/wiki/Red-black_tree .

Lo principal que podría ayudarte con los árboles rojos y negros es el hecho de que, dependiendo de esas cinco reglas, puedes colorear el árbol de forma recursiva hasta la raíz si el tío es rojo. Si el tío es negro, tendrá que hacer un máximo de dos rotaciones para solucionar cualquier problema que tenga, pero después de esas una o dos rotaciones, YA HAS TERMINADO. Empaquételo y diga buenas noches porque ese es el final de la manipulación que necesita hacer.

La regla grande es la número 5 ... 'Cada camino simple desde un nodo dado a cualquiera de sus hojas descendientes contiene el mismo número de nodos negros'.

Esto provocará la mayoría de las rotaciones que necesitará para que el árbol funcione y eso hará que el árbol no se desequilibre demasiado.

En resumen: AvlTrees está ligeramente mejor equilibrado que RedBlackTrees. Ambos árboles toman O (log n) tiempo en general para búsquedas, inserciones y eliminaciones, pero para la inserción y eliminación, el primero requiere O (log n) rotaciones, mientras que el segundo solo toma O (1) rotaciones.

Dado que las rotaciones significan escribir en la memoria y escribir en la memoria es costoso, RedBlackTrees es en la práctica más rápido de actualizar que AvlTrees