algorithm - online - red black tree
Aplicaciones de árboles rojo-negro (4)
¿Cuáles son las aplicaciones de los árboles rojo-negro? ¿Hay alguna aplicación donde solo se puedan usar RB Trees y ninguna otra estructura de datos?
A menos que tenga requisitos de rendimiento muy específicos, un árbol RB podría ser reemplazado por otro árbol binario autoequilibrado, por ejemplo, un árbol AVL. Elegir entre los dos es básicamente una optimización del rendimiento: ofrecen las mismas operaciones básicas.
No es que ninguno de ellos sea definitivamente "más rápido" que el otro, solo que son lo suficientemente diferentes como para que los usos específicos de ellos tiendan a tener un rendimiento ligeramente diferente, en igualdad de condiciones. Entonces, si dibujas tus requisitos con cuidado o por casualidad, podrías terminar con uno de ellos siendo "lo suficientemente rápido" para tu uso, y el otro no. RB ofrece una inserción ligeramente más rápida que AVL, a costa de una búsqueda un poco más lenta.
Los árboles negros rojos son de una clase de BST que se equilibran a sí mismos y, como han respondido otros, se puede usar cualquier árbol de autoequilibrio. Me gustaría agregar que los árboles rojo-negro son ampliamente utilizados como tablas de símbolos del sistema. Por ejemplo, se usan para implementar lo siguiente:
- Java: java.util.TreeMap, java.util.TreeSet.
- C ++ STL: mapa, multimapa, multiset.
- Kernel de Linux: planificador completamente justo, linux / rbtree.h
No existe tal regla, como el rojo negro solo se puede usar en un caso particular, depende de la aplicación en casos como cuando tiene que construir el árbol una sola vez y debe consultarlo muchas veces, entonces puede buscar un árbol AVL porque en AVL la búsqueda de árboles es bastante rápida ... pero está estrictamente equilibrada, por lo que la inserción y supresión pueden llevar algún tiempo. El árbol AVl puede usarse para dicción de lenguaje donde se debe construir la estructura de datos una sola vez y el árbol negro rojo. Programador justo usado en los kernels actuales de Linux ahora en días.
las restricciones aplicadas en el árbol negro rojo también refuerzan el punto de que el camino desde la raíz hasta la hoja más alejada no es más de dos veces más largo que el camino desde la raíz hasta la hoja más cercana.
Por cierto, puedes buscar los diferentes tiempos de búsqueda e inserción, etc. necesarios para un árbol negro rojo aquí
Average Worst case
Space O(n) O(n)
Search O(log n) O(log n)
Insert O(log n) O(log n)
Delete O(log n) O(log n)
Un árbol rojo-negro es una implementación particular de un árbol de búsqueda binaria autoequilibrante , y hoy parece ser la opción de implementación más popular.
Los árboles binarios de búsqueda se utilizan para implementar mapas finitos, donde almacena un conjunto de claves con valores asociados. También puede implementar conjuntos utilizando solo las claves y no almacenando ningún valor.
Se necesita equilibrar el árbol para garantizar un buen rendimiento, ya que de lo contrario el árbol podría degenerar en una lista, por ejemplo, si inserta claves que ya están ordenadas.
La ventaja de los árboles de búsqueda sobre las tablas hash es que puede recorrer el árbol de manera eficiente en orden de clasificación.
AVL-trees son otra variante de árboles de búsqueda binaria equilibrada. Eran populares antes de que los árboles rojo oscuro fueran conocidos. Se equilibran más cuidadosamente, con una diferencia máxima de uno entre las alturas del subárbol izquierdo y derecho (los árboles RB garantizan como máximo un factor de dos). Su principal inconveniente es que el reequilibrio requiere más esfuerzo.
Entonces, los árboles rojo-negros son ciertamente una buena pero no la única opción para esta aplicación.