Árbol rojo-negro

Self-balancing binary search tree data structure

En informática , un árbol rojo-negro es una estructura de datos de árbol de búsqueda binaria autoequilibrada que se destaca 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, a menudo representado como 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 "repinta" para restaurar las propiedades de coloración que limitan el desequilibrio que puede presentar el árbol en el peor de los casos. Las propiedades están diseñadas de modo que esta reorganización y recoloración se puedan realizar de manera eficiente.

El (re)equilibrio no es perfecto, pero garantiza la búsqueda en el tiempo, donde 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 el tiempo. ^{[2] [3]} ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle O(\log n)}$

Para rastrear el color de cada nodo se necesita 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 diferir). El árbol no contiene ningún otro dato específico de que sea un árbol rojo-negro, por lo que su huella de memoria es casi idéntica a la de un árbol binario de búsqueda clásico (sin color) . En algunos casos, el bit de información adicional se puede almacenar sin costo adicional de memoria.

Historia

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 binarios de búsqueda. Bayer los llamó "árboles B binarios simétricos" en su artículo y más tarde se hicieron populares como árboles 2-3-4 o incluso árboles 2-3. ^[5]

En un artículo de 1978, "A Dichromatic Framework for Balanced Trees", ^[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 más atractivo 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 rojo y negro disponibles 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 equilibrio solo necesitaba ocuparse de 4 casos desequilibrados y un caso equilibrado predeterminado. ^[11]

El algoritmo original utilizaba 8 casos desequilibrados, pero Cormen et al. (2001) lo redujeron a 6 casos desequilibrados. ^[1] Sedgewick demostró que la operación de inserción se puede implementar en solo 46 líneas de código 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 fueran rojos, haciendo que sus árboles se parecieran más a árboles 2-3-4, pero más tarde se agregó esta restricción, haciendo que los árboles nuevos se parecieran más a á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]}

Terminología

Ejemplo de un árbol rojo-negro

Un árbol rojo-negro es un tipo especial de árbol binario de búsqueda , utilizado en informática para organizar fragmentos de datos comparables , como fragmentos de texto o números (como los números de las figuras 1 y 2). Los nodos que contienen claves o datos se denominan con frecuencia "nodos internos" , pero para que esto sea más específico, en este artículo también se los denomina nodos no NIL.

Los nodos de hoja de los árboles rojo-negros ( NIL en la figura 1) no contienen claves ni datos. Estas "hojas" no necesitan ser individuos explícitos en la memoria de la computadora: un puntero NULL puede, como en todas las estructuras de datos de árboles binarios, codificar el hecho de que no hay ningún nodo hijo en esta posición en el nodo (padre). Sin embargo, por su posición en el árbol, estos objetos están en relación con otros nodos que son relevantes para la estructura RB, pueden tener un nodo padre, hermano (es decir, el otro hijo del padre), tío, incluso sobrino; y pueden ser hijos, pero nunca padres, de otro nodo. En realidad, no es necesario atribuir un "color" a estos objetos de fin de ruta, porque la condición "es o " está implícita en la condición "es " (ver también esta observación).  NILBLACKNIL

La figura 2 muestra el mismo árbol rojo-negro conceptualmente sin estas hojas NIL. Para llegar a la misma noción de ruta , se debe notar que, por ejemplo, 3 rutas pasan por el nodo 1 , es decir, una ruta a través de 1 a la _izquierda más 2 rutas agregadas a través de 1 _{a la derecha} , es decir, las rutas a través de 6 _{a la izquierda} y 6 _{a la derecha} . De esta manera, estos extremos de las rutas también son puntos de acoplamiento para que se inserten nuevos nodos, completamente equivalentes a las hojas NIL de la figura 1.

En lugar de ello, para ahorrar una cantidad marginal de tiempo de ejecución, estas (posiblemente muchas) hojas NIL pueden implementarse como punteros a un nodo centinela único (y negro) (en lugar de punteros de valor NULL ).

Como conclusión, el hecho de que un hijo no exista (no sea un nodo verdadero, no contenga datos) puede especificarse en todas las instancias mediante el mismo puntero NULL o como el mismo puntero a un nodo centinela. En este artículo, cualquiera de las dos opciones se denomina nodo NIL y tiene el valor constante NIL .

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 camino 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 NIL se establecerá en 0, porque su subárbol está vacío como lo sugiere la figura 2, y su altura de árbol también es 0.

Propiedades

Además de los requisitos impuestos a un árbol de búsqueda binario, un árbol rojo-negro debe satisfacer lo siguiente : ^[17]

1. Cada nodo es rojo o negro.
2. Todos los nodos NIL (figura 1) se consideran negros.
3. Un nodo rojo no tiene un hijo rojo.
4. Cada ruta desde un nodo dado a cualquiera de sus nodos NIL descendientes pasa por el mismo número de nodos negros.
5. (Conclusión) Si un nodo N tiene exactamente un hijo, debe ser un hijo rojo, porque si fuera negro, sus descendientes NIL se ubicarían en una profundidad negra diferente que el hijo NIL de N , 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] o Sedgewick y Wayne. ^{[15] : 432–447} Dado que la raíz siempre se puede cambiar 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, cada á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 de un árbol, no afectan a ninguno de los requisitos. Por el contrario, las operaciones de modificación insert y delete 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, llamadaviolación roja , o del requisito 4, llamadaviolación negra .

Los requisitos imponen una propiedad crítica de los árboles rojo-negros: 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 las operaciones como insertar, eliminar y encontrar valores requieren un tiempo en el peor de los casos proporcional a la altura del árbol, este límite superior en la altura permite que los árboles rojo-negros sean eficientes en el peor de los casos, es decir, logarítmicos en el número de entradas, es decir , que no es el caso de los árboles de búsqueda binarios ordinarios . Para una prueba matemática, consulte la sección Prueba de límites. ${\displaystyle h}$ ${\displaystyle n}$ ${\displaystyle h\in O(\log n)}$

Los árboles rojo-negros, como todos los árboles binarios de búsqueda , permiten un acceso secuencial bastante eficiente (por ejemplo, un 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 tiempo de búsqueda. ${\displaystyle O(\log n)}$

Analogía con 2-3-4 árboles

Figura 3: Similitudes entre árboles 2-3-4 y árboles rojo-negros

Los árboles rojo-negros 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 nodo negro – hijos rojos en árboles rojo-negros, como se muestra en la figura 3. No es una correspondencia 1 a 1 , porque los 3 nodos tienen dos representaciones equivalentes: el hijo rojo puede estar a la izquierda o a la derecha. La variante del árbol rojo-negro con inclinación 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-negros es equivalente a decir que las hojas de un árbol 2–3–4 se encuentran todas al mismo nivel.

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

Aplicaciones y estructuras de datos relacionadas

Los árboles rojo-negros 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 los convierte en valiosos bloques de construcción en otras estructuras de datos que brindan garantías en el peor de los casos. Por ejemplo, muchas estructuras de datos utilizadas en geometría computacional se basan en árboles rojo-negros, y el Completely Fair Scheduler y la llamada al sistema epoll del núcleo Linux utilizan árboles rojo-negros. ^{[20] [21]} El árbol AVL es otra estructura que admite la búsqueda, la inserción y la eliminación. Los árboles AVL pueden colorearse de rojo-negro y, por lo tanto, son un subconjunto de los árboles rojo-negros. La altura en el peor de los casos de AVL es 0,720 veces la altura en el peor de los casos de los árboles rojo-negros, por lo que los árboles AVL están equilibrados de manera más rígida. Las mediciones de rendimiento de Ben Pfaff con casos de prueba realistas en 79 ejecuciones encuentran proporciones AVL a RB entre 0,677 y 1,077, una mediana de 0,947 y una media geométrica de 0,910. ^[22] El rendimiento de los árboles WAVL se encuentra entre los árboles AVL y los árboles rojo-negros. ^{[ cita requerida ]} ${\displaystyle O(\log n)}$

Los árboles rojo-negros 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 matrices y conjuntos asociativos que pueden retener versiones anteriores después de mutaciones. La versión persistente de los árboles rojo-negros requiere espacio para cada inserción o eliminación, además de tiempo. ${\displaystyle O(\log n)}$

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 la inversión de color y las rotaciones en árboles rojo–negro. Esto hace que los árboles 2–3–4 sean una herramienta importante para comprender la lógica detrás de los árboles rojo–negros, y es por eso que muchos textos introductorios de algoritmos introducen los árboles 2–3–4 justo antes de los árboles rojo–negros, aunque los árboles 2–3–4 no se usan a menudo 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], eliminando un grado de libertad no especificado previamente en la implementación. El LLRB mantiene una invariante adicional que establece que todos los enlaces rojos deben inclinarse a la izquierda, excepto durante las inserciones y eliminaciones. Los árboles rojo-negros se pueden hacer 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 árboles 2-3-4, la isometría se resuelve mediante un "cambio de color", correspondiente a una división, en la que el color rojo de dos nodos secundarios abandona los nodos secundarios y se mueve al nodo principal.

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

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

Operaciones

Las operaciones de solo lectura, como la búsqueda o el recorrido de un árbol, en un árbol rojo-negro no requieren ninguna modificación con respecto a las utilizadas para los árboles binarios de búsqueda , porque cada árbol rojo-negro es un caso especial de un árbol binario de búsqueda 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-negros se vuelven autoequilibrados.Requiere en el peor de los casos un número pequeño, en notación Big O , donde es el número de objetos en el árbol, en promedio o amortizado , un número constante, ^{[27] : 310  [16] : 158} de cambios de color (que son muy rápidos en la práctica); y no más de tres rotaciones de árbol ^[28] (dos para inserción). ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle O(1)}$

Si la implementación de ejemplo a continuación no es adecuada, se pueden encontrar otras implementaciones con explicaciones en la biblioteca C anotada GNU libavl (v2.0.3 a junio de 2019) de Ben Pfaff ^{[29] .}

Los detalles de las operaciones de inserción y eliminación se demostrarán con un código C++ de ejemplo , que utiliza las definiciones de tipo, las macros a continuación y la función auxiliar para rotaciones:

// Definiciones de tipos básicos:enumeración color_t { NEGRO , ROJO };     struct RBnode { // nodo del árbol rojo-negro RBnode * padre ; // == NIL si es la raíz del árbol RBnode * hijo [ 2 ]; // == NIL si el hijo está vacío // El índice es: // IZQUIERDA := 0, si (clave < padre->clave) // DERECHA := 1, si (clave > padre->clave) enum color_t color ; int clave ; };                 #define NIL NULL // puntero nulo o puntero a nodo centinela #define IZQUIERDA 0 #define DERECHA 1 #define hijo izquierdo[IZQUIERDA] #define hijo derecho[DERECHA]struct RBtree { // árbol rojo-negro RBnode * root ; // == NIL si el árbol está vacío };      // Obtener la dirección del hijo (∈ { IZQUIERDA, DERECHA }) // del RBnode no raíz no NIL* N: #define childDir(N) ( N == (N->parent)->right ? RIGHT : LEFT )

Rotación a la izquierda y
rotación a la derecha, animadas.

RBnode * RotateDirRoot ( RBtree * T , // árbol rojo-negro RBnode * P , // raíz del subárbol ( puede ser la raíz de T ) int dir ) { // dir ∈ { IZQUIERDA, DERECHA } RBnode * G = P -> padre ; RBnode * S = P -> hijo [ 1 - dir ]; RBnode * C ; assert ( S != NIL ); // puntero al nodo verdadero requerido C = S -> hijo [ dir ]; P -> hijo [ 1 - dir ] = C ; if ( C != NIL ) C -> padre = P ; S -> hijo [ dir ] = P ; P -> padre = S ; S -> padre = G ; if ( G != NULL ) G -> hijo [ P == G -> derecha ? DERECHA : IZQUIERDA ] = S ; else T -> raíz = S ; return S ; // nueva raíz del subárbol }                                                                               #define RotarDir(N,dir) RotarDirRaiz(T,N,dir) #define RotarIzquierda(N) RotarDirRaiz(T,N, IZQUIERDA) #define RotarDerecha(N) RotarDirRaiz(T,N,DERECHA)

Notas sobre el código de muestra y diagramas de inserción y extracción

La propuesta descompone tanto la inserción como la eliminación (sin mencionar algunos casos muy simples) en seis constelaciones de nodos, aristas y colores, que se denominan casos. La propuesta contiene, tanto para la inserción como para la eliminación, exactamente un caso que avanza un nivel negro más cerca de la raíz y hace bucles, mientras que los otros cinco casos reequilibran el árbol por sí solos. Los casos más complicados se representan en un diagrama.

• simboliza un nodo rojo yun nodo negro (no NIL) (de altura negra ≥ 1),Simboliza el color rojo o negro de un nodo que no es NIL, pero el mismo color en todo el diagrama. Los nodos NIL no están representados en los diagramas.
• La variable N denota el nodo actual, que está etiquetado como N o N en los diagramas.    
• Un diagrama contiene tres columnas y de dos a cuatro acciones. La columna de la izquierda muestra la primera iteración, la columna de la derecha las iteraciones superiores y la columna del medio muestra la segmentación de un caso en sus diferentes acciones. ^[30]

1. La acción "entrada" muestra la constelación de nodos con sus colores, lo que define un caso y, en la mayoría de los casos, viola algunos de los requisitos. Un
   borde azul rodea el nodo actual N y los demás nodos están etiquetados según su relación con N.
2. Si una rotación se considera útil, esto se ilustra en la siguiente acción, que se denomina "rotación".
3. Si se considera útil cambiar el color, esto se ilustra en la siguiente acción, que se denomina "colorear". ^[31]
4. Si todavía hay alguna necesidad de reparación, los casos hacen uso del código de otros casos y esto después de una reasignación del nodo actual N , que luego nuevamente lleva un anillo azul y en relación con el cual otros nodos también pueden tener que ser reasignados. Esta acción se denomina "reasignar".
   Para ambos, insertar y eliminar, hay (exactamente) un caso que itera un nivel negro más cerca de la raíz; luego, la constelación reasignada satisface el invariante de bucle respectivo.

• Un triángulo posiblemente numerado con un círculo negro encimarepresenta un subárbol rojo-negro (conectado a su padre según el requisito 3) con una altura negra igual al nivel de iteración menos uno, es decir, cero en la primera iteración. Su raíz puede ser roja o negra.
  Un triángulo posiblemente numeradorepresenta un subárbol rojo-negro con una altura negra menos, es decir, su padre tiene una altura negra cero en la segunda iteración.

Observación

Para simplificar, el código de muestra utiliza la disyunción :

U == NIL || U->color == BLACK // considered black

y la conjunción :

U != NIL && U->color == RED   // not considered black

Por lo tanto, debe tenerse en cuenta que ambas afirmaciones no se evalúan en su totalidad, si U == NIL. Entonces, en ambos casos U->colorno se toca (véase Evaluación de cortocircuito ).
(El comentario considered blackestá de acuerdo con el requisito 2).

Las declaraciones relacionadas ifdeben ocurrir con mucha menos frecuencia si la propuesta ^[30] se realiza.

Inserción

La inserción comienza colocando el nuevo nodo (no NIL), digamos N , en la posición en el árbol binario de búsqueda de un nodo NIL cuya clave de predecesor en orden se compara menos que la clave del nuevo nodo, que a su vez se compara menos 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 consta de un nodo Pjunto con una dirección dircon P->child[dir] == NIL). El nodo recién insertado se colorea temporalmente de rojo para que todas las rutas contengan la misma cantidad de nodos negros que antes. Pero si su padre, digamos P , también es rojo, entonces esta acción introduce una violación roja.

void RBinsert1 ( RBtree * T , // -> árbol rojo-negro struct RBnode * N , // -> nodo a insertar struct RBnode * P , // -> nodo padre de N (puede ser NULL) int dir ) // lado (IZQUIERDO o DERECHO) de P donde insertar N { struct RBnode * G ; // -> nodo padre de P struct RBnode * U ; // -> tío de N                        N -> color = ROJO ; N -> izquierda = NIL ; N -> derecha = NIL ; N -> padre = P ; if ( P == NULL ) { // No hay padre T -> raíz = N ; // N es la nueva raíz del árbol T. return ; // inserción completa } P -> hijo [ dir ] = N ; // inserta N como dir-hijo de P // inicio del bucle (do while): do {                               

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

• La variable N , que representa el nodo actual N e inicialmente el nodo de inserción, se convierte en la variable que recorre el bucle.
• N es(rojo) al comienzo de cada iteración.
• El requisito 3 se satisface para todos los pares nodo←padre con la posible excepción N ← P cuando P también es rojo (una violación de rojo en N ).
• Todas las demás propiedades (incluido el requisito 4) se cumplen en todo el árbol.

Notas para los diagramas de inserción

• En los diagramas, P se utiliza para el padre de N , G para su abuelo y U para su tío. En la tabla, un signo — indica raíz.
• Los diagramas muestran el nodo padre P como el hijo izquierdo de su padre G, aunque es posible que P esté en cualquiera de los lados. El código de muestra cubre ambas posibilidades mediante la variable lateral dir.
• Los diagramas también muestran los casos en los que P es rojo, la violación del rojo.
• La columna x indica el cambio en la dirección del niño, es decir, o (para "externo") significa que P y N son ambos hijos izquierdos o derechos, mientras que i (para "interno") significa que la dirección del niño cambia de P a N.
• El grupo de columnas anterior define el caso, cuyo nombre se proporciona en la columna case . Por lo tanto, se ignoran los posibles valores en las celdas que se dejan vacías. Por lo tanto, en el caso I2, el código de ejemplo cubre ambas posibilidades de direcciones secundarias de N , aunque el diagrama correspondiente muestra solo una.
• Las filas de la sinopsis están ordenadas de tal manera que la cobertura de todos los posibles casos 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 ingresar a un paso posterior. Esto posiblemente induce una reasignación también de los otros nodos P , G , U.
• Si se ha modificado algo en el caso, esto se muestra en el grupo de columnas después de .
• El signo ✓ en la columna siguiente significa que el reequilibrio se ha completado con este paso. Si la columna siguiente determina exactamente un caso, este caso se indica como el siguiente; de ​​lo contrario, aparecen signos de interrogación.
• El bucle está contenido en las secciones "Insertar caso I1" e "Insertar caso I2", donde en el caso I2 el problema de reequilibrio se escala a 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, se necesitan el máximo de pasos de iteración para reparar el árbol (donde 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, se amortiza constante. ${\displaystyle \Delta h=2}$ ${\displaystyle {\tfrac {h}{2}}}$ ${\displaystyle h}$
• Desde el cuerpo del bucle, el caso I1 sale por sí solo y hay ramas de salida hacia los casos I4, I6, I5 + I6 e I3.
• Las rotaciones se producen en los casos I6 y I5 + I6 – fuera del bucle. Por lo tanto, se producen como máximo dos rotaciones en total.

Insertar caso I1

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

 if ( P -> color == BLACK ) { // Case_I1 (P black): return ; // inserción completa } // De ahora en adelante P es rojo. if (( G = P -> parent ) == NULL ) goto Case_I4 ; // P rojo y raíz // else: P rojo y G!=NULL. dir = childDir ( P ); // el lado del padre G en el que se encuentra el nodo P U = G -> child [ 1 - dir ]; // tío if ( U == NIL || U -> color == BLACK ) // considerado negro goto Case_I56 ; // P rojo && U negro                                        

Insertar caso I2

Insertar caso I2

Si tanto el padre P como el tío U son rojos, entonces ambos pueden ser repintados de negro y el abuelo G se vuelve rojo para mantener el requisito 4. Dado que cualquier camino a través del padre o tío debe pasar por el abuelo, la cantidad de nodos negros en estos caminos 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 de bucle para que el reequilibrio se pueda iterar en un nivel negro (= 2 niveles de árbol) superior.

 // Caso_I2 (P+U rojo): P -> color = NEGRO ; U -> color = NEGRO ; G -> color = ROJO ; N = G ; // nuevo nodo actual // iterar 1 nivel negro más arriba // (= 2 niveles de árbol) } while (( P = N -> padre ) != NULL ); // fin del bucle (do while)                       

Insertar caso I3

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

 // Saliendo del bucle (do while) (después de haber pasado por Case_I2). // Case_I3: N es la raíz y rojo. return ; // inserción completa   

Insertar caso I4

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

Caso_I4 : // P es la raíz y rojo: P -> color = BLACK ; return ; // inserción completa      

Insertar caso I5

Insertar caso I5

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 (aquellos en el subárbol etiquetado 2 , vea el diagrama) y elimina caminos a través de P (aquellos en el subárbol etiquetado 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.

Caso_I56 : // P rojo && U negro: if ( N == P -> child [ 1 - dir ]) { // Caso_I5 (P rojo && U negro && N nieto interno de G): RotateDir ( P , dir ); // P nunca es la raíz N = P ; // nuevo nodo actual P = G -> child [ dir ]; // nuevo padre de N // pasar a Caso_I6 }                   

Insertar caso I6

Insertar caso I6

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

 // Caso_I6 (P rojo && U negro && N nieto externo de G): RotateDirRoot ( T , G , 1 - dir ); // G puede ser la raíz P -> color = NEGRO ; G -> color = ROJO ; return ; // inserción completa } // fin de RBinsert1           

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, se encuentra en el lugar .

Eliminación

Casos sencillos

- Cuando el nodo eliminado tiene 2 hijos (no NIL), podemos intercambiar su valor con su sucesor en orden (el hijo más a la izquierda del subárbol derecho) y luego eliminar el sucesor en su lugar. Dado que el sucesor está más a la izquierda, solo puede tener un hijo derecho (no NIL) o ningún hijo en absoluto.

- Cuando el nodo eliminado tiene solo un hijo (no NIL). En este caso, simplemente reemplace el nodo con su hijo y coloréelo de negro.
El único hijo (no NIL) 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 NIL) y es la raíz, reemplácelo por NIL. El árbol queda vacío.

- Cuando el nodo eliminado no tiene hijos (ambos NIL) y está en rojo , simplemente elimine el nodo hoja.

- Cuando el nodo eliminado no tiene hijos (ambos NIL) y es negro , eliminarlo creará un desequilibrio y requerirá una reparación, como se explica en la siguiente sección.

Eliminación de una hoja negra sin raíz

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

void RBdelete2 ( RBtree * T , // -> árbol rojo-negro struct RBnode * N ) // -> nodo que se eliminará { struct RBnode * P = N -> parent ; // -> nodo padre de N byte dir ; // lado de P en el que se encuentra N (∈ {LEFT, RIGHT}) struct RBnode * S ; // -> hermano de N struct RBnode * C ; // -> sobrino cercano struct RBnode * D ; // -> sobrino lejano                               // P != NULL, ya que N no es la raíz. dir = childDir ( N ​​); // lado del padre P en el que se encuentra el nodo N // Reemplazar N en su padre P por NIL: P -> child [ dir ] = NIL ; goto Start_D ; // saltar al bucle            // inicio del bucle (do while): do { dir = childDir ( N ​​); // lado del padre P en el que se encuentra el nodo N Start_D : S = P -> child [ 1 - dir ]; // hermano de N (tiene altura negra >= 1) D = S -> child [ 1 - dir ]; // sobrino lejano C = S -> child [ dir ]; // sobrino cercano if ( S -> color == RED ) goto Case_D3 ; // S rojo ===> P+C+D negro // S es negro: if ( D != NIL && D -> color == RED ) // no se considera negro goto Case_D6 ; // D rojo && S negro if ( C != NIL && C -> color == RED ) // no se considera negro goto Case_D5 ; // C rojo && S+D negro // Aquí ambos sobrinos son == NIL (primera iteración) o negros (posteriormente). si ( P -> color == ROJO ) ir a Caso_D4 ; // P rojo && C+S+D negro                                                           

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 superiores.
• El número de nodos negros en los caminos que pasan por N es uno menos que antes de la eliminación, mientras que no cambia en todos los demás caminos, de modo que hay una violación negra en P si existen otros caminos.
• Todas las demás propiedades (incluido el requisito 3) se satisfacen en todo el árbol.

Notas para los diagramas de eliminación

• En los diagramas siguientes, P se utiliza 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 NIL 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 NIL).
• Los diagramas muestran el nodo actual N como el hijo izquierdo de su padre P, aunque es posible que N esté en cualquiera de los lados. Los ejemplos de código cubren ambas posibilidades mediante la variable lateral dir.
• Al comienzo (en la primera iteración) de la eliminación, N es el nodo NIL 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(es decir: el nodo actual N es un nodo NIL y un hijo izquierdo) en la columna izquierda de los diagramas de eliminación. A medida que avanza la operación, también los nodos propios (de altura negra ≥ 1) pueden volverse actuales (ver, por ejemplo, el caso D2).
• Contando las balas negras (y) en un diagrama de borrado se puede observar que los caminos a través de N tienen una bala menos que los otros caminos. Esto significa una violación de la línea negra en P , si es que existe.
• La constelación de colores del grupo de columnas anterior define el caso, cuyo nombre se indica en la columna caso . 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 posibles casos 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 ingresar a un paso de iteración posterior. Esto posiblemente induce también una reasignación de los otros nodos P , C , S y D.
• Si se ha modificado algo en el caso, esto se muestra en el grupo de columnas después de .
• El signo ✓ en la columna siguiente significa que el reequilibrio se ha completado con este paso. Si la columna siguiente determina exactamente un caso, este caso se indica como el siguiente; de ​​lo contrario, aparecen signos de interrogación.
• El bucle está contenido en las secciones desde Start_Dhasta "Eliminar caso D2", donde el problema de reequilibrio se escala a un nivel superior en el árbol en el que el padre P se convierte en el nuevo nodo actual N. Por lo tanto, se necesitan el máximo de iteraciones para reparar el árbol (donde 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. (Solo como un aparte: 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. ^[33] ) ${\displaystyle \Delta h=1}$ ${\displaystyle h}$ ${\displaystyle h}$
• Fuera del cuerpo del bucle hay ramas de salida a los casos D3, D6, D5 + D6, D4 y D1; la sección "Eliminar caso D3" tiene tres ramas de salida diferentes a los casos D6 , D5 y D4 .
• Las rotaciones se producen en los casos D6 y D5 + D6 y D3 + D5 + D6 , todos fuera del bucle. Por lo tanto, se producen como máximo tres rotaciones en total.

Eliminar caso D1

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 de RB. La altura negra del árbol disminuye en 1.

 // Caso_D1 (P == NULL): return ; // eliminación completa  

Eliminar caso D2

→ Explicación de los símbolos

Eliminar caso D2

Los hijos de P , S y 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 todavía puede violarse. Después de reetiquetar P a N , se cumple el invariante de bucle de modo que el reequilibrio se puede iterar en un nivel negro (= 1 nivel de árbol) superior.

 // Caso_D2 (P+C+S+D negro): S -> color = ROJO ; N = P ; // nuevo nodo actual (quizás la raíz) // iterar 1 nivel de negro // (= 1 nivel de árbol) más alto } while (( P = N -> padre ) != NULL ); // fin del bucle (do while) // (con retorno;)                  

Eliminar caso D3

Eliminar caso D3

El hermano S es rojo, por lo que P y los sobrinos C y D tienen que ser negros. Una dirrotación en P convierte a S en el abuelo de N. Luego, después de invertir los colores de P y S , el camino a través de N todavía es corto por un nodo negro. Pero N ahora tiene un padre rojo P y después de la reasignación un hermano negro S , por lo que las transformaciones en los casos D4, D5 o D6 pueden restaurar la forma RB.

Case_D3 : // S rojo && P+C+D negro: RotateDirRoot ( T , P , dir ); // P puede ser la raíz P -> color = ROJO ; S -> color = NEGRO ; S = C ; // != NIL // ahora: P rojo && S negro D = S -> hijo [ 1 - dir ]; // sobrino lejano if ( D != NIL && D -> color == ROJO ) goto Case_D6 ; // D rojo && S negro C = S -> hijo [ dir ]; // sobrino cercano if ( C != NIL && C -> color == ROJO ) goto Case_D5 ; // C rojo && S+D negro // De lo contrario, C+D se considera negro. // pasa a Case_D4                                               

Eliminar caso D4

Eliminar caso D4

Los hijos de los hermanos S y S son negros, pero P es rojo. Intercambiar los colores de S y P no afecta la cantidad de nodos negros en las rutas que pasan por S , pero sí suma uno a la cantidad de nodos negros en las rutas que pasan por N , lo que compensa el nodo negro eliminado en esas rutas.

Case_D4 : // P rojo && S+C+D negro: S -> color = ROJO ; P -> color = NEGRO ; return ; // eliminación completa         

Eliminar caso D5

Eliminar caso D5

El hermano S es negro, el hijo cercano C de S es rojo y el hijo lejano D de S es negro. Después de una rotación en S, el sobrino C se convierte en el padre de S y el nuevo hermano de N. Los colores de S y C se intercambian. Todos los caminos todavía tienen 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 apta para el caso D6. Ni N ni su padre P se ven afectados por esta transformación, y P puede ser rojo o negro ((1-dir)en el diagrama).

Case_D5 : // C rojo && S+D negro: RotateDir ( S , 1 - dir ); // S nunca es la raíz S -> color = ROJO ; C -> color = NEGRO ; D = S ; S = C ; // ahora: D rojo && S negro // pasan a Case_D6                 

Eliminar caso D6

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 el hijo lejano de S , D. Los colores de P y S se intercambian y D se vuelve negro. Todo el subárbol todavía tiene el mismo color en su raíz S , es decir, rojo o negro.en el diagrama), 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 la misma cantidad 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 de RB.

Case_D6 : // D rojo y S negro: RotateDirRoot ( T , P , dir ); // P puede ser la raíz S -> color = P -> color ; P -> color = NEGRO ; D -> color = NEGRO ; return ; // eliminación completa } // fin de RBdelete2               

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, se encuentra en el lugar .

Prueba de límites

Figura 4: Árboles rojo-negros RB _h de alturas h = 1, 2, 3, 4, 5,
cada uno con un número mínimo de nodos 1, 2, 4, 6 o 10.

Porque hay un árbol rojo-negro de altura con ${\displaystyle h\in \mathbb {N} }$ ${\displaystyle h}$

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

Prueba

Para que un árbol rojo-negro de una 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 de árbol máxima con una altura negra mínima. Además de este camino, todos los demás nodos deben ser negros. ^{[15] : 444 Boceto de prueba} Si se quita un nodo de este árbol, pierde altura o alguna propiedad RB.

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

${\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 4) de altura tiene una raíz cuyos dos subárboles hijos tienen diferentes alturas. El subárbol hijo superior también es un árbol RB mínimo, RB _{h –1} , que contiene también un camino más largo que define su altura ; tiene nodos y la altura negra El otro subárbol es un árbol binario perfecto de altura (negra) que tiene nodos negros y ningún nodo rojo. Entonces, el número de nodos es por inducción ${\displaystyle h>1}$ ${\displaystyle h\!\!-\!\!1}$ ${\displaystyle m_{h-1}}$ ${\displaystyle \lfloor (h\!\!-\!\!1)/2\rfloor =:s.}$ ${\displaystyle s}$ ${\displaystyle 2^{s}\!\!-\!\!1=2^{\lfloor (h-1)/2\rfloor }\!\!-\!\!1}$

La gráfica de la función es convexa y lineal por partes con puntos de corte en donde La función ha sido tabulada como A027383( h –1) para (secuencia A027383 en la OEIS ). ${\displaystyle m_{h}}$ ${\displaystyle (h=2k\;|\;m_{2k}=2\cdot 2^{k}\!-\!2)}$ ${\displaystyle k\in \mathbb {N} .}$ ${\displaystyle m_{h}=}$ ${\displaystyle h\geq 1}$

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

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

${\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, el par y el impar, está en el intervalo ${\displaystyle h}$

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

Conclusión

Un árbol rojo-negro con nodos (claves) tiene una altura de árbol ${\displaystyle n}$ ${\displaystyle h\in O(\log n).}$

Operaciones de conjunto y operaciones en masa

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

• Join : La función Join se basa en dos árboles rojo-negros t ₁ y t ₂ y 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 ₁ , t ₂ también como k .

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

Si las alturas negras son desiguales, supongamos que t ₁ tiene una altura negra mayor que t ₂ (el otro caso es simétrico). La unión 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 el hijo izquierdo c , la raíz k (establecida como roja) y el hijo derecho t ₂ para reemplazar a c. El nuevo nodo puede invalidar el invariante rojo-negro porque, como máximo, pueden aparecer tres nodos rojos seguidos. Esto se puede solucionar con una doble rotación. Si el problema del doble rojo se propaga a la raíz, la raíz se establece como negra, lo que restaura las propiedades. El costo de esta función es la diferencia de las alturas negras entre los dos árboles de entrada.

• Split : Para dividir un árbol rojo-negro en dos árboles más pequeños, aquellos más pequeños que la clave x y aquellos más grandes que la clave x , primero dibuje una ruta desde la raíz insertando x en el árbol rojo-negro. Después de esta inserción, todos los valores menores que x se encontrarán a la izquierda de la ruta, y todos los valores mayores que x se encontrarán a la derecha. Al aplicar Join , todos los subárboles del lado izquierdo se fusionan de abajo hacia arriba usando claves en la ruta como nodos intermedios de abajo hacia arriba para formar el árbol izquierdo, y 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 el 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 se puede utilizar en cualquier árbol con una operación de unión , como un árbol AVL . ${\displaystyle O(\log n),}$

El algoritmo de unión es el siguiente:

función joinRightRB(T L , k, T R ): si (T L .color=negro) y (T L .blackHeight=T R .blackHeight): devuelve Nodo(T L ,⟨k,rojo⟩,T R ) T'=Nodo(T L .izquierda,⟨T L .clave,T L .color⟩,unirseDerechaRB(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; devolver rotarIzquierda(T') devolver T' /* T ' '[T recta'] */función joinLeftRB(T L , k, T R ): /* simétrico para unirse a RightRB */función join(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 devuelve T' si T R .blackHeight>T L .blackHeight: /* simétrico */ si (T L .color=negro) y (T R .color=negro): devuelve Nodo(T L ,⟨k,rojo⟩,T R ) devuelve Nodo(T L ,⟨k,negro⟩,T R )

El algoritmo de división es el siguiente:

función split(T, k): si (T = nulo) devuelve (nulo, falso, nulo) si (k = T.clave) devuelve (T.izquierda, verdadero, T.derecha) si (k < T.clave): (L',b,R') = dividir(T.izquierda, k) devolver (L',b,unir(R',T.tecla,T.derecha)) (L',b,R') = dividir(T.derecha, k) regresar (unir(T.izquierda,T.tecla,L'),b,T.derecha)

La unión de dos árboles rojo-negros 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 = nulo devuelve t 2  si t 2 = nulo devuelve 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 = unión(R 1 ,t 2 .derecha) esperar todo proc1,proc2 devolver unión(T L , t 2 .clave, T R )

Aquí, se supone que split devuelve dos árboles: uno que contiene las claves menos su clave de entrada, y otro que contiene las claves mayores. (El algoritmo no es destructivo , pero también existe una versión destructiva en el lugar).

El algoritmo para la intersección o diferencia es similar, pero requiere la rutina auxiliar Join2 que es la misma que Join pero sin la clave intermedia. Con base en las nuevas funciones para la unión, intersección o diferencia, se puede insertar o eliminar una o varias claves en el árbol rojo-negro. Dado que Split llama a Join pero no se ocupa directamente de los criterios de equilibrio de los árboles rojo-negros, una implementación de este tipo se suele denominar implementación "basada en unión" .

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

Algoritmos paralelos

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

Los algoritmos basados ​​en unión para árboles rojo-negros son paralelos para operaciones en masa, incluidas unión, intersección, construcción, filtro, mapa-reducción, etc.

Operaciones masivas paralelas

Las operaciones básicas como inserción, eliminación o actualización se pueden paralelizar definiendo operaciones que procesen lotes de múltiples elementos. También es posible procesar lotes con varias operaciones básicas; por ejemplo, los lotes pueden contener elementos para insertar y también elementos para eliminar del árbol.

The algorithms for bulk operations aren't just applicable to the red–black tree, but can be adapted to other sorted sequence data structures also, like the 2–3 tree, 2–3–4 tree and (a,b)-tree. In the following different algorithms for bulk insert will be explained, but the same algorithms can also be applied to removal and update. Bulk insert is an operation that inserts each element of a sequence ${\displaystyle I}$ into a tree ${\displaystyle T}$.

Join-based

This approach can be applied to every sorted sequence data structure that supports efficient join- and split-operations.^[37]The general idea is to split ${\displaystyle I}$ and ${\displaystyle T}$ in multiple parts and perform the insertions on these parts in parallel.

1. First the bulk ${\displaystyle I}$ of elements to insert must be sorted.
2. After that, the algorithm splits ${\displaystyle I}$ into ${\displaystyle k\in \mathbb {N} ^{+}}$ parts ${\displaystyle \langle I_{1},\cdots ,I_{k}\rangle }$ of about equal sizes.
3. Next the tree ${\displaystyle T}$ must be split into ${\displaystyle k}$ parts ${\displaystyle \langle T_{1},\cdots ,T_{k}\rangle }$ in a way, so that for every ${\displaystyle j\in \mathbb {N} ^{+}|\,1\leq j<k}$ following constraints hold:
   1. ${\displaystyle {\text{last}}(I_{j})<{\text{first}}(T_{j+1})}$
   2. ${\displaystyle {\text{last}}(T_{j})<{\text{first}}(I_{j+1})}$
4. Now the algorithm inserts each element of ${\displaystyle I_{j}}$ into ${\displaystyle T_{j}}$ sequentially. This step must be performed for every ${\displaystyle j}$, which can be done by up to ${\displaystyle k}$ processors in parallel.
5. Finally, the resulting trees will be joined to form the final result of the entire operation.

Note that in Step 3 the constraints for splitting ${\displaystyle I}$ assure that in Step 5 the trees can be joined again and the resulting sequence is sorted.

• 
  initial tree
• 
  split I and T
• 
  insert into the split T
• 
  join T

The pseudo code shows a simple divide-and-conquer implementation of the join-based algorithm for bulk-insert. Both recursive calls can be executed in parallel. The join operation used here differs from the version explained in this article, instead join2 is used, which misses the second parameter k.

bulkInsert(T, I, k): I.sort() bulklInsertRec(T, I, k)bulkInsertRec(T, I, k): if k = 1: forall e in I: T.insert(e) else m := ⌊size(I) / 2⌋ (T1, _, T2) := split(T, I[m]) bulkInsertRec(T1, I[0 .. m], ⌈k / 2⌉) || bulkInsertRec(T2, I[m + 1 .. size(I) - 1], ⌊k / 2⌋) T ← join2(T1, T2)

Execution time

Sorting ${\displaystyle I}$ is not considered in this analysis.

This can be improved by using parallel algorithms for splitting and joining. In this case the execution time is ${\displaystyle \in O\left(\log |T|+{\frac {|I|}{k}}\log |T|\right)}$.^[38]

Work

Pipelining

Another method of parallelizing bulk operations is to use a pipelining approach.^[39]This can be done by breaking the task of processing a basic operation up into a sequence of subtasks. For multiple basic operations the subtasks can be processed in parallel by assigning each subtask to a separate processor.

1. First the bulk ${\displaystyle I}$ of elements to insert must be sorted.
2. For each element in ${\displaystyle I}$ the algorithm locates the according insertion position in ${\displaystyle T}$. This can be done in parallel for each element ${\displaystyle \in I}$ since ${\displaystyle T}$ won't be mutated in this process. Now ${\displaystyle I}$ must be divided into subsequences ${\displaystyle S}$ according to the insertion position of each element. For example ${\displaystyle s_{n,{\mathit {left}}}}$ is the subsequence of ${\displaystyle I}$ that contains the elements whose insertion position would be to the left of node ${\displaystyle n}$.
3. The middle element ${\displaystyle m_{n,{\mathit {dir}}}}$ of every subsequence ${\displaystyle s_{n,{\mathit {dir}}}}$ will be inserted into ${\displaystyle T}$ as a new node ${\displaystyle n'}$. This can be done in parallel for each ${\displaystyle m_{n,{\mathit {dir}}}}$ since by definition the insertion position of each ${\displaystyle m_{n,{\mathit {dir}}}}$ is unique. If ${\displaystyle s_{n,{\mathit {dir}}}}$ contains elements to the left or to the right of ${\displaystyle m_{n,{\mathit {dir}}}}$, those will be contained in a new set of subsequences ${\displaystyle S}$ as ${\displaystyle s_{n',{\mathit {left}}}}$ or ${\displaystyle s_{n',{\mathit {right}}}}$.
4. Now ${\displaystyle T}$ possibly contains up to two consecutive red nodes at the end of the paths form the root to the leaves, which needs to be repaired. Note that, while repairing, the insertion position of elements ${\displaystyle \in S}$ have to be updated, if the corresponding nodes are affected by rotations.
   If two nodes have different nearest black ancestors, they can be repaired in parallel. Since at most four nodes can have the same nearest black ancestor, the nodes at the lowest level can be repaired in a constant number of parallel steps.
   This step will be applied successively to the black levels above until ${\displaystyle T}$ is fully repaired.
5. The steps 3 to 5 will be repeated on the new subsequences until ${\displaystyle S}$ is empty. At this point every element ${\displaystyle \in I}$ has been inserted. Each application of these steps is called a stage. Since the length of the subsequences in ${\displaystyle S}$ is ${\displaystyle \in O(|I|)}$ and in every stage the subsequences are being cut in half, the number of stages is ${\displaystyle \in O(\log |I|)}$.
   Since all stages move up the black levels of the tree, they can be parallelised in a pipeline. Once a stage has finished processing one black level, the next stage is able to move up and continue at that level.

• 
  Initial tree
• 
  Find insert positions
• 
  Stage 1 inserts elements
• 
  Stage 1 begins to repair nodes
• 
  Stage 2 inserts elements
• 
  Stage 2 begins to repair nodes
• 
  Stage 3 inserts elements
• 
  Stage 3 begins to repair nodes
• 
  Stage 3 continues to repair nodes

Execution time

Sorting ${\displaystyle I}$ is not considered in this analysis. Also, ${\displaystyle |I|}$ is assumed to be smaller than ${\displaystyle |T|}$, otherwise it would be more efficient to construct the resulting tree from scratch.

Work

See also

• List of data structures
• Tree data structure
• Tree rotation
• Order statistic tree
• AA tree, a variation of the red–black tree
• Left-leaning red–black tree
• AVL tree
• B-tree (2–3 tree, 2–3–4 tree, B+ tree, B*-tree, UB-tree)
• Scapegoat tree
• Splay tree
• T-tree
• WAVL tree

References and notes

1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Red–Black Trees". Introduction to Algorithms (2nd ed.). MIT Press. pp. 273–301. ISBN 978-0-262-03293-3.
2. Paton, James. "Red–Black Trees".
3. Morris, John (1998). "Red–Black Trees". Data Structures and Algorithms.
4. Bayer, Rudolf (1972). "Symmetric binary B-Trees: Data structure and maintenance algorithms". Acta Informatica. 1 (4): 290–306. doi:10.1007/BF00289509. S2CID 28836825.
5. Drozdek, Adam (2001). Data Structures and Algorithms in Java (2 ed.). Sams Publishing. p. 323. ISBN 978-0534376680.
6. Guibas, Leonidas J.; Sedgewick, Robert (1978). "A Dichromatic Framework for Balanced Trees". Proceedings of the 19th Annual Symposium on Foundations of Computer Science. pp. 8–21. doi:10.1109/SFCS.1978.3.
7. "Red Black Trees". eternallyconfuzzled.com. Archived from the original on 2007-09-27. Retrieved 2015-09-02.
8. Sedgewick, Robert (2012). Red–Black BSTs. Coursera. A lot of people ask why did we use the name red–black. Well, we invented this data structure, this way of looking at balanced trees, at Xerox PARC that was the home of the personal computer and many other innovations that we live with today entering[sic] graphic user interfaces, Ethernet and object-oriented programmings[sic] and many other things. But one of the things that was invented there was laser printing and we were very excited to have nearby color laser printer that could print things out in color and out of the colors the red looked the best. So, that's why we picked the color red to distinguish red links, the types of links, in three nodes. So, that's an answer to the question for people that have been asking.
9. "Where does the term "Red/Black Tree" come from?". programmers.stackexchange.com. Retrieved 2015-09-02.
10. Andersson, Arne (1993-08-11). "Balanced search trees made simple". In Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue (eds.). Algorithms and Data Structures (Proceedings). Lecture Notes in Computer Science. Vol. 709. Springer-Verlag Berlin Heidelberg. pp. 60–71. CiteSeerX 10.1.1.118.6192. doi:10.1007/3-540-57155-8_236. ISBN 978-3-540-57155-1. Archived from the original on 2018-12-08. Alt URL
11. Okasaki, Chris (1999-01-01). "Red–black trees in a functional setting". Journal of Functional Programming. 9 (4): 471–477. doi:10.1017/S0956796899003494. ISSN 1469-7653. S2CID 20298262.
12. Sedgewick, Robert (1983). Algorithms (1st ed.). Addison-Wesley. ISBN 978-0-201-06672-2.
13. Sedgewick, Robert; Wayne, Kevin. "RedBlackBST.java". algs4.cs.princeton.edu. Retrieved 7 April 2018.
14. Sedgewick, Robert (2008). "Left-leaning Red–Black Trees" (PDF).
15. Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th ed.). Addison-Wesley Professional. ISBN 978-0-321-57351-3.
16. Mehlhorn, Kurt; Sanders, Peter (2008). "7. Sorted Sequences" (PDF). Algorithms and Data Structures: The Basic Toolbox. Berlin/Heidelberg: Springer. CiteSeerX 10.1.1.148.2305. doi:10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.
17. Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2022). "13. Red–Black Trees". Introduction to Algorithms (4th ed.). MIT Press. pp. 331–332. ISBN 9780262046305.
18. Using Knuth’s definition of order: the maximum number of children
19. Sedgewick, Robert (1998). Algorithms in C++. Addison-Wesley Professional. pp. 565–575. ISBN 978-0-201-35088-3.
20. "IBM Developer". developer.ibm.com. Retrieved 25 May 2024.
21. "The Implementation of epoll (1)". September 2014.
22. Pfaff 2004
23. "Robert Sedgewick" (PDF). Cs.princeton.edu. 4 June 2020. Retrieved 26 March 2022.
24. "Balanced Trees" (PDF). Cs.princeton.edu. Retrieved 26 March 2022.
25. Demaine, E. D.; Harmon, D.; Iacono, J.; Pătraşcu, M. (2007). "Dynamic Optimality—Almost" (PDF). SIAM Journal on Computing. 37 (1): 240. doi:10.1137/S0097539705447347. S2CID 1480961.
26. "How does a HashMap work in JAVA". coding-geek.com.
27. Tarjan, Robert Endre (April 1985). "Amortized Computational Complexity" (PDF). SIAM Journal on Algebraic and Discrete Methods. 6 (2): 306–318. doi:10.1137/0606031.
28. The important thing about these tree rotations is that they preserve the in-order sequence of the tree’s nodes.
29. "Ben Pfaff (2007): Online HTML version of a well-documented collection of binary search tree and balanced tree library routines".
30. The left columns contain far less nodes than the right ones, especially for removal. This indicates that some efficiency can be gained by pulling the first iteration out of the rebalancing loops of insertion and deletion, because many of the named nodes are NIL nodes in the first iteration and definitively non-NIL later. (See also this remark.)
31. Rotations have been placed before recoloring for reasons of clarity. But the two commute, so that it is free choice to move the rotation to the tail.
32. The same partitioning is found in Ben Pfaff.
33. Dinesh P. Mehta, Sartaj Sahni (Ed.) Handbook of Data Structures and Applications 10.4.2
34. Equality at the upper bound holds for the minimal RB trees RB_2k of even height ${\displaystyle 2\cdot k}$ with ${\displaystyle n=2\cdot 2^{k}-2}$ nodes and only for those. So the inequality is marginally more precise than the widespread ${\displaystyle h<2\log _{2}(n+1),}$ e.g. in Cormen p. 264.
    Moreover, these trees are binary trees that admit one and only one coloring conforming to the RB requirements 1 to 4. But there are further such trees, e.g. appending a child node to a black leaf always forces it to red. (A minimal RB tree of odd height allows to flip the root’s color from red to black.)
35. Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets" (PDF), Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID 2897793.
36. Park, Heejin; Park, Kunsoo (2001). "Parallel algorithms for red–black trees". Theoretical Computer Science. 262 (1–2): 415–435. doi:10.1016/S0304-3975(00)00287-5. Our parallel algorithm for constructing a red–black tree from a sorted list of ${\displaystyle n}$ items runs in ${\displaystyle O(1)}$ time with ${\displaystyle n}$ processors on the CRCW PRAM and runs in ${\displaystyle O(\log \log n)}$ time with ${\displaystyle n/\log \log n}$ processors on the EREW PRAM.
37. Sanders, Peter (2019). Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (eds.). Sequential and Parallel Algorithms and Data Structures : The Basic Toolbox. Springer eBooks. Cham: Springer. pp. 252–253. doi:10.1007/978-3-030-25209-0. ISBN 9783030252090. S2CID 201692657.
38. Akhremtsev, Yaroslav; Sanders, Peter (2016). "Fast Parallel Operations on Search Trees". HiPC 2016, the 23rd IEEE International Conference on High Performance Computing, Data, and Analytics, Hyderabad, India, December, 19-22. IEEE, Piscataway (NJ): 291–300. arXiv:1510.05433. Bibcode:2015arXiv151005433A. ISBN 978-1-5090-5411-4.
39. Jájá, Joseph (1992). An introduction to parallel algorithms. Reading, Mass. [u.a.]: Addison-Wesley. pp. 65–70. ISBN 0201548569. Zbl 0781.68009.

Further reading

• Mathworld: Red–Black Tree
• San Diego State University: CS 660: Red–Black tree notes, by Roger Whitney
• Pfaff, Ben (junio de 2004). "Análisis de rendimiento de las BST en el software de sistemas" (PDF) . Universidad de Stanford .

Enlaces externos

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