algorithm - rojinegros - ¿Cómo funciona un árbol rojo-negro?
ejercicios arboles rojo negro (2)
Para búsquedas y recorridos, es lo mismo que cualquier árbol binario.
Para inserciones y eliminaciones, se aplican algoritmos más sofisticados con el objetivo de garantizar que el árbol no pueda estar demasiado desequilibrado. Esto garantiza que todas las operaciones de un solo elemento siempre se ejecutarán en el peor momento O (log n), mientras que en un árbol binario simple, el árbol binario puede desequilibrarse tanto que es efectivamente una lista enlazada, lo que da a O (n) el peor rendimiento de caso para cada operación de un solo elemento.
La idea básica del árbol rojo-negro es imitar un árbol B con hasta 3 teclas y 4 hijos por nodo. Los árboles B (o variaciones como los árboles B +) se utilizan principalmente para los índices de base de datos y para los datos almacenados en el disco duro.
Cada nodo de árbol binario tiene un "color" - rojo o negro. Cada nodo negro es, en la analogía del árbol B, la raíz del subárbol para el subárbol que se ajusta dentro de ese nodo del árbol B. Si este nodo tiene hijos rojos, también se consideran parte del mismo nodo B-tree. Por lo tanto, es posible (aunque no se hace en la práctica) convertir un árbol rojo-negro en un árbol B y volver, con (la mayoría) de la estructura conservada. La única anomoly posible es que cuando un nodo de árbol B tiene dos teclas y tres hijos, tiene la opción de elegir la tecla que va al nodo negro en el árbol rojo-negro equivalente.
Por ejemplo, con árboles rojo-negros, cada línea desde la raíz a la hoja tiene el mismo número de nodos negros. Esta regla se deriva de la regla del árbol B de que todos los nodos de hoja están a la misma profundidad.
Aunque esta es la idea básica de la que se derivan los árboles rojo-negro, los algoritmos utilizados en la práctica para las inserciones y eliminaciones se modifican para hacer cumplir todas las reglas del árbol B (puede haber una excepción menor, lo olvido) durante las actualizaciones, pero son adaptado para la forma de árbol binario. Esto significa que hacer una inserción o eliminación de árbol rojo-negro puede dar una estructura diferente para el resultado de la que se esperaría comparando con hacer la inserción o eliminación de árbol B.
Para más detalles, siga el enlace de Wikipedia que MigDus ya suministró.
Hay muchas preguntas sobre los árboles rojo-negro, pero ninguna de ellas responde cómo funcionan. ¿Por qué se llama rojo-negro? ¿Cómo mantiene esto equilibrado el árbol (aumentando así el rendimiento en un árbol de búsqueda binario normal no equilibrado)? Sólo estoy buscando una visión general de cómo y por qué funciona.
Un árbol rojo-negro es un árbol binario ordenado donde cada vértice está coloreado de rojo o negro. La intuición es que un vértice rojo debe verse a la misma altura que su padre (es decir, se considera que un borde de un vértice rojo es "horizontal" en lugar de "descendente").
[No creo que la entrada de Wikipedia aclare este punto.]
Las reglas habituales para los árboles rojo-negros requieren que un vértice rojo nunca apunte a otro vértice rojo. Esto significa que los arreglos posibles de vértices para cualquier subárbol arraigado con un vértice negro (bbb, bbr, rbb, rbr - para [left child] [root] [right child]) corresponden a 234 árboles.
Buscar un árbol rojo-negro es lo mismo que buscar un árbol binario ordinario. La inserción y la eliminación son similares, excepto que puede requerirse una rotación de "reparación" en algún momento para conservar el invariante rojo-negro.
¡Aclamaciones!