¿Cómo funciona un árbol rojo-negro?

Question

Hay muchas preguntas en torno a los árboles rojo-negro, pero ninguno de ellos responde cómo funcionan. ¿Por qué se llama rojo-negro? ¿Cómo mantiene esto equilibrado el árbol (aumentando así el rendimiento sobre un árbol de búsqueda binaria normal desequilibrado)? Solo estoy buscando una visión general de cómo y por qué funciona.

Answer 1

Para búsquedas y recorridos, es lo mismo que cualquier árbol binario.

Para inserciones y eliminaciones, se aplican algoritmos más sofisticados que tienen como objetivo garantizar que el árbol no pueda estar demasiado desequilibrado. Esto garantiza que todas las operaciones de elementos individuales siempre se ejecutarán en el peor tiempo O (log n), mientras que en un árbol binario simple el árbol binario puede desequilibrarse tanto que es efectivamente una lista enlazada, dando 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 B-tree con hasta 3 claves y 4 hijos por nodo. B-trees (o variaciones como árboles B +) se utilizan principalmente para índices de bases de datos y para 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 B-tree. Si este nodo tiene hijos rojos, también se los considera parte del mismo nodo B-tree. De modo que es posible (aunque no se hace en la práctica) convertir un árbol rojo-negro en un árbol B y volver, conservando (la mayoría) la estructura. La única anomalía posible es que cuando un nodo de árbol B tiene dos claves y tres hijos, puede elegir qué clave va en el nodo negro en el árbol rojo-negro equivalente.

Por ejemplo, con árboles rojo-negro, 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 que dice que todos los nodos hoja tienen la misma profundidad. Aunque esta es la idea básica de la que se derivan árboles rojo-negro, los algoritmos utilizados en la práctica para inserciones y eliminaciones se modifican para aplicar todas las reglas del árbol B (puede haber una excepción menor, se me olvida) actualizaciones, pero están diseñados para la forma de árbol binario. Esto significa que al hacer una inserción o eliminación de un árbol rojo-negro puede dar una estructura diferente para el resultado de la que esperaría comparar al hacer la inserción o eliminación del árbol B.

Para obtener más información, siga el Wikipedia link que ya proporcionó MigDus.

Answer 2

Un árbol rojo-negro es un árbol binario ordenado donde cada vértice es de color rojo o negro. La intuición es que un vértice rojo debe verse a la misma altura que su elemento primario (es decir, un borde a un vértice rojo se considera "horizontal" en lugar de "descendente").

[I no creen la entrada de Wikipedia aclara este punto.]

las normas habituales para árboles rojo-negro que requieren un vértice rojo Nunca apunte a otro vértice rojo. Esto significa que los posibles arreglos de vértices para cualquier subárbol enraizado con un vértice negro (bbb, bbr, rbb, rbr - para [niño izquierdo] [raíz] [niño derecho]) corresponden a 234 árboles.

Buscar en un árbol rojo-negro es lo mismo que buscar en un árbol binario ordinario. La inserción y la eliminación son similares, excepto que puede ser necesaria una rotación de "reparación" en algún momento para preservar la invariante roja-negra.

¡Salud!