data structures - multicamino - Diferencia entre árboles rojo-negro y árboles AVL
ejercicios arboles rojo negro (9)
¿Puede alguien explicar por favor 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 uno sería preferido sobre el otro? ¿Qué situaciones prácticas hacen que uno sea "mejor" para usar que el otro?
Los árboles AVL a menudo se comparan con árboles rojo-negro porque ambos admiten el mismo conjunto de operaciones y toman el tiempo
O(log n)para las operaciones básicas. Para las 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 tienen equilibrio de peso ni μ balanceado para ningún μ ≤ ½; es decir, los nodos hermanos pueden tener un gran número de descendientes.
Del artículo de Wikipedia sobre árboles AVL
Citando de esto: Diferencia entre AVL y árboles rojo-negro
Los árboles RB son, además de los árboles AVL, autoequilibrados. Ambos proporcionan búsqueda O (log n) y rendimiento de inserción. La diferencia es que RB-Trees garantiza O (1) rotaciones por operación de inserción. Eso es lo que realmente cuesta el rendimiento en implementaciones reales. Simplificados, RB-Trees obtienen esta ventaja de ser 2-3 árboles conceptualmente sin llevar la sobrecarga de las estructuras dinámicas de los nodos. Físicamente, los árboles RB se implementan como árboles binarios, los indicadores rojos / negros simulan un comportamiento de 2-3.
por definición, cada AVL es subconjuntos de Rojo-Negro. Uno debería ser capaz de colorear cualquier árbol AVL, sin reestructuración o rotación, para transformarlo en un árbol Rojo-Negro.
El hecho de que los árboles RedBlack tengan menos rotaciones puede hacerlos más rápidos en las inserciones / eliminaciones, sin embargo .... Como suelen ser un poco más profundos, también pueden ser más lentos en las inserciones y eliminaciones. Cada vez que se pasa de un nivel en el árbol al siguiente, hay un gran cambio de que la información solicitada no está en el caché y debe recuperarse de la memoria RAM. Por lo tanto, el tiempo ganado con menos rotaciones ya puede perderse, ya que tiene que navegar más profundo y, por lo tanto, tiene que actualizar su caché con más frecuencia. Ser capaz de operar desde el caché o no hace una gran diferencia. Si la información relevante está en la memoria caché, puede realizar varias operaciones de rotación, en el tiempo necesario para navegar un nivel adicional y la información del siguiente nivel no está en la memoria 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, debido a errores de caché.
En resumen: AvlTrees está ligeramente mejor equilibrado que RedBlackTrees. Ambos árboles toman el tiempo O (log n) global para búsquedas, inserciones y eliminaciones, pero para la inserción y eliminación, el primero requiere rotaciones O (log n), mientras que el último toma solo O (1) rotaciones.
Dado que las rotaciones significan escribir en la memoria, y escribir en la memoria es costoso, los RedBlackTrees en la práctica son más rápidos de actualizar que los AvlTrees
Los árboles AVL mantienen un equilibrio más rígido que los árboles rojo-negro. El camino desde la raíz hasta la hoja más profunda en un árbol AVL es como mucho ~ 1.44 lg (n + 2), mientras que en los árboles rojos y negros es como mucho ~ 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 lenta 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 la cantidad de actualizaciones en el árbol.
Para tener una idea de cómo funciona un Árbol AVL, this visualización interactiva ayuda.
Tanto AVL como RedBlack Trees son estructuras de datos de árbol 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 adición / eliminación, mayor en el caso de AVL, para preservar un equilibrio global más homogéneo.
Ambas implementaciones se escalan como 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 intensiva: aprovechando el mejor equilibrio, los recorridos de árbol son más cortos en promedio. Por otro lado, en cuanto a inserción y eliminación, un árbol AVL es más lento: se necesita un número mayor de rotaciones para reequilibrar adecuadamente 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, donde la Estructura de datos se modifica con tanta frecuencia como se busca . Un ejemplo, TreeMap y TreeSet en Java hacen uso de un árbol RedBlack de respaldo.
Por lo que he visto, parece que los Árboles AVL hacen tantas rotaciones (recursivamente en el árbol algunas veces) como sea necesario para obtener la altura deseada del Árbol AVL (Log n). Esto lo hace más rígidamente equilibrado.
Para Red Black Trees hay 5 conjuntos de reglas que necesita para asegurarse de que permanezca insertado y eliminado, 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 recursivamente 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 los problemas que tenga, pero después de esas rotaciones uno o dos, ESTÁ HECHO. Empacalo y di buenas noches porque ese es el final de la manipulación que necesitas hacer.
La regla Grande es el número 5 ... ''Cada ruta simple desde un nodo dado a cualquiera de sus hojas descendientes contiene el mismo número de nodos negros''.
Esto causará la mayoría de las rotaciones que necesitará para que el árbol funcione y que el árbol no se salga demasiado de balance.
Para datos pequeños :
insert : el árbol RB y el árbol avl tienen 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.
delete : el árbol RB tiene un número constante de rotación máxima, pero el árbol AVL puede tener O (log N) los tiempos de rotación como los 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 particular antes de la inserción. a medida que tenga más datos, la diferencia de tiempo al buscar el nodo particular crece 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. (lo mismo que en 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 extracció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.
La altura máxima de los árboles es lo más importante para mantener el equilibrio. Casi equivale a 1.44 * log(n) para AVL, pero para el árbol RB, es 2 * log(n) . Entonces, podemos llegar a la conclusión de que es mejor usar AVL cuando el problema es el incentivo de búsqueda. Lo que importa es otra pregunta para el árbol AVL y RB. El árbol RB es mejor que AVL cuando se enfrenta a la inserción aleatoria al menor costo de rotación, pero el AVL es bueno para insertar los datos ascendentes o descendentes. Entonces, si el problema es el incentivo de inserción, podemos usar el árbol RB.