Árbol rojo-negro

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] $O(\log n)$ ${\estilo de visualización n}$ $O(\log n)$

Para rastrear el color de cada nodo se necesita solo un bit de información por nodo porque 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 un camino , uno debe notar que, por ejemplo, 3 caminos pasan por el nodo 1 , es decir, un camino a través de 1 _izquierda más 2 caminos agregados a través de 1 _derecha , es decir, los caminos a través de 6 _izquierda y 6 _derecha . De esta manera, estos extremos de los caminos 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]

Cada nodo es rojo o negro.
Todos los nodos NIL (figura 1) se consideran negros.
Un nodo rojo no tiene un hijo rojo.
Cada ruta desde un nodo dado a cualquiera de sus nodos NIL descendientes pasa por el mismo número de nodos negros.
(Conclusión) Si un nodo N tiene exactamente un hijo, el hijo debe ser 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. ${\estilo de visualización h}$ ${\estilo de visualización n}$ $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. $O(\log n)$

Analogía con 2-3-4 árboles

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}^] $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 conservar 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. $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–negro, y es por eso que muchos textos introductorios de algoritmos introducen los árboles 2–3–4 justo antes de los árboles rojo–negro, 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 primario.

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] $O(m)$ $O(\log m)$ ${\estilo de visualización 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). $O(\log n)$ ${\estilo de visualización n}$ ${\estilo de visualización 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 nodo RB no raíz no NIL* N: #define childDir(N) ( N == (N->parent)->right ? RIGHT : LEFT )

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]

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.
Si una rotación se considera útil, esto se ilustra en la siguiente acción, que se denomina "rotación".
Si se considera útil cambiar el color, esto se ilustra en la siguiente acción, que se denomina "colorear". ^[31]
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 etiqueta como "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 niveles del á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. $\Delta h=2$ ${\tfrac {h}{2}}$ ${\estilo de visualización 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

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. ${\tfrac {h-1}{2}}$ ${\estilo de visualización 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

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

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 a 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 de acuerdo con la conclusión 5, y el nodo eliminado debe ser negro de acuerdo con 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 acotación 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. ^[33] ) $\Delta h=1$ ${\estilo de visualización h}$ ${\estilo de visualización 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

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

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

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 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 (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

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 = BLACK ; D -> color = BLACK ; return ; // eliminación completa } // fin de RBdelete2

Prueba de límites

Porque hay un árbol rojo-negro de altura con $h\in \mathbb {N}$ ${\estilo de visualización 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 $\lpiso \,\rpiso$
$\lceil h/2\rceil$ ${\estilo de visualización h}$ ${\estilo de visualización (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 ${\estilo de visualización h=1}$

m_{1}=2^{\lpiso (1+1)/2\rpiso }\!+\!2^{\lpiso 1/2\rpiso }\!\!-\!\!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 $h>1$ $h\!\!-\!\!1$ $estilo de visualización m_{h-1}}$ $\lpiso (h\!\!-\!\!1)/2\rpiso =:s.$ ${\estilo de visualización s}$ $2^{s}\!\!-\!\!1=2^{\lpiso (h-1)/2\rpiso }\!\!-\!\!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 ). $Estilo de visualización m_ {h}}$ $(h=2k\;|\;m_{2k}=2\cdot 2^{k}\!-\!2)$ $k\in \mathbb {N} .$ $Estilo de visualización m_ {h}=}$ $h\geq 1$

Resolviendo la función para ${\estilo de visualización h}$

La desigualdad conduce a , lo que para impar conduce a $Estilo de visualización 9>8=2^{3}}$ $Estilo de visualización 3>2^{3/2}}$ ${\estilo de visualización h}$

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 ${\estilo de visualización h}$

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

Conclusión

Un árbol rojo-negro con nodos (claves) tiene una altura de árbol ${\estilo de visualización n}$ $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 1$ y $t 2$ y una clave $k$ , donde $t 1 < k < t 2$ , es decir, todas las claves en $t 1$ son menores que $k$ , y todas las claves en $t 2$ son mayores que $k$ . Devuelve un árbol que contiene todos los elementos en $t 1$ , $t 2$ también como $k$ .

Si los dos árboles tienen la misma altura negra, Join simplemente crea un nuevo nodo con subárbol izquierdo

t 1

, raíz

k

y subárbol derecho

t 2

. Si tanto

t 1

como

t 2

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 1

tiene una altura negra mayor que

t 2

(el otro caso es simétrico). La unión sigue la columna derecha de

t 1

hasta un nodo negro

c

, que está equilibrado con

t 2

. 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 2

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 .

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 1$ y $t 2$ que representan los conjuntos $A$ y $B$ , es un árbol rojo-negro $t$ que representa $A \cup B$ . La siguiente función recursiva calcula esta unión:

función unión(t ₁ , t ₂ ): si t ₁ = nulo devuelve t ₂ si t ₂ = nulo devuelve t ₁ (L ₁ ,b,R ₁ )=split(t ₁ ,t ₂ .key) proc1= inicio : T _L = unión (L ₁ ,t ₂ .izquierda) proc2= inicio : T _R = unión(R ₁ ,t ₂ .derecha) esperar todo proc1,proc2 devolver unión(T _L , t ₂ .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 join" .

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. $O\left(m\log \left({n \sobre m}+1\right)\right)$ ${\estilo de visualización m}$ $n(\geq m)$ $O(\log m\log n)$ ${\estilo de visualización 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] $O(\log \log n)$ ${\estilo de visualización n}$ $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.

Los algoritmos para operaciones masivas no solo son aplicables al árbol rojo-negro, sino que también se pueden adaptar a otras estructuras de datos de secuencias ordenadas, como el árbol 2-3 , el árbol 2-3-4 y el árbol (a,b) . A continuación, se explicarán diferentes algoritmos para la inserción masiva, pero los mismos algoritmos también se pueden aplicar a la eliminación y actualización. La inserción masiva es una operación que inserta cada elemento de una secuencia en un árbol . $I$ $T$

Basado en unión

Este enfoque se puede aplicar a cualquier estructura de datos de secuencia ordenada que admita operaciones de unión y división eficientes. ^[37] La idea general es dividir en múltiples partes y realizar las inserciones en estas partes en paralelo. $I$ $T$

Primero se debe ordenar la mayor parte de elementos a insertar. $I$
Después de eso, el algoritmo se divide en partes de tamaños aproximadamente iguales. $I$ $k\in \mathbb {N} ^{+}$ $\langle I_{1},\cdots ,I_{k}\rangle$
A continuación, el árbol debe dividirse en partes de manera que para cada una de las siguientes restricciones se cumplan: $T$ $k$ $\langle T_{1},\cdots ,T_{k}\rangle$ $j\in \mathbb {N} ^{+}|\,1\leq j<k$
1. ${\text{last}}(I_{j})<{\text{first}}(T_{j+1})$
2. ${\text{last}}(T_{j})<{\text{first}}(I_{j+1})$
Ahora el algoritmo inserta cada elemento de en secuencialmente. Este paso debe realizarse para cada , lo que puede realizarse con hasta procesadores en paralelo. $I_{j}$ $T_{j}$ $j$ $k$
Finalmente, los árboles resultantes se unirán para formar el resultado final de toda la operación.

Tenga en cuenta que en el Paso 3 las restricciones para la división aseguran que en el Paso 5 los árboles puedan unirse nuevamente y se ordene la secuencia resultante. $I$

árbol inicial
dividir I y T
Insertar en la T dividida
articulación

El pseudocódigo muestra una implementación simple de divide y vencerás del algoritmo basado en join para la inserción masiva. Ambas llamadas recursivas se pueden ejecutar en paralelo. La operación de join que se utiliza aquí difiere de la versión explicada en este artículo; en su lugar, se utiliza join2 , que omite el segundo parámetro k.

inserción masiva (T, I, k): yo.ordenar() InsertarRec en masa (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 ₁ , _, T ₂ ) := dividir(T, I[m]) InsertarRec en masa (T ₁ , I[0 .. m], ⌈k / 2⌉) || bulkInsertRec(T ₂ , I[m + 1 .. tamaño(I) - 1], ⌊k / 2⌋) T ← unir2(T ₁ , T ₂ )

Tiempo de ejecución

La clasificación no se considera en este análisis. $I$

Esto se puede mejorar utilizando algoritmos paralelos para dividir y unir. En este caso, el tiempo de ejecución es . ^[38] $\in O\left(\log |T|+{\frac {|I|}{k}}\log |T|\right)$

Trabajar

Canalización

Otro método para paralelizar operaciones en bloque es utilizar un enfoque de segmentación . ^[39] Esto se puede hacer dividiendo la tarea de procesar una operación básica en una secuencia de subtareas. Para múltiples operaciones básicas, las subtareas se pueden procesar en paralelo asignando cada subtarea a un procesador independiente.

Primero se debe ordenar la mayor parte de elementos a insertar. $I$
Para cada elemento del algoritmo se ubica la posición de inserción correspondiente en . Esto se puede hacer en paralelo para cada elemento ya que no se mutará en este proceso. Ahora se debe dividir en subsecuencias según la posición de inserción de cada elemento. Por ejemplo , la subsecuencia de que contiene los elementos cuya posición de inserción estaría a la izquierda del nodo . $I$ $T$ $\in I$ $T$ $I$ $S$ $s_{n,{\mathit {left}}}$ $I$ $n$
El elemento central de cada subsecuencia se insertará en un nuevo nodo . Esto se puede hacer en paralelo para cada uno, ya que por definición la posición de inserción de cada uno es única. Si contiene elementos a la izquierda o a la derecha de , estos estarán contenidos en un nuevo conjunto de subsecuencias como o . $m_{n,{\mathit {dir}}}$ $s_{n,{\mathit {dir}}}$ $T$ $n'$ $m_{n,{\mathit {dir}}}$ $m_{n,{\mathit {dir}}}$ $s_{n,{\mathit {dir}}}$ $m_{n,{\mathit {dir}}}$ $S$ $s_{n',{\mathit {left}}}$ $s_{n',{\mathit {right}}}$
Ahora es posible que contenga hasta dos nodos rojos consecutivos al final de las rutas que van desde la raíz hasta las hojas, que deben repararse. Tenga en cuenta que, durante la reparación, la posición de inserción de los elementos debe actualizarse si los nodos correspondientes se ven afectados por rotaciones. Si dos nodos tienen diferentes ancestros negros más cercanos, se pueden reparar en paralelo. Dado que como máximo cuatro nodos pueden tener el mismo ancestro negro más cercano, los nodos del nivel más bajo se pueden reparar en un número constante de pasos paralelos. Este paso se aplicará sucesivamente a los niveles negros superiores hasta que se repare por completo. $T$ $\in S$

$T$
Los pasos 3 a 5 se repetirán en las nuevas subsecuencias hasta que esté vacío. En este punto, se han insertado todos los elementos . Cada aplicación de estos pasos se denomina etapa . Dado que la longitud de las subsecuencias en es y en cada etapa las subsecuencias se reducen a la mitad, el número de etapas es . Dado que todas las etapas suben los niveles negros del árbol, se pueden paralelizar en una tubería. Una vez que una etapa ha terminado de procesar un nivel negro, la siguiente etapa puede subir y continuar en ese nivel. $S$ $\in I$ $S$ $\in O(|I|)$ $\in O(\log |I|)$

Árbol inicial
Buscar posiciones de inserción
La etapa 1 inserta elementos
La etapa 1 comienza a reparar los ganglios
La etapa 2 inserta elementos
La etapa 2 comienza a reparar los ganglios
La etapa 3 inserta elementos
La etapa 3 comienza a reparar los ganglios
La etapa 3 continúa reparando los ganglios

Tiempo de ejecución

En este análisis no se tiene en cuenta la ordenación . Además, se supone que es menor que , de lo contrario sería más eficiente construir el árbol resultante desde cero. $I$ $|I|$ $|T|$

Trabajar

Véase también

Lista de estructuras de datos
Estructura de datos de árbol
Rotación de árboles
Ordenar árbol estadístico
Árbol AA , una variación del árbol rojo-negro
Árbol rojo-negro con inclinación hacia la izquierda
Árbol AVL
Árbol B ( árbol 2–3 , árbol 2–3–4 , árbol B+ , árbol B* , árbol UB )
Árbol de chivos expiatorios
Árbol de expansión
árbol T
Árbol WAVL

Referencias y notas

^ desde Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "Árboles rojos y negros". Introducción a los algoritmos (2.ª ed.). MIT Press. págs. 273–301. ISBN 978-0-262-03293-3.
^ Paton, James. "Árboles rojo-negros".
^ Morris, John (1998). "Árboles rojos y negros". Estructuras de datos y algoritmos .
^ Bayer, Rudolf (1972). "Árboles B binarios simétricos: Estructura de datos y algoritmos de mantenimiento". Acta Informatica . 1 (4): 290–306. doi :10.1007/BF00289509. S2CID 28836825.
^ Drozdek, Adam (2001). Estructuras de datos y algoritmos en Java (2.ª edición). Sams Publishing. pág. 323. ISBN 978-0534376680.
^ ab Guibas, Leonidas J. ; Sedgewick, Robert (1978). "Un marco dicromático para árboles equilibrados". Actas del 19.º Simposio anual sobre fundamentos de la informática . págs. 8–21. doi :10.1109/SFCS.1978.3.
^ "Árboles rojos y negros". eternallyconfuzzled.com . Archivado desde el original el 27 de septiembre de 2007. Consultado el 2 de septiembre de 2015 .
^ Sedgewick, Robert (2012). Red–Black BSTs. Coursera. Mucha gente pregunta por qué usamos el nombre rojo–negro. Bueno, inventamos esta estructura de datos, esta forma de ver los árboles balanceados, en Xerox PARC, que fue el hogar de la computadora personal y muchas otras innovaciones con las que vivimos hoy en día, introduciendo interfaces gráficas de usuario, Ethernet y programación orientada a objetos y muchas otras cosas. Pero una de las cosas que se inventó allí fue la impresión láser y estábamos muy emocionados de tener cerca una impresora láser a color que pudiera imprimir cosas en color y, de los colores, el rojo se veía mejor. Entonces, es por eso que elegimos el color rojo para distinguir los enlaces rojos, los tipos de enlaces, en tres nodos. Entonces, esa es una respuesta a la pregunta para las personas que han estado preguntando.
^ "¿De dónde viene el término "árbol rojo/negro"?". programmers.stackexchange.com . Consultado el 2 de septiembre de 2015 .
^ Andersson, Arne (11 de agosto de 1993). "Árboles de búsqueda balanceados simplificados". En Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue (eds.). Algoritmos y estructuras de datos (Actas). Apuntes de clase en informática. Vol. 709. Springer-Verlag Berlin Heidelberg. págs. 60–71. CiteSeerX 10.1.1.118.6192 . doi :10.1007/3-540-57155-8_236. ISBN . 978-3-540-57155-1. Archivado desde el original el 8 de diciembre de 2018.URL alternativa
^ Okasaki, Chris (1 de enero de 1999). "Árboles rojo-negros en un entorno funcional". Revista de programación funcional . 9 (4): 471–477. doi : 10.1017/S0956796899003494 . ISSN 1469-7653. S2CID 20298262.
^ Sedgewick, Robert (1983). Algoritmos (1.ª ed.). Addison-Wesley . ISBN 978-0-201-06672-2.
^ Sedgewick, Robert ; Wayne, Kevin. "RedBlackBST.java". algs4.cs.princeton.edu . Consultado el 7 de abril de 2018 .
^ Sedgewick, Robert (2008). "Árboles rojo-negros de tendencia izquierdista" (PDF) .
^ abc Sedgewick, Robert ; Wayne, Kevin (2011). Algoritmos (4.ª ed.). Addison-Wesley Professional. ISBN 978-0-321-57351-3.
^ abcd Mehlhorn, Kurt ; Sanders, Peter (2008). "7. Secuencias ordenadas" (PDF) . Algoritmos y estructuras de datos: la caja de herramientas básica. Berlín/Heidelberg: Springer. CiteSeerX 10.1.1.148.2305 . doi :10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.
^ ab Cormen, Thomas ; Leiserson, Charles ; Rivest, Ronald ; Stein, Clifford (2022). "13. Árboles rojo-negros". Introducción a los algoritmos (4.ª ed.). MIT Press . págs. 331–332. ISBN 9780262046305.
^ Utilizando la definición de orden de Knuth: el número máximo de hijos
^ Sedgewick, Robert (1998). Algoritmos en C++ . Addison-Wesley Professional. págs. 565–575. ISBN. 978-0-201-35088-3.
^ "IBM Developer". developer.ibm.com . Consultado el 25 de mayo de 2024 .
^ "La implementación de epoll (1)". Septiembre de 2014.
^ Pfaff 2004
^ ab "Robert Sedgewick" (PDF) . Cs.princeton.edu . 4 de junio de 2020 . Consultado el 26 de marzo de 2022 .
^ "Árboles equilibrados" (PDF) . Cs.princeton.edu . Consultado el 26 de marzo de 2022 .
^ Demaine, ED; Armon, D.; Iacono, J.; Pătraşcu, M. (2007). "Optimidad dinámica: casi" (PDF) . Revista SIAM de Computación . 37 (1): 240. doi :10.1137/S0097539705447347. S2CID 1480961.
^ "¿Cómo funciona un HashMap en JAVA?". coding-geek.com.
^ Tarjan, Robert Endre (abril de 1985). "Complejidad computacional amortizada" (PDF) . Revista SIAM sobre métodos algebraicos y discretos . 6 (2): 306–318. doi :10.1137/0606031.
^ Lo importante de estas rotaciones de árboles es que preservan la secuencia en orden de los nodos del árbol.
^ "Ben Pfaff (2007): Versión HTML en línea de una colección bien documentada de rutinas de biblioteca de árboles de búsqueda binarios y árboles equilibrados".
^ ab Las columnas de la izquierda contienen muchos menos nodos que las de la derecha, especialmente para la eliminación. Esto indica que se puede ganar cierta eficiencia al sacar la primera iteración de los bucles de reequilibrio de inserción y eliminación, porque muchos de los nodos nombrados son nodos NIL en la primera iteración y definitivamente no NIL más adelante. (Véase también esta observación.)
^ Se han colocado rotaciones antes de la recoloración por razones de claridad. Pero ambas conmutan, por lo que es libre elegir mover la rotación hacia la cola .
^ ab La misma partición se encuentra en Ben Pfaff.
^ Dinesh P. Mehta, Sartaj Sahni (Ed.) Manual de estructuras de datos y aplicaciones 10.4.2
^ La igualdad en el límite superior se cumple para los árboles RB mínimos RB _{2 k} de altura par con nodos y solo para estos. Por lo tanto, la desigualdad es marginalmente más precisa que la generalizada, por ejemplo, en Cormen p. 264. Además, estos árboles son árboles binarios que admiten una y solo una coloración conforme a los requisitos RB 1 a 4. Pero hay más árboles de este tipo, por ejemplo, agregar un nodo hijo a una hoja negra siempre la obliga a ser roja. (Un árbol RB mínimo de altura impar permite cambiar el color de la raíz de rojo a negro). $2\cdot k$ $n=2\cdot 2^{k}-2$ $h<2\log _{2}(n+1),$
^ ab Blelloch, Guy E .; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets" (PDF) , Simposio sobre algoritmos y arquitecturas paralelas, Actas del 28.º Simposio de la ACM sobre algoritmos y arquitecturas paralelas (SPAA 2016) , ACM, págs. 253–264, arXiv : 1602.02120 , doi :10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, Número de identificación del sujeto 2897793.
^ Park, Heejin; Park, Kunsoo (2001). "Algoritmos paralelos para árboles rojo-negros". Theoretical Computer Science . 262 (1–2): 415–435. doi : 10.1016/S0304-3975(00)00287-5 . Nuestro algoritmo paralelo para construir un árbol rojo-negro a partir de una lista ordenada de elementos se ejecuta en tiempo con procesadores en la PRAM CRCW y se ejecuta en tiempo con procesadores en la PRAM EREW. $n$ $O(1)$ $n$ $O(\log \log n)$ $n/\log \log n$
^ Sanders, Peter (2019). Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (eds.). Algoritmos secuenciales y paralelos y estructuras de datos: la caja de herramientas básica . Springer eBooks. Cham: Springer. págs. 252–253. doi :10.1007/978-3-030-25209-0. ISBN . 9783030252090.S2CID201692657 .
^ Akhremtsev, Yaroslav; Sanders, Peter (2016). "Operaciones rápidas en paralelo en árboles de búsqueda". HiPC 2016, la 23.ª Conferencia internacional IEEE sobre computación de alto rendimiento, datos y análisis, Hyderabad, India, diciembre, 19-22 . IEEE, Piscataway (Nueva Jersey): 291–300. arXiv : 1510.05433 . Código Bibliográfico :2015arXiv151005433A. ISBN : 978-0-822-2-2015. 978-1-5090-5411-4.
^ Jájá, Joseph (1992). Introducción a los algoritmos paralelos. Reading, Mass. [ua]: Addison-Wesley. págs. 65–70. ISBN 0201548569. Número de serie 0781.68009.

Lectura adicional

Mathworld: Árbol rojo y negro
Universidad Estatal de San Diego: CS 660: Notas sobre árboles rojos y negros, por 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 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-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