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

Question

Hay muchas preguntas sobre los árboles rojos-negros, 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 binario normal no balanceado)? Solo estoy buscando una descripción general de cómo y por qué funciona.

Answer 1

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

Para insertos y eliminaciones, se aplican algoritmos más sofisticados que tienen como objetivo garantizar que el árbol no pueda estar demasiado desequilibrado. Estos garantizan que todas las operaciones de un solo elemento siempre se ejecutarán en el peor de los casos de tiempo o (log n), mientras que en un árbol binario simple, el árbol binario puede estar tan desequilibrado que es efectivamente una lista vinculada, dando o (n) el peor rendimiento de los casos para cada operación de un solo elemento.

La idea básica del árbol rojo-negro es imitar un árbol B con hasta 3 claves y 4 niños por nodo. Los árboles B (o variaciones como los árboles B+) se utilizan principalmente para los índices de bases 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 de á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 a un árbol B y espalda, con (la mayoría) de la estructura conservada. La única anomolia posible es que cuando un nodo B-Tree tiene dos claves y tres hijos, tiene una opción de que la clave va en el nodo negro en el árbol rojo-negro equivalente.

Por ejemplo, con árboles rojos negros, cada línea desde la raíz hasta 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 tienen la misma profundidad.

Aunque esta es la idea básica de la que se derivan los árboles rojos-negro, los algoritmos utilizados en la práctica para insertos y eliminaciones se modifican para hacer cumplir todas las reglas de árbol B (puede haber una excepción menor, olvido) durante las actualizaciones, pero son. personalizado para la forma del árbol binario. Esto significa que hacer un árbol o eliminación de árbol rojo-negro puede dar una estructura diferente para el resultado que la que esperaría comparar con el inserto o eliminación del árbol B.

Para más detalles, siga el Wikipedia Link Ese Migdus ya se suministró.

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 como a la misma altura que su padre (es decir, se considera un borde de un vértice rojo como "horizontal" en lugar de "descender").

No creo que la entrada de Wikipedia aclare este punto.

Las reglas habituales para los árboles rojos-negro requieren que un vértice rojo nunca apunte a otro vértice rojo. Esto significa que las posibles arreglos de vértice 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 un árbol rojo negro es lo mismo que buscar en un árbol binario ordinario. La inserción y la deleción son similares, excepto que se puede requerir una rotación de "reparación" en algún momento para preservar el invariante rojo-negro.

¡Salud!