Aplicaciones de árboles rojo-negro

Question

¿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?

Answer 1

A menos que tenga requisitos de rendimiento muy específicos, un árbol R-B 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 que los usos específicos de ellos tenderán 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. R-B ofrece una inserción ligeramente más rápida que AVL, a costa de una búsqueda un poco más lenta.

Answer 2

A red-black tree es una implementación particular de self-balancing binary search tree, y hoy parece ser la opción de implementación más popular.

Binary search trees se utilizan para implementar mapas finitos, donde almacena un conjunto de claves con los valores asociados. También puede implementar conjuntos utilizando solo las claves y no almacenando ningún valor.

El equilibrio del árbol es necesario 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 tablas hash es que puede recorrer el árbol de forma eficiente en orden de clasificación.

AVL-trees son otra variante de los á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.

Así que los árboles rojo-negro son sin duda una buena opción, pero no la única para esta aplicación.

Answer 3

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 ir para 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 eliminación pueden llevar algún tiempo El árbol AVl se puede utilizar para dicción de lenguaje donde solo debe construir la estructura de datos y el rojo el árbol negro se usa en el planificador completamente justo que se usa en los kernels actuales de Linux.

las restricciones aplicadas en el árbol negro rojo también refuerzan el punto que la ruta desde la raíz hasta la hoja más alejada no es más de dos veces más larga que la ruta desde la raíz hasta la hoja más cercana.

Por cierto que usted puede buscar los diferentes seach e inserte tiempo, etc necesarios para un árbol negro rojo aquí abajo

 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) 

Answer 4

Rojo Negro Los árboles son de una clase de auto equilibrio BSTs y como respondida por otros, tal árbol de auto equilibrio puede ser utilizado. Me gustaría agregar que los árboles rojo-negro son ampliamente utilizados como tablas de símbolos del sistema.Por ejemplo, se utilizan para implementar lo siguiente:

• Java: java.util.TreeMap, java.util.TreeSet.
• C++ STL: mapa, multimap, multiset.
• núcleo de Linux: planificador completamente justo, Linux/rbtree.h

Answer 5

El planificador de procesos en Linux utiliza Rojo Negro árboles. Los árboles negros rojos son un reemplazo para las colas de ejecución que tenían prioridades para los procesos en cola para que el planificador recogiera.

Completely Fair Scheduler (C.F.S) es el nombre de un programador de procesos que se fusionó en la versión 2.6.23 del kernel de Linux. Maneja la asignación de recursos de la CPU para la ejecución de procesos, y tiene como objetivo maximizar la utilización general de la CPU al tiempo que maximiza el rendimiento interactivo.