Árbol rojo-negro

En informática , un árbol rojo-negro es una estructura de datos de árbol de búsqueda binaria autoequilibrada que se caracteriza por el rápido almacenamiento y recuperación de información ordenada. Los nodos de un árbol rojo-negro contienen un bit de "color" adicional, generalmente representado en rojo y negro, que ayuda a garantizar que el árbol esté siempre aproximadamente equilibrado. ^{[ 1 ]}

Cuando se modifica el árbol, el nuevo árbol se reorganiza y se "recolorea" para restaurar las propiedades de color que limitan el desequilibrio que puede presentar en el peor de los casos. Las propiedades están diseñadas para que esta reorganización y recoloración se realicen de manera eficiente.

El (re)equilibrio no es perfecto, pero garantiza la búsqueda en${\displaystyle O(\log n)}$tiempo, donde${\displaystyle n}$es el número de entradas en el árbol. Las operaciones de inserción y eliminación, junto con la reorganización y el cambio de color del árbol, también se ejecutan en${\displaystyle O(\log n)}$tiempo. ^{[ 2 ] [ 3 ]}

El seguimiento del color de cada nodo requiere solo un bit de información por nodo, ya que solo hay dos colores (debido a la alineación de memoria presente en algunos lenguajes de programación, el consumo real de memoria puede variar). El árbol no contiene ningún otro dato específico de ser un árbol rojo-negro, por lo que su huella de memoria es casi idéntica a la de un árbol de búsqueda binaria clásico (sin color) . En algunos casos, el bit de información adicional se puede almacenar sin coste adicional de memoria.

En 1972, Rudolf Bayer ^{[ 4 ]} inventó una estructura de datos que era un caso especial de orden 4 de un árbol B. Estos árboles mantenían todos los caminos desde la raíz hasta la hoja con el mismo número de nodos, creando árboles perfectamente equilibrados. Sin embargo, no eran árboles de búsqueda binaria . Bayer los denominó "árbol B binario simétrico" en su artículo y posteriormente se popularizaron como árboles 2-3-4 o incluso árboles 2-3. ^{[ 5 ]}

En un artículo de 1978, "Un marco dicromático para árboles equilibrados", ^{[ 6 ]} Leonidas J. Guibas y Robert Sedgewick derivaron el árbol rojo-negro del árbol B binario simétrico. ^{[ 7 ]} El color "rojo" fue elegido porque era el color de mejor aspecto producido por la impresora láser a color disponible para los autores mientras trabajaban en Xerox PARC . ^{[ 8 ]} Otra respuesta de Guibas afirma que fue debido a los bolígrafos rojos y negros que tenían a su disposición para dibujar los árboles. ^{[ 9 ]}

En 1993, Arne Andersson introdujo la idea de un árbol inclinado hacia la derecha para simplificar las operaciones de inserción y eliminación. ^{[ 10 ]}

En 1999, Chris Okasaki demostró cómo hacer que la operación de inserción fuera puramente funcional. Su función de balance solo necesitaba ocuparse de cuatro casos desequilibrados y un caso equilibrado por defecto. ^{[ 11 ]}

El algoritmo original utilizaba ocho casos desequilibrados, pero Cormen et al. (2001) lo redujeron a seis casos desequilibrados. ^{[ 1 ]} Sedgewick demostró que la operación de inserción se puede implementar en solo 46 líneas de Java . ^{[ 12 ] [ 13 ]} En 2008, Sedgewick propuso el árbol rojo-negro inclinado a la izquierda , aprovechando la idea de Andersson que simplificaba las operaciones de inserción y eliminación. Sedgewick originalmente permitía nodos cuyos dos hijos son rojos, haciendo que sus árboles se parecieran más a los árboles 2-3-4, pero posteriormente se añadió esta restricción, haciendo que los nuevos árboles se parecieran más a los árboles 2-3. Sedgewick implementó el algoritmo de inserción en solo 33 líneas, acortando significativamente sus 46 líneas de código originales. ^{[ 14 ] [ 15 ]}

La profundidad negra de un nodo se define como el número de nodos negros desde la raíz hasta ese nodo (es decir, el número de ancestros negros). La altura negra de un árbol rojo-negro es el número de nodos negros en cualquier ruta desde la raíz hasta las hojas, que, por el requisito 4 , es constante (alternativamente, podría definirse como la profundidad negra de cualquier nodo hoja). ^{[ 16 ] : 154–165} La altura negra de un nodo es la altura negra del subárbol enraizado por él. En este artículo, la altura negra de un nodo nulo se establecerá en 0, porque su subárbol está vacío como sugiere la figura de ejemplo, y su altura de árbol también es 0.

Además de los requisitos impuestos a un árbol de búsqueda binaria, un árbol rojo-negro debe cumplir con lo siguiente : ^{[ 17 ]}

1. Cada nodo es rojo o negro.
2. Todos los nodos nulos se consideran negros.
3. Un nodo rojo no tiene un hijo rojo.
4. Cada ruta desde un nodo dado a cualquiera de sus nodos hoja (es decir, a cualquier nodo nulo descendiente) pasa por el mismo número de nodos negros.
5. (Conclusión) Si un nodo N tiene exactamente un hijo, el hijo debe ser rojo. Si el hijo fuera negro, sus hojas estarían en una profundidad negra diferente a la del nodo nulo de N (que se considera negro según la regla 2), violando el requisito 4 .

Algunos autores, por ejemplo Cormen y otros, ^{[ 17 ]} afirman que "la raíz es negra" es el quinto requisito; pero no Mehlhorn y Sanders ^{[ 16 ]} ni Sedgewick y Wayne. ^{[ 15 ] : 432–447} Dado que la raíz siempre puede cambiarse de roja a negra, esta regla tiene poco efecto en el análisis. Este artículo también la omite, porque altera ligeramente los algoritmos y las demostraciones recursivas.

Por ejemplo, todo árbol binario perfecto que consta únicamente de nodos negros es un árbol rojo-negro.

Las operaciones de solo lectura, como la búsqueda o el recorrido del árbol, no afectan a ninguno de los requisitos. Por el contrario, las operaciones de modificación insertar y eliminar mantienen fácilmente los requisitos 1 y 2, pero con respecto a los demás requisitos se debe hacer un esfuerzo adicional para evitar introducir una violación del requisito 3, llamadoviolación roja , o del requisito 4, llamado unaviolación negra .

Los requisitos imponen una propiedad crítica de los árboles rojo-negro: el camino desde la raíz hasta la hoja más lejana no es más del doble de largo que el camino desde la raíz hasta la hoja más cercana . El resultado es que el árbol está equilibrado en altura . Dado que operaciones como insertar, eliminar y buscar valores requieren un tiempo en el peor de los casos proporcional a la altura${\displaystyle h}$del árbol, este límite superior en la altura permite que los árboles rojo-negro sean eficientes en el peor de los casos, es decir, logarítmicos en el número${\displaystyle n}$de entradas, es decir${\displaystyle h\in O(\log n)}$(una propiedad que comparten todos los árboles autoequilibrados, por ejemplo, el árbol AVL o el árbol B , pero no los árboles de búsqueda binaria ordinarios ). Para una demostración matemática, véase la sección Demostración de límites .

Los árboles rojo-negro, como todos los árboles de búsqueda binaria , permiten un acceso secuencial bastante eficiente (por ejemplo , recorrido en orden , es decir: en el orden Izquierda-Raíz-Derecha) de sus elementos. Pero también admiten un acceso directo asintóticamente óptimo a través de un recorrido desde la raíz hasta la hoja, lo que resulta en${\displaystyle O(\log n)}$tiempo de búsqueda.

Los árboles rojo-negro son similares en estructura a los árboles 2-3-4 , que son árboles B de orden 4. ^{[ 18 ]} En los árboles 2-3-4, cada nodo puede contener entre 1 y 3 valores y tener entre 2 y 4 hijos. Estos nodos 2-3-4 corresponden a grupos de nodos negros e hijos rojos en los árboles rojo-negro, como se muestra en la figura 1. No es una correspondencia 1 a 1 , porque los nodos 3 tienen dos representaciones equivalentes: el hijo rojo puede estar a la izquierda o a la derecha. La variante del árbol rojo-negro inclinado a la izquierda hace que esta relación sea exactamente 1 a 1, al permitir solo la representación del hijo izquierdo. Dado que cada nodo 2-3-4 tiene un nodo negro correspondiente, el invariante 4 de los árboles rojo-negro es equivalente a decir que las hojas de un árbol 2-3-4 están todas en el mismo nivel.

A pesar de las similitudes estructurales, las operaciones con árboles rojo-negro son más económicas que con árboles B. Los árboles B requieren la gestión de vectores de longitud variable, mientras que los árboles rojo-negro son simplemente árboles binarios. ^{[ 19 ]}

Los árboles rojo-negro ofrecen garantías en el peor de los casos para el tiempo de inserción, el tiempo de eliminación y el tiempo de búsqueda. Esto no solo los hace valiosos en aplicaciones sensibles al tiempo, como las aplicaciones en tiempo real , sino que también los convierte en valiosos bloques de construcción en otras estructuras de datos que proporcionan garantías en el peor de los casos. Por ejemplo, muchas estructuras de datos utilizadas en geometría computacional se basan en árboles rojo-negro, y el planificador completamente justo y la llamada al sistema epoll del kernel de Linux utilizan árboles rojo-negro. ^{[ 20 ] [ 21 ]} El árbol AVL es otra estructura que admite${\displaystyle O(\log n)}$búsqueda, inserción y eliminación. Los árboles AVL pueden ser coloreados de rojo a negro, y por lo tanto son un subconjunto de árboles rojo-negro. La altura en el peor caso de AVL es 0,720 veces la altura en el peor caso de árboles rojo-negro, por lo que los árboles AVL están más rígidamente equilibrados. Las mediciones de rendimiento de Ben Pfaff con casos de prueba realistas en 79 ejecuciones encuentran relaciones AVL a RB entre 0,677 y 1,077, mediana en 0,947 y media geométrica 0,910. ^{[ 22 ]} El rendimiento de los árboles WAVL se encuentra entre los árboles AVL y los árboles rojo-negro.

Los árboles rojo-negro también son particularmente valiosos en la programación funcional , donde son una de las estructuras de datos persistentes más comunes , utilizadas para construir arreglos y conjuntos asociativos que pueden conservar versiones anteriores después de mutaciones. La versión persistente de los árboles rojo-negro requiere${\displaystyle O(\log n)}$espacio para cada inserción o eliminación, además del tiempo.

Por cada árbol 2-3-4 , existen árboles rojo-negro correspondientes con elementos de datos en el mismo orden. Las operaciones de inserción y eliminación en árboles 2-3-4 también son equivalentes a las rotaciones y cambios de color en árboles rojo-negro. Esto convierte a los árboles 2-3-4 en una herramienta importante para comprender la lógica subyacente a los árboles rojo-negro, y por ello muchos textos introductorios de algoritmos los presentan justo antes de los árboles rojo-negro, aunque los árboles 2-3-4 no se utilicen con frecuencia en la práctica.

En 2008, Sedgewick introdujo una versión más simple del árbol rojo-negro llamada árbol rojo-negro inclinado a la izquierda ^{[ 23 ]} al eliminar un grado de libertad previamente no especificado en la implementación. El LLRB mantiene un invariante adicional que todos los enlaces rojos deben inclinarse a la izquierda excepto durante inserciones y eliminaciones. Los árboles rojo-negro pueden hacerse isométricos a árboles 2-3 , ^{[ 24 ]} o árboles 2-3-4, ^{[ 23 ]} para cualquier secuencia de operaciones. La isometría del árbol 2-3-4 fue descrita en 1978 por Sedgewick. ^{[ 6 ]} Con los árboles 2-3-4, la isometría se resuelve mediante un "cambio de color", que corresponde a una división, en la que el color rojo de dos nodos hijos abandona a los hijos y se mueve al nodo padre.

La descripción original del árbol tango , un tipo de árbol optimizado para búsquedas rápidas, utiliza específicamente árboles rojo-negro como parte de su estructura de datos. ^{[ 25 ]}

A partir de Java 8, el HashMap se ha modificado de tal manera que, en lugar de usar una LinkedList para almacenar diferentes elementos con códigos hash que colisionan , se utiliza un árbol rojo-negro. Esto da como resultado una mejora en la complejidad temporal de la búsqueda de dicho elemento.${\displaystyle O(m)}$a${\displaystyle O(\log m)}$dónde${\displaystyle m}$es el número de elementos con hashes que colisionan. ^{[ 26 ]}

Las operaciones de solo lectura, como la búsqueda o el recorrido del árbol, en un árbol rojo-negro no requieren ninguna modificación respecto a las utilizadas en los árboles de búsqueda binaria , ya que todo árbol rojo-negro es un caso especial de un árbol de búsqueda binaria simple. Sin embargo, el resultado inmediato de una inserción o eliminación puede violar las propiedades de un árbol rojo-negro, cuya restauración se denomina reequilibrio , de modo que los árboles rojo-negro se autoequilibran. El reequilibrio (es decir, los cambios de color) tiene una complejidad temporal en el peor de los casos de${\displaystyle O(\log n)}$y promedio de${\displaystyle O(1)}$, ^{[ 27 ] : 310 [ 16 ] : 158} aunque en la práctica son muy rápidos. Además, el reequilibrio no requiere más de tres rotaciones del árbol ^{[ 28 ]} (dos para la inserción).

Este es un ejemplo de implementación de las operaciones de inserción y eliminación en C. A continuación se muestran las estructuras de datos y la rotate_subtreefunción auxiliar utilizadas en los ejemplos de inserción y eliminación.

typedef enum Color : char {NEGRO ,ROJO} Color ;typedef enum Dirección : char {IZQUIERDA ,BIEN} Dirección ;// nodo de árbol rojo-negrotypedef struct Nodo {struct Node * parent ; // null para el nodo raízunión {// Unión para que podamos usar ->izquierda/->derecha o ->hijo[0]/->hijo[1]struct {struct Nodo * izquierda ;struct Nodo * derecha ;};struct Nodo * hijo [ 2 ];};Color color ;clave entera ;} Nodo ;typedef struct {struct Nodo * raíz ;} Árbol ;Dirección estática dirección ( const Nodo * N ) {devolver N == N -> padre -> derecha ? DERECHA : IZQUIERDA ;}Nodo * rotar_subárbol ( Árbol * árbol , Nodo * sub , Dirección dir ) {Nodo * sub_padre = sub -> padre ;Nodo * nueva_raíz = sub -> hijo [ 1 - dir ]; // 1 - dir es la dirección opuestaNodo * nuevo_hijo = nueva_raíz -> hijo [ directorio ];sub -> hijo [ 1 - dir ] = nuevo_hijo ;si ( nuevo_hijo ) {nuevo_hijo -> padre = sub ;}nueva_raíz -> hijo [ dir ] = sub ;nueva_raíz -> padre = subpadre ;sub -> padre = nueva_raíz ;si ( sub_padre ) {sub_padre -> hijo [ sub == sub_padre -> derecha ] = nueva_raíz ;} demás {árbol -> raíz = nueva_raíz ;}devolver nueva_raíz ;}

Inserción

La inserción comienza colocando el nuevo nodo (no nulo), digamos N , en la posición en el árbol de búsqueda binaria de un nodo nulo cuya clave del predecesor en orden es menor que la clave del nuevo nodo, que a su vez es menor que la clave de su sucesor en orden. (Con frecuencia, este posicionamiento es el resultado de una búsqueda dentro del árbol inmediatamente anterior a la operación de inserción y consiste en un nodo Pjunto con una dirección dircon P->child[dir] == NULL.) El nodo recién insertado se colorea temporalmente de rojo para que todos los caminos contengan el mismo número de nodos negros que antes. Pero si su padre, digamos P , también es rojo, entonces esta acción introduce una violación de rojo .

// El padre es opcionalvoid insertar ( Árbol * árbol , Nodo * nodo , Nodo * padre , Dirección dir ) {nodo -> color = ROJO ;nodo -> padre = padre ;si ( ! padre ) {árbol -> raíz = nodo ;devolver ;}padre -> hijo [ dir ] = nodo ;// reequilibrar el árbolhacer {// Caso n.º 1si ( padre -> color == NEGRO ) {devolver ;}Nodo * abuelo = padre -> padre ;si ( ! abuelo ) {// Caso n.º 4padre -> color = NEGRO ;devolver ;}dir = dirección ( padre );Nodo * tío = abuelo -> hijo [ 1 - dir ];si ( ! tío || tío -> color == NEGRO ) {si ( nodo == padre -> hijo [ 1 - dir ]) {// Caso n.º 5rotar_subárbol ( árbol , padre , dir );nodo = padre ;padre = abuelo -> hijo [ dir ];}// Caso n.º 6rotar_subárbol ( árbol , abuelo , 1 - dir );padre -> color = NEGRO ;abuelo/a -> color = ROJO ;devolver ;}// Caso n.º 2padre -> color = NEGRO ;tío -> color = NEGRO ;abuelo/a -> color = ROJO ;nodo = abuelo ;} mientras (( padre = nodo -> padre ));// Caso n.º 3devolver ;}

El bucle de reequilibrio de la operación de inserción tiene las siguientes invariantes :

• El nodo es el nodo actual, inicialmente el nodo de inserción.
• El nodo es rojo al comienzo de cada iteración.
• El requisito 3 se cumple para todos los pares nodo←padre con la posible excepción nodo ← padre cuando padre también es rojo (una violación roja en el nodo ).
• Todas las demás propiedades (incluido el requisito 4 ) se cumplen en todo el árbol.

Notas para insertar diagramas

• En los diagramas, P se usa para el padre de N , G para su abuelo y U para su tío. En la tabla, "—" indica la raíz.
• Los diagramas muestran el nodo padre P como el hijo izquierdo de su padre G, aunque es posible que P esté a cualquiera de los lados. El código de ejemplo cubre ambas posibilidades mediante la variable lateral dir.
• Los diagramas muestran los casos en los que P también es rojo, la violación roja.
• La columna x indica el cambio en la dirección del hijo, es decir, o (de "exterior") significa que P y N son hijos izquierdos o derechos, mientras que i (de "interior") significa que la dirección del hijo cambia de P a N.
• El grupo de columnas anterior define el caso, cuyo nombre se indica en la columna case . De este modo, se ignoran los posibles valores en las celdas vacías. Así, en el caso I2, el código de ejemplo abarca ambas posibilidades de direcciones secundarias de N , aunque el diagrama correspondiente muestre solo una.
• Las filas de la sinopsis están ordenadas de tal manera que la cobertura de todos los casos posibles de RB sea fácilmente comprensible.
• La rotación de la columna indica si una rotación contribuye al reequilibrio.
• La asignación de columnas muestra una asignación de N antes de pasar al siguiente paso. Esto posiblemente induce también una reasignación de los otros nodos P , G y U.
• Si el caso ha modificado algo, esto se muestra en el grupo de columnas que aparece a continuación .
• Un signo en la columna siguiente indica que el reequilibrio se ha completado con este paso. Si la columna posterior determina exactamente un caso, este se indica como el siguiente; de ​​lo contrario, aparecen signos de interrogación.
• En el caso 2, el problema del reequilibrio se agrava.${\displaystyle \Delta h=2}$niveles de árbol o 1 nivel negro más arriba en el árbol, en el que el abuelo G se convierte en el nuevo nodo actual N. Por lo tanto, toma como máximo${\displaystyle {\tfrac {h}{2}}}$pasos de iteración para reparar el árbol (donde h es la altura del árbol). Debido a que la probabilidad de escalada disminuye exponencialmente con cada paso, el costo total de reequilibrio es constante en promedio, de hecho, constante amortizada .
• Las rotaciones ocurren en los casos I6 e I5 + I6 – fuera del bucle. Por lo tanto, ocurren como máximo dos rotaciones en total.

Insertar caja 1

El padre del nodo actual P es negro, por lo que se cumple el requisito 3. El requisito 4 también se cumple según el invariante del bucle .

Insertar caja 2

primera iteración

iteración superior

Insertar caja 2

Si tanto el padre P como el tío U son rojos, ambos pueden ser repintados de negro y el abuelo G se vuelve rojo para mantener el requisito 4. Dado que cualquier ruta a través del padre o el tío debe pasar por el abuelo, el número de nodos negros en estas rutas no ha cambiado. Sin embargo, el abuelo G ahora puede violar el requisito 3, si tiene un padre rojo. Después de reetiquetar G a N, se cumple el invariante del bucle , por lo que el reequilibrio puede iterarse en un nivel negro (= 2 niveles de árbol) más arriba.

Insertar caja 3

Se ha ejecutado el caso de inserción 2 para${\displaystyle {\tfrac {h-1}{2}}}$veces y la altura total del árbol ha aumentado en 1, siendo ahora h . El nodo actual N es la raíz (roja) del árbol, y se satisfacen todas las propiedades RB.

Insertar caja 4

El nodo padre P es rojo y es la raíz. Como N también es rojo, se incumple el requisito 3. Pero después de cambiar el color de P , el árbol tiene forma RB. La altura negra del árbol aumenta en 1.

Insertar caja 5

primera iteración

iteración superior

Insertar Caso 5

El padre P es rojo pero el tío U es negro. El objetivo final es rotar el nodo padre P a la posición de abuelo, pero esto no funcionará si N es un nieto "interno" de G (es decir, si N es el hijo izquierdo del hijo derecho de G o el hijo derecho del hijo izquierdo de G ). Una dirrotación en P cambia los roles del nodo actual N y su padre P. La rotación agrega caminos a través de N (los del subárbol etiquetado como 2 , ver diagrama) y elimina caminos a través de P (los del subárbol etiquetado como 4 ). Pero tanto P como N son rojos, por lo que se conserva el requisito 4. El requisito 3 se restaura en el caso 6.

primera iteración

iteración superior

Insertar caja 6

Insertar caja 6

El nodo actual N ahora es seguro que es un nieto "externo" de G (a la izquierda del hijo izquierdo o a la derecha del hijo derecho). Ahora (1-dir)-rota en G , colocando P en lugar de G y haciendo que P sea el padre de N y G. G es negro y su antiguo hijo P es rojo, ya que se violó el requisito 3. Después de intercambiar los colores de P y G, el árbol resultante satisface el requisito 3. El requisito 4 también permanece satisfecho, ya que todos los caminos que pasaban por el G negro ahora pasan por el P negro .

Debido a que el algoritmo transforma la entrada sin utilizar una estructura de datos auxiliar y utilizando solo una pequeña cantidad de espacio de almacenamiento adicional para variables auxiliares, es in situ .

Eliminación

Casos sencillos

• Cuando el nodo eliminado tiene dos hijos (distintos de NULL), podemos intercambiar su valor con el de su sucesor en orden (el hijo más a la izquierda del subárbol derecho) y, en su lugar, eliminar el sucesor. Dado que el sucesor es el más a la izquierda, solo puede tener un hijo a la derecha (distinto de NULL) o ningún hijo.
• Cuando el nodo eliminado tiene solo un hijo (distinto de NULL). En este caso, simplemente reemplace el nodo con su hijo y píntelo de negro.
  • El único hijo (no nulo) debe ser rojo según la conclusión 5 , y el nodo eliminado debe ser negro según el requisito 3 .
• Cuando el nodo eliminado no tiene hijos (ambos son NULL) y es la raíz, reemplácelo con NULL. El árbol queda vacío.
• Cuando el nodo eliminado no tiene hijos (ambos NULL) y está en rojo , simplemente elimine el nodo hoja.
• Cuando el nodo eliminado no tiene hijos (ambos son NULL) y es negro , eliminarlo creará un desequilibrio y requerirá un reequilibrio, como se explica en la siguiente sección.

Eliminación de una hoja negra sin raíz

El caso complejo se da cuando N no es la raíz, está coloreado de negro y no tiene hijos propios (⇔ solo hijos NULL). En la primera iteración, N se reemplaza por NULL.

void remove ( Tree * tree , Node * node ) {Nodo * padre = nodo -> padre ;Nodo * hermano ;Nodo * close_nephew ;Nodo * sobrino_distante ;Dirección dir = dirección ( nodo );padre -> hijo [ dir ] = NULL ;ir a start_balance ;hacer {dir = dirección ( nodo );saldo_inicial :hermano = padre -> hijo [ 1 - dir ];sobrino_distante = hermano -> hijo [ 1 - dir ];sobrino_cercano = hermano -> hijo [ dir ];si ( hermano -> color == ROJO ) {// Caso n.º 3rotar_subárbol ( árbol , padre , dir );padre -> color = ROJO ;hermano -> color = NEGRO ;hermano = sobrino_cercano ;sobrino_distante = hermano -> hijo [ 1 - dir ];si ( distant_nephew && distant_nephew -> color == ROJO ) {ir al caso_6 ;}sobrino_cercano = hermano -> hijo [ dir ];si ( close_nephew && close_nephew -> color == ROJO ) {ir al caso_5 ;}// Caso n.º 4hermano -> color = ROJO ;padre -> color = NEGRO ;devolver ;}si ( distant_nephew && distant_nephew -> color == ROJO ) {ir al caso_6 ;}si ( close_nephew && close_nephew -> color == ROJO ) {ir al caso_5 ;}si ( padre -> color == ROJO ) {// Caso n.º 4hermano -> color = ROJO ;padre -> color = NEGRO ;devolver ;}// Caso n.º 2hermano -> color = ROJO ;nodo = padre ;} mientras ( padre = nodo -> padre );// Caso n.º 1devolver ;caso_5 :rotar_subárbol ( árbol , hermano , 1 - dir );hermano -> color = ROJO ;sobrino_cercano -> color = NEGRO ;sobrino_distante = hermano/a ;hermano = sobrino_cercano ;caso_6 :rotar_subárbol ( árbol , padre , dir );hermano -> color = padre -> color ;padre -> color = NEGRO ;sobrino_distante -> color = NEGRO ;devolver ;}

El bucle de reequilibrio de la operación de eliminación tiene la siguiente invariante :

• Al comienzo de cada iteración, la altura negra de N es igual al número de iteración menos uno, lo que significa que en la primera iteración es cero y que N es un verdadero nodo negro en iteraciones posteriores.
• El número de nodos negros en los caminos que pasan por N es uno menos que antes de la eliminación, mientras que permanece sin cambios en todos los demás caminos, de modo que hay una violación de nodos negros en P si existen otros caminos.
• Todas las demás propiedades (incluido el requisito 3 ) se cumplen en todo el árbol.

Notas para eliminar diagramas

• En los diagramas a continuación, P se usa para el padre de N , S para el hermano de N , C (que significa sobrino cercano ) para el hijo de S en la misma dirección que N , y D (que significa sobrino lejano ) para el otro hijo de S ( S no puede ser un nodo NULO en la primera iteración, porque debe tener una altura negra de uno, que era la altura negra de N antes de su eliminación, pero C y D pueden ser nodos NULOS).
• Los diagramas muestran el nodo actual N como el hijo izquierdo de su padre P, aunque es posible que N esté a cualquiera de los lados. Los ejemplos de código cubren ambas posibilidades mediante la variable lateral dir.
• Al inicio (en la primera iteración) de la eliminación, N es el nodo NULO que reemplaza al nodo que se va a eliminar. Debido a que su ubicación en el nodo padre es lo único importante, se simboliza con (lo que significa: el nodo actual N es un nodo NULO e hijo izquierdo) en la columna izquierda de los diagramas de eliminación. A medida que avanza la operación, también los nodos adecuados (de altura negra ≥ 1) pueden convertirse en actuales (ver, por ejemplo, el caso 2 ).
• Al contar las balas negras ( y ) en un diagrama de eliminación, se puede observar que los caminos que pasan por N tienen una bala menos que los demás. Esto significa una violación negra en P , si existe.
• La constelación de colores en el grupo de columnas anterior define el caso, cuyo nombre se indica en la columna case . Por lo tanto, se ignoran los posibles valores en las celdas que se dejan vacías.
• Las filas de la sinopsis están ordenadas de tal manera que la cobertura de todos los casos posibles de RB sea fácilmente comprensible.
• La rotación de la columna indica si una rotación contribuye al reequilibrio.
• La asignación de columnas muestra una asignación de N antes de entrar en un paso de iteración posterior. Esto posiblemente induce una reasignación de los otros nodos P , C , S , D también.
• Si el caso ha modificado algo, esto se muestra en el grupo de columnas que aparece a continuación .
• Un signo en la columna siguiente indica que el reequilibrio se ha completado con este paso. Si la columna posterior determina exactamente un caso, este se indica como el siguiente; de ​​lo contrario, aparecen signos de interrogación.
• El bucle es donde se agrava el problema del reequilibrio.${\displaystyle \Delta h=1}$nivel superior en el árbol, ya que el padre P se convierte en el nuevo nodo actual N. Por lo tanto, se necesitan como máximo h iteraciones para reparar el árbol (donde h es la altura del árbol). Debido a que la probabilidad de escalada disminuye exponencialmente con cada iteración, el costo total de reequilibrio es constante en promedio, de hecho, constante amortizado . (Como nota al margen: Mehlhorn y Sanders señalan: "Los árboles AVL no admiten costos de actualización amortizados constantes". ^{[ 16 ] : 165, 158} Esto es cierto para el reequilibrio después de una eliminación, pero no para la inserción AVL. ^{[ 32 ]} )
• Desde el cuerpo del bucle salen ramas hacia los casos 3 , 6 , 5 , 4 y 1 ; la sección "Eliminar caso 3" tiene a su vez tres ramas diferentes hacia los casos 6 , 5 y 4 .
• Se producen rotaciones en los casos 6 , 5 + 6 y 3 + 5 + 6 , todos fuera del bucle. Por lo tanto, se producen como máximo tres rotaciones en total.

Eliminar caso 1

El nodo actual N es la nueva raíz. Se ha eliminado un nodo negro de cada ruta, por lo que se conservan las propiedades RB. La altura negra del árbol disminuye en 1.

Eliminar caso 2

→ Explicación de los símbolos

primera iteración

iteración superior

Eliminar caso D2

P , S y los hijos de S son negros. Después de pintar S de rojo, todos los caminos que pasan por S , que son precisamente aquellos caminos que no pasan por N , tienen un nodo negro menos. Ahora todos los caminos en el subárbol enraizado por P tienen el mismo número de nodos negros, pero uno menos que los caminos que no pasan por P , por lo que el requisito 4 aún puede ser violado. Después de volver a etiquetar P a N, se cumple el invariante del bucle , de modo que el reequilibrio puede iterarse en un nivel negro (= 1 nivel de árbol) más arriba.

Eliminar caso 3

primera iteración

iteración superior

Eliminar caso D3

El hermano S es rojo, por lo que P y los sobrinos C y D deben ser negros. Una dirrotación A en P convierte a S en el abuelo de N. Luego, tras invertir los colores de P y S , el camino a través de N aún tiene un nodo negro menos. Pero ahora N tiene un padre rojo P y, tras la reasignación, un hermano negro S , por lo que las transformaciones en los casos 4, 5 o 6 pueden restaurar la forma RB.

Eliminar caso 4

primera iteración

iteración superior

Eliminar caso D4

Los hermanos S y sus hijos son negros, pero P es rojo. Intercambiar los colores de S y P no afecta la cantidad de nodos negros en los caminos que pasan por S , pero sí agrega uno a la cantidad de nodos negros en los caminos que pasan por N , compensando así el nodo negro eliminado en esos caminos.

Eliminar caso 5

primera iteración

iteración superior

Eliminar caso D5

El hermano S es negro, el hijo cercano de S , C , es rojo, y el hijo lejano de S , D, es negro. Después de una (1-dir)rotación en S, el sobrino C se convierte en el padre de S y en el nuevo hermano de N. Los colores de S y C se intercambian. Todos los caminos siguen teniendo el mismo número de nodos negros, pero ahora N tiene un hermano negro cuyo hijo lejano es rojo, por lo que la constelación es adecuada para el caso D6. Ni N ni su padre P se ven afectados por esta transformación, y P puede ser rojo o negro ( en el diagrama).

Eliminar caso 6

primera iteración

iteración superior

Eliminar caso D6

El hermano S es negro, el hijo lejano de S , D , es rojo. Después de una dirrotación en P, el hermano S se convierte en el padre de P y del hijo lejano de S , D. Los colores de P y S se intercambian, y D se vuelve negro. Todo el subárbol sigue teniendo el mismo color en su raíz S , es decir, rojo o negro ( en el diagrama), lo que se refiere al mismo color tanto antes como después de la transformación. De esta manera se conserva el requisito 3. Los caminos en el subárbol que no pasan por N (es decir, que pasan por D y el nodo 3 en el diagrama) pasan por el mismo número de nodos negros que antes, pero N ahora tiene un ancestro negro adicional: o P se ha vuelto negro, o era negro y S se agregó como abuelo negro. Por lo tanto, los caminos que pasan por N pasan por un nodo negro adicional, de modo que se restaura el requisito 4 y el árbol total tiene forma RB.

Debido a que el algoritmo transforma la entrada sin utilizar una estructura de datos auxiliar y utilizando solo una pequeña cantidad de espacio de almacenamiento adicional para variables auxiliares, es in situ .

Para${\displaystyle h\in \mathbb {N} }$Hay un árbol rojo y negro de altura${\displaystyle h}$con

nodos (${\displaystyle \lfloor \,\rfloor }$es la función piso ) y no hay ningún árbol rojo-negro de esta altura con menos nodos; por lo tanto, es mínimo . Su altura negra es${\displaystyle \lceil h/2\rceil }$(con raíz negra) o para impares${\displaystyle h}$(luego con una raíz roja) también${\displaystyle (h-1)/2~.}$

Prueba

Para que un árbol rojo-negro de cierta altura tenga un número mínimo de nodos, debe tener exactamente un camino más largo con un número máximo de nodos rojos, para lograr una altura máxima del árbol con una altura mínima de nodos negros. Aparte de este camino, todos los demás nodos tienen que ser negros. ^{[ 15 ] : 444 Bosquejo de la prueba} Si se quita un nodo de este árbol, pierde altura o alguna propiedad RB.

El árbol RB de altura${\displaystyle h=1}$con raíz roja es mínimo. Esto está de acuerdo con

${\displaystyle m_{1}=2^{\lfloor (1+1)/2\rfloor }\!+\!2^{\lfloor 1/2\rfloor }\!\!-\!\!2=2^{1}\!+\!2^{0}\!\!-\!\!2=1~.}$

Un árbol RB mínimo (RB _h en la figura 2) de altura${\displaystyle h>1}$tiene una raíz cuyos dos subárboles hijos son de diferente altura. El subárbol hijo superior es también un árbol RB mínimo, RB _{h –1} , que contiene además un camino más largo que define su altura.${\displaystyle h\!\!-\!\!1}$; tiene${\displaystyle m_{h-1}}$nodos y la altura negra${\displaystyle \lfloor (h\!\!-\!\!1)/2\rfloor =:s.}$El otro subárbol es un árbol binario perfecto de altura (negra)${\displaystyle s}$teniendo${\displaystyle 2^{s}\!\!-\!\!1=2^{\lfloor (h-1)/2\rfloor }\!\!-\!\!1}$nodos negros y ningún nodo rojo. Entonces, el número de nodos se obtiene por inducción.

La gráfica de la función${\displaystyle m_{h}}$es convexa y lineal a trozos con puntos de quiebre en${\displaystyle (h=2k\;|\;m_{2k}=2\cdot 2^{k}\!-\!2)}$dónde${\displaystyle k\in \mathbb {N} .}$La función se ha tabulado como${\displaystyle m_{h}=}$A027383( h –1) para${\displaystyle h\geq 1}$(secuencia A027383 en el OEIS ).

Resolviendo la función para${\displaystyle h}$

La desigualdad${\displaystyle 9>8=2^{3}}$conduce a${\displaystyle 3>2^{3/2}}$, que para impar${\displaystyle h}$conduce a

${\displaystyle m_{h}=3\cdot 2^{(h-1)/2}-2={\bigl (}3\cdot 2^{-3/2}{\bigr )}\cdot 2^{(h+2)/2}-2>2\cdot 2^{h/2}-2}$.

Así que en ambos casos, par e impar,${\displaystyle h}$está en el intervalo

con${\displaystyle n}$siendo el número de nodos. ^{[ 33 ]}

Conclusión

Un árbol rojo y negro con${\displaystyle n}$los nodos (claves) tienen altura de árbol${\displaystyle h\in O(\log n).}$

Además de las operaciones de inserción, eliminación y búsqueda de un solo elemento, se han definido varias operaciones de conjuntos en árboles rojo-negro: unión , intersección y diferencia de conjuntos . Luego, se pueden implementar operaciones masivas rápidas en inserciones o eliminaciones basadas en estas funciones de conjuntos. Estas operaciones de conjuntos dependen de dos operaciones auxiliares, Split y Join . Con las nuevas operaciones, la implementación de árboles rojo-negro puede ser más eficiente y altamente paralelizable. ^{[ 34 ]} Para lograr sus complejidades de tiempo, esta implementación requiere que la raíz pueda ser roja o negra, y que cada nodo almacene su propia altura negra .

• Join : La función Join se aplica a dos árboles rojo-negro t ₁ y t ₂ y a una clave k , donde t ₁ < k < t ₂ , es decir, todas las claves en t ₁ son menores que k , y todas las claves en t ₂ son mayores que k . Devuelve un árbol que contiene todos los elementos en t _{1 y} t ₂ , además de k .

Si los dos árboles tienen la misma altura negra, la operación Join simplemente crea un nuevo nodo con el subárbol izquierdo t ₁ , la raíz k y el subárbol derecho t _2. Si tanto t ₁ como t ₂ tienen la raíz negra, se establece k en rojo. De lo contrario, k se establece en negro.

Si las alturas negras son desiguales, supongamos que t ₁ tiene una altura negra mayor que t ₂ (el otro caso es simétrico). Join sigue la columna derecha de t ₁ hasta un nodo negro c , que está equilibrado con t ₂ . En este punto se crea un nuevo nodo con hijo izquierdo c , raíz k (establecida como roja) e hijo derecho t ₂ para reemplazar a c . El nuevo nodo puede invalidar la invariante rojo-negro porque como máximo pueden aparecer tres nodos rojos en una fila. Esto se puede solucionar con una rotación doble. Si el problema de doble rojo se propaga a la raíz, entonces la raíz se establece como negra, restaurando las propiedades. El costo de esta función es la diferencia de las alturas negras entre los dos árboles de entrada.

• Para dividir un árbol rojo-negro en dos árboles más pequeños (uno con valores menores que la clave x y otro con valores mayores que la clave x) , primero se traza un camino desde la raíz insertando x en el árbol rojo-negro. Tras esta inserción, todos los valores menores que x se ubicarán a la izquierda del camino, y todos los valores mayores que x se ubicarán a la derecha. Al aplicar la operación de unión , todos los subárboles del lado izquierdo se fusionan de abajo hacia arriba utilizando las claves del camino como nodos intermedios para formar el árbol izquierdo, mientras que la parte derecha es simétrica.

Para algunas aplicaciones, Split también devuelve un valor booleano que indica si x aparece en el árbol. El costo de Split es${\displaystyle O(\log n),}$orden de la altura del árbol. Este algoritmo en realidad no tiene nada que ver con ninguna propiedad especial de un árbol rojo-negro, y puede usarse en cualquier árbol con una operación de unión , como un árbol AVL .

El algoritmo de unión es el siguiente:

función joinRightRB(T L , k, T R ): si (T L .color=black) y (T L .blackHeight=T R .blackHeight): devolver Node(T L ,⟨k,red⟩,T R ) T'=Nodo(T L .izquierda,⟨T L .clave,T L .color⟩,unirDerechaRB(T L .derecha,k,T R )) si (T L .color=negro) y (T'.derecha.color=T'.derecha.derecha.color=rojo): T'.right.right.color=negro; return rotateLeft(T') return T' /* T ' ' [rectificar T'] */ función joinLeftRB(T L , k, T R ): /* simétrico a joinRightRB */ función unir(T L , k, T R ): si T L .blackHeight>T R .blackHeight: T'=joinRightRB(T L ,k,T R ) si (T'.color=rojo) y (T'.right.color=rojo): T'.color=negro devolver T' si T R .blackHeight>T L .blackHeight: /* simétrico */ if (T L .color=black) and (T R .color=black): return Node(T L ,⟨k,red⟩,T R ) return Node(T L ,⟨k,black⟩,T R )

El algoritmo de división es el siguiente:

función split(T, k): si (T = NULL) devolver (NULL, falso, NULL) si (k = T.key) devolver (T.left, verdadero, T.right) si (k < T.key): (L',b,R') = dividir(T.izquierda, k) devolver (L',b,join(R',T.key,T.right)) (L',b,R') = dividir(T.derecha, k) devolver (unir(T.left,T.key,L'),b,R')

La unión de dos árboles rojo-negro t ₁ y t ₂ que representan los conjuntos A y B , es un árbol rojo-negro t que representa A ∪ B. La siguiente función recursiva calcula esta unión:

función unión(t 1 , t 2 ): si t 1 = NULL devolver t 2 si t 2 = NULL devolver t 1 (L 1 ,b,R 1 )=split(t 1 ,t 2 .key) proc1= inicio : T L = unión(L 1 ,t 2 .izquierda) proc2= inicio : T R =union(R 1 ,t 2 .right) wait all proc1,proc2 return join(T L , t 2 .key, T R )

Aquí, se supone que la operación `split` devuelve dos árboles: uno con las claves menores que su clave de entrada y otro con las claves mayores. (El algoritmo no es destructivo , pero también existe una versión destructiva in situ).

El algoritmo para la intersección o la diferencia es similar, pero requiere la rutina auxiliar Join2 , que es igual a Join pero sin la clave central. Basándose en las nuevas funciones de unión, intersección o diferencia, se puede insertar o eliminar una o varias claves del árbol rojo-negro. Dado que Split llama a Join pero no maneja directamente los criterios de balanceo de los árboles rojo-negro, esta implementación se suele denominar implementación "basada en unión" .

La complejidad de cada uno de la unión, la intersección y la diferencia es${\displaystyle O\left(m\log \left({n \over m}+1\right)\right)}$para dos árboles rojos y negros de tamaños${\displaystyle m}$y${\displaystyle n(\geq m)}$Esta complejidad es óptima en términos del número de comparaciones. Más importante aún, dado que las llamadas recursivas a unión, intersección o diferencia son independientes entre sí, pueden ejecutarse en paralelo con una profundidad paralela.${\displaystyle O(\log m\log n)}$. ^{[ 34 ]} Cuando${\displaystyle m=1}$La implementación basada en uniones tiene el mismo grafo acíclico dirigido (DAG) computacional que la inserción y eliminación de un solo elemento si se utiliza la raíz del árbol más grande para dividir el árbol más pequeño.

Los algoritmos paralelos para construir árboles rojo-negro a partir de listas ordenadas de elementos pueden ejecutarse en tiempo constante o${\displaystyle O(\log \log n)}$tiempo, dependiendo del modelo de computadora, si el número de procesadores disponibles es asintóticamente proporcional al número${\displaystyle n}$de artículos donde${\displaystyle n\to \infty }$También se conocen algoritmos paralelos de búsqueda, inserción y eliminación rápidas. ^{[ 35 ]}

Los algoritmos basados ​​en uniones para árboles rojo-negro son paralelos para operaciones masivas, incluyendo unión, intersección, construcción, filtrado, map-reduce, etc.

bulkInsertar (T, I, k): Yo.ordenar() bulklInsertRec(T, I, k) bulkInsertRec (T, I, k): si k = 1: para todo e en I: T.insert(e) de lo contrario m := ⌊tamaño(I) / 2⌋ (T 1 , _, T 2 ) := split(T, I[m]) bulkInsertRec(T 1 , I[0 .. m], ⌈k / 2⌉) || bulkInsertRec(T 2 , I[m + 1 .. size(I) - 1], ⌊k / 2⌋) T ← unir2(T 1 , T 2 )

• Lista de estructuras de datos
• Estructura de datos de árbol
• rotación de árboles
• Árbol estadístico de orden
• Árbol AA , una variación del árbol rojo-negro.
• Árbol rojo-negro de tendencia izquierdista
• Árbol AVL
• Árbol B ( árbol 2–3 , árbol 2–3–4 , árbol B+ , árbol B* , árbol UB )
• Árbol del chivo expiatorio
• Árbol desplegado
• Árbol en T
• Árbol WAVL
• biblioteca GNU

• Mathworld: Árbol rojo-negro
• Universidad Estatal de San Diego: CS 660: Apuntes sobre árboles rojo-negro , por Roger Whitney
• Pfaff, Ben (junio de 2004). "Análisis de rendimiento de BST en software de sistema" (PDF) . Universidad de Stanford .

• Ben Pfaff: Introducción a los árboles de búsqueda binaria y árboles equilibrados. Free Software Foundation, Boston, 2004, ftp.gnu.org (PDF gzip; 1662  kB)
• Una implementación completa y funcional en C
• Conferencia de Erik Demaine sobre árboles rojo-negros en OCW MIT.
• Visualización de inserciones en árboles de búsqueda binaria en YouTube : visualización de inserciones de datos aleatorios y preordenados en árboles de búsqueda binaria elementales y árboles rojo-negro con inclinación hacia la izquierda.
• Un árbol rojo-negro intrusivo escrito en C++.
• Árboles de búsqueda balanceados rojo-negro en 3.3
• Demostración BST rojo-negro