algorithm - online - arboles rojo negro ejercicios
Árbol negro rojo sobre árbol avl (6)
¿Cuál es la razón principal para elegir Árboles negros rojos en lugar de árboles AVL?
Tanto los árboles rojo-negro como los árboles AVL son los árboles de búsqueda binaria equilibrados más comúnmente utilizados y admiten la inserción, eliminación y búsqueda en tiempo O(logN) time garantizado. Sin embargo, existen los siguientes puntos de comparación entre los dos:
- Los árboles AVL están más rígidamente equilibrados y, por lo tanto, proporcionan búsquedas más rápidas. Por lo tanto, para una tarea intensiva de búsqueda use un árbol AVL.
- Para una tarea de inserción intensiva, use un árbol Rojo-Negro.
- Los árboles AVL almacenan el factor de equilibrio en cada nodo. Esto toma
O(N) extra space. Sin embargo, si sabemos que las claves que se insertarán en el árbol siempre serán mayores que cero, podemos usar el bit de signo de las teclas para almacenar la información de color de un árbol rojo-negro. Por lo tanto, en tales casos, el árbol rojo-negro tomaO(1) extra space. - En general, las rotaciones para un árbol AVL son más difíciles de implementar y depurar que las de un árbol Rojo-Negro.
¿Cuál es la aplicación del árbol negro rojo?
Los árboles rojo-negros son más generales. Lo hacen relativamente bien en agregar, eliminar y buscar, pero los árboles AVL tienen búsquedas más rápidas a costa de agregar / eliminar más lentamente. El árbol rojo-negro se usa en lo siguiente:
- Java: java.util.TreeMap, java.util.TreeSet.
- C ++ STL: mapa, multimapa, multiset.
- Kernel de Linux: planificador completamente justo, linux / rbtree.h
Los árboles AVL y Rojo negro son autoequilibrados, excepto el rojo y el negro en los nodos. ¿Cuál es la razón principal para elegir Árboles negros rojos en lugar de árboles AVL? ¿Cuáles son las aplicaciones de los árboles negros rojos?
El reequilibrio del árbol AVL debe cumplir con la propiedad siguiente. (Referencia Wiki - Árbol AVL )
En un árbol AVL, las alturas de los dos subárboles secundarios de cualquier nodo difieren en máximo uno; si en algún momento difieren en más de uno, el reequilibrio se realiza para restaurar esta propiedad.
Así que esto implica que la altura total del árbol AVL no puede enloquecer, es decir, las búsquedas mejorarán con AVL Trees. Y dado que las operaciones adicionales (rotaciones) se deben hacer para no dejar que la altura se vuelva loca, las operaciones de modificación del árbol pueden ser costosas.
Generalmente, a los programadores no les gusta asignar memoria dinámicamente. El problema con el árbol avl es que para los elementos "n" necesitas al menos log2 (log2 (n)) ... (height-> log2 (n)) bits para almacenar la altura del árbol. Por lo tanto, cuando maneja datos enormes, no puede estar seguro de cuántos bits asignar para almacenar la altura en cada nodo.
Por ejemplo, si usa 4 bytes int (32 bits) para almacenar la altura. La altura máxima puede ser: 2 ^ 32 y, por lo tanto, la cantidad máxima de elementos que puede almacenar en el árbol es 2 ^ (2 ^ 32) - (parece ser muy grande, pero en esta era de datos nada es demasiado grande, supongo). Y por lo tanto, si sobrepasas este límite, debes asignar dinámicamente más espacio para almacenar la altura.
¡Esta es una respuesta sugerida por un profesor de mi universidad que me pareció razonable! Espero que tenga sentido.
Ediciones: Los árboles AVL son más equilibrados en comparación con Red Black Trees, pero pueden causar más rotaciones durante la inserción y la eliminación. Entonces, si su aplicación involucra muchas inserciones y eliminaciones frecuentes, entonces se deberían preferir los árboles Red Black. Y si las inserciones y eliminaciones son menos frecuentes y la búsqueda es una operación más frecuente, entonces se debe preferir el árbol AVL sobre el árbol rojo negro. --Fuente GEEKSFORGEEKS.ORG
Intenta leer este article
Ofrece algunas buenas ideas sobre diferencias, similitudes, rendimiento, etc.
Aquí hay una cita del artículo:
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 el comportamiento 2-3
En mi opinión, los árboles AVL y RB no están muy lejos en términos de rendimiento. Un árbol RB es simplemente una variante de un árbol B y el equilibrio se implementa de forma diferente que un árbol AVL.
Nuestra comprensión de las diferencias en el rendimiento ha mejorado a lo largo de los años y ahora la razón principal para usar árboles rojo oscuro sobre AVL sería no tener acceso a una buena implementación de AVL ya que son un poco menos comunes quizás porque no están cubiertos por CLRS.
Ambos árboles ahora se consideran formas de árboles de rango equilibrado, pero los árboles rojo-negro son consistentemente más lentos en aproximadamente un 20% en las pruebas del mundo real . O incluso un 30-40% más lento cuando se insertan datos secuenciales .
Entonces, las personas que han estudiado árboles rojo-negros pero no árboles AVL tienden a elegir árboles rojo-negros. Los usos principales para los árboles rojo-negro se detallan en la entrada de Wikipedia para ellos .
Otras respuestas aquí resumen los pros y los contras de los árboles RB y AVL, pero esta diferencia me pareció particularmente interesante:
Los árboles AVL no son compatibles con el costo constante de actualización amortizado [pero los árboles rojo-negro sí]
Fuente: Mehlhorn & Sanders (2008) (sección 7.4)
Entonces, mientras que los árboles RB y AVL garantizan O (log (N)) el tiempo del peor caso para buscar, insertar y eliminar, la restauración de la propiedad AVL / RB después de insertar o eliminar un nodo se puede hacer en O (1) tiempo amortizado para árboles rojo-negro.