En informática , un árbol rojo-negro es una especie de árbol de búsqueda binaria autoequilibrado . Cada nodo almacena un bit adicional que representa el "color" ("rojo" o "negro"), que se utiliza para garantizar que el árbol permanezca equilibrado durante las inserciones y eliminaciones. [2]
Árbol rojo-negro | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | árbol | ||||||||||||||||||||
Inventado | 1972 | ||||||||||||||||||||
Inventado por | Rudolf Bayer | ||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||
|
Cuando se modifica el árbol, el nuevo árbol se reorganiza y se "vuelve a pintar" para restaurar las propiedades de color que limitan el desequilibrio que puede llegar a tener el árbol en el peor de los casos. Las propiedades están diseñadas de manera que esta reorganización y cambio de color se pueda realizar de manera eficiente.
El reequilibrio no es perfecto, pero garantiza la búsqueda en tiempo, donde es el número de nodos del árbol. Las operaciones de inserción y eliminación, junto con la reordenación y el cambio de color del árbol, también se realizan enhora. [3]
El seguimiento del color de cada nodo requiere solo 1 bit de información por nodo porque solo hay dos colores. 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 un árbol de búsqueda binario clásico (sin color) . En muchos casos, el bit adicional de información se puede almacenar sin costo adicional de memoria.
Historia
En 1972, Rudolf Bayer [4] inventó una estructura de datos que era un caso especial fin-4 de un árbol-B . Estos árboles mantuvieron todos los caminos desde la raíz hasta la hoja con el mismo número de nodos, creando árboles perfectamente equilibrados. Sin embargo, no eran árboles de búsqueda binarios . Bayer los llamó un "árbol B binario simétrico" en su artículo y más tarde se hicieron populares como 2–3–4 árboles o solo 2–4 árboles. [5]
En un artículo de 1978, "Un marco dicromático para árboles equilibrados", [6] Leonidas J. Guibas y Robert Sedgewick derivaron el árbol rojo-negro del árbol B binario simétrico. [7] Se eligió el color "rojo" 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 por los bolígrafos rojos y negros 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 mostró cómo hacer que la operación de inserción sea puramente funcional. Su función de equilibrio necesitaba ocuparse de solo 4 casos desequilibrados y un caso equilibrado predeterminado. [11]
El algoritmo original utilizó 8 casos desequilibrados, pero Cormen et al. (2001) redujeron eso a 6 casos desequilibrados. [2] 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 permitió nodos cuyos dos hijos son rojos, lo que hace que sus árboles se parezcan más a 2–3–4 árboles, pero más tarde se agregó esta restricción, haciendo que los nuevos árboles se parezcan más a 2–3 árboles. Sedgewick implementó el algoritmo de inserción en solo 33 líneas, acortando significativamente sus 46 líneas originales de código. [14] [15]
Terminología
Un árbol rojo-negro es un tipo especial de árbol de búsqueda binario , utilizado en informática para organizar piezas de datos comparables , como fragmentos de texto o números (por ejemplo, los números de las figuras 1 y 2). Los nodos que llevan claves y / o datos se denominan con frecuencia "nodos internos" , pero para que esto sea muy específico, también se denominan nodos no NIL en este artículo.
Los nodos de las hojas de los árboles rojo-negro ( NIL en la figura 1) no contienen claves ni datos. Estas "hojas" no tienen por qué ser individuos explícitos en la memoria de la computadora: un puntero NULL puede, como en todas las estructuras de datos de árbol binario, 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, puede tener un nodo padre, hermano (es decir, el otro hijo del padre), tío, incluso sobrino; y puede ser hijo, pero nunca padre de otro nodo. No es realmente necesario atribuir un "color" a estos objetos de fin de ruta, porque la condición "es " o [16] está implícita en la condición "es ". NIL
BLACK
NIL
La Figura 2 muestra el mismo árbol rojo-negro conceptualmente sin estas hojas NIL. Para llegar a la misma noción de ruta , uno tiene que notar que, por ejemplo, 3 rutas atraviesan el nodo 1 , es decir, una ruta a través de 1 a la izquierda más 2 rutas adicionales a 1 a la derecha , es decir, las rutas a través de 6 a la izquierda y 6 a la derecha . De esta forma, estos extremos de los caminos también son puntos de atraque para insertar nuevos nodos, totalmente equivalente a las hojas NIL de la figura 1.
Por otro lado, 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 niño no existe (no es un nodo verdadero, no contiene datos) puede ser especificado en todas las ocasiones por el mismo puntero NULL o como el mismo puntero a un nodo centinela. A lo largo de este artículo, cualquier elección de este valor se indicará con la constante nombrada NIL
.
La profundidad de negro 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 antepasados 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, según la propiedad 4, es constante (alternativamente, podría definirse como la profundidad negra de cualquier nodo foliar). [17] : 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 una hoja NIL se establecerá en 0, porque su subárbol está vacío como se sugiere en la figura 2, y la altura de su á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 : [18]
- Cada nodo es rojo o negro.
- Todas las hojas NIL (figura 1) se consideran negras.
- Si un nodo es rojo, entonces sus dos hijos son negros.
- Cada camino desde un nodo dado a cualquiera de sus hojas NIL descendientes pasa por el mismo número de nodos negros.
Algunos autores, por ejemplo, Cormen & al., [18] afirman que "la raíz es negra" como quinta propiedad; pero no Mehlhorn & Sanders [17] ni Sedgewick & Wayne. [15] : 432–447 Dado que la raíz siempre se puede cambiar de rojo a negro, esta regla tiene poco efecto en el análisis. Este artículo también lo omite, porque perturba ligeramente los algoritmos recursivos y las pruebas.
Como ejemplo, cada árbol binario perfecto que consta solo de nodos negros es un árbol rojo-negro.
Las operaciones de solo lectura, como la búsqueda o el recorrido del árbol, no afectan a ninguna de las propiedades. Por otro lado, las operaciones de modificación insertar y borrar mantienen fácilmente las propiedades 1 y 2, pero con respecto a las otras propiedades se debe hacer un esfuerzo adicional para evitar la introducción de una violación de la propiedad 3, llamadainfracción roja , o de la propiedad 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 operaciones como insertar, eliminar y encontrar valores requieren un tiempo en el peor de los casos proporcional a la alturadel árbol, este límite superior en la altura permite que los árboles rojo-negro sean eficientes en el peor de los casos, es decir, logarítmico en el número de nodos, es decir , que no es el caso de los árboles de búsqueda binarios ordinarios . Para obtener una demostración matemática, consulte la sección Prueba de límites .
Los árboles rojo-negro, como todos los árboles de búsqueda binarios , permiten un acceso secuencial bastante eficiente (por ejemplo , recorrido en orden , es decir: en el orden Izquierda-Raíz-Derecha) de sus elementos. Pero también admiten un acceso directo asintóticamente óptimo a través de un recorrido de raíz a hoja, lo que da como resultado tiempo de búsqueda.
Analogía con árboles B de orden 4
Un árbol rojo-negro es similar en estructura a un árbol B de orden [19] 4, donde cada nodo puede contener entre 1 y 3 valores y (en consecuencia) entre 2 y 4 punteros secundarios. En tal árbol B, cada nodo contendrá solo un valor que coincida con el valor en un nodo negro del árbol rojo-negro, con un valor opcional antes y / o después en el mismo nodo, ambos coincidiendo con un nodo rojo equivalente de el árbol rojo-negro.
Una forma de ver esta equivalencia es "mover hacia arriba" los nodos rojos en una representación gráfica del árbol rojo-negro, de modo que se alineen horizontalmente con su nodo negro padre, creando juntos un grupo horizontal. En el árbol B, o en la representación gráfica modificada del árbol rojo-negro, todos los nodos de las hojas están a la misma profundidad.
El árbol rojo-negro es entonces estructuralmente equivalente a un árbol B de orden 4, con un factor de llenado mínimo del 33% de los valores por grupo con una capacidad máxima de 3 valores.
Sin embargo, este tipo de árbol B es aún más general que un árbol rojo-negro, ya que permite la ambigüedad en una conversión de árbol rojo-negro; se pueden producir varios árboles rojo-negro a partir de un árbol B equivalente de orden 4 (ver figura 3 ). Si un grupo de árbol B contiene solo 1 valor, es el mínimo, negro y tiene dos punteros secundarios. Si un grupo contiene 3 valores, entonces el valor central será negro y cada valor almacenado en sus lados será rojo. Sin embargo, si el clúster contiene dos valores, cualquiera de los dos puede convertirse en el nodo negro en el árbol rojo-negro (y el otro será rojo).
Por lo tanto, el árbol B de orden 4 no mantiene cuál de los valores contenidos en cada grupo es el árbol raíz negro para todo el grupo y el padre de los otros valores en el mismo grupo. A pesar de esto, las operaciones en árboles rojo-negro son más económicas en el tiempo porque no es necesario mantener el vector de valores. [20] Puede resultar costoso si los valores se almacenan directamente en cada nodo en lugar de almacenarse por referencia. Los nodos de árbol B, sin embargo, son más económicos en el espacio porque no es necesario almacenar el atributo de color para cada nodo. En su lugar, debe saber qué ranura del vector de clúster se utiliza. Si los valores se almacenan por referencia, por ejemplo, objetos, se pueden usar referencias nulas y, por lo tanto, el clúster se puede representar mediante un vector que contiene 3 ranuras para punteros de valor más 4 ranuras para referencias secundarias en el árbol. En ese caso, el árbol B puede ser más compacto en memoria, mejorando la ubicación de los datos.
Se puede hacer la misma analogía con árboles B con órdenes más grandes que pueden ser estructuralmente equivalentes a un árbol binario coloreado: solo necesitas más colores. Suponga que agrega azul, luego el árbol azul-rojo-negro definido como árboles rojo-negro pero con la restricción adicional de que no hay dos nodos sucesivos en la jerarquía que serán azules y todos los nodos azules serán hijos de un nodo rojo, entonces se convierte en equivalente a un árbol B cuyos grupos tendrán como máximo 7 valores en los siguientes colores: azul, rojo, azul, negro, azul, rojo, azul (Para cada grupo, habrá como máximo 1 nodo negro, 2 nodos rojos y 4 nodos azules).
Para volúmenes moderados de valores, las inserciones y eliminaciones en un árbol binario de color son más rápidas en comparación con los árboles B porque los árboles de colores no intentan maximizar el factor de relleno de cada grupo horizontal de nodos (solo el factor de relleno mínimo está garantizado en el binario de color árboles, limitando el número de divisiones o uniones de grupos). Los árboles B serán más rápidos para realizar rotaciones (porque las rotaciones ocurrirán con frecuencia dentro del mismo grupo en lugar de con múltiples nodos separados en un árbol binario de color). Sin embargo, para almacenar grandes volúmenes, los árboles B serán mucho más rápidos, ya que serán más compactos al agrupar a varios niños en el mismo grupo, donde se puede acceder a ellos localmente.
Todas las optimizaciones posibles en árboles B para aumentar los factores de relleno promedio de los clústeres son posibles en el árbol binario multicolor equivalente. En particular, maximizar el factor de relleno promedio en un árbol B estructuralmente equivalente es lo mismo que reducir la altura total del árbol multicolor, aumentando el número de nodos no negros. El peor de los casos ocurre cuando todos los nodos en un árbol binario coloreado son negros, el mejor caso ocurre cuando solo un tercio de ellos son negros (y los otros dos tercios son nodos rojos).
Los árboles rojo-negro ofrecen las peores garantías de tiempo de inserción, tiempo de eliminación y tiempo de búsqueda. Esto no solo los hace valiosos en aplicaciones urgentes, 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 pueden basarse en árboles rojo-negro, y el Programador Completamente Justo utilizado en los núcleos Linux actuales y la implementación de llamadas al sistema epoll [21] utiliza árboles rojo-negro.
El árbol AVL es otra estructura que soportabúsqueda, inserción y eliminación. Los árboles AVL pueden ser de color rojo-negro, por lo que son un subconjunto de árboles RB. La altura del peor caso es 0,720 veces la altura del peor caso de los árboles RB, por lo que los árboles AVL están más rígidamente equilibrados. Las mediciones de rendimiento de Ben Pfaff con casos de prueba realistas en 79 ejecuciones encuentran proporciones de AVL a RB entre 0,677 y 1,077, mediana en 0,947 y media geométrica de 0,910. [22] Los árboles WAVL tienen un rendimiento entre esos dos.
Los árboles rojo-negro también son particularmente valiosos en la programación funcional , donde son una de las estructuras de datos persistentes más comunes , que se utilizan para construir matrices asociativas y conjuntos que pueden retener versiones anteriores después de mutaciones. La versión persistente de árboles rojo-negro requiere espacio para cada inserción o eliminación, además del tiempo.
Por cada 2 a 4 árboles , hay árboles rojo-negro correspondientes con elementos de datos en el mismo orden. Las operaciones de inserción y supresión en 2–4 árboles también son equivalentes a las rotaciones y cambios de color en árboles rojo-negro. Esto hace de 2 a 4 árboles una herramienta importante para comprender la lógica detrás de los árboles rojo-negro, y esta es la razón por la que muchos textos introductorios de algoritmos introducen de 2 a 4 árboles justo antes de los árboles rojo-negro, aunque 2 a 4 árboles no se usan con frecuencia en práctica.
En 2008, Sedgewick introdujo una versión más simple del árbol rojo-negro llamado árbol rojo-negro inclinado a la izquierda [23] al eliminar un grado de libertad no especificado previamente en la implementación. El LLRB mantiene una invariante adicional de que todos los enlaces rojos deben inclinarse hacia la izquierda, excepto durante las inserciones y eliminaciones. Los árboles rojo-negro se pueden hacer isométricos para 2 a 3 árboles , [24] o 2 a 4 árboles, [23] para cualquier secuencia de operaciones. La isometría de 2-4 árboles fue descrita en 1978 por Sedgewick. [6] Con 2 a 4 árboles, la isometría se resuelve mediante un "cambio de color", que corresponde a una división, en la que el color rojo de dos nodos secundarios deja a los 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-negro 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 la mejora de la complejidad del tiempo de buscar un elemento de este tipo en a . [26]
Operaciones
Las operaciones de sólo lectura, como la búsqueda o el recorrido de árbol, en un árbol rojo-negro no requieren modificación de las que se utilizan para los árboles de búsqueda binaria , porque cada árbol rojo-negro es un caso especial de un árbol de búsqueda binario simple. Sin embargo, el resultado inmediato de una inserción o remoción puede violar las propiedades de un árbol rojo-negro, cuya restauración se llama reequilibrio para que los árboles rojo-negro se vuelvan auto-equilibrados.Requiere como máximo un pequeño número, en notación Big O , o en promedio una constante amortizada [17] : 158 número de cambios de color (que son muy rápidos en la práctica); y no más de tres rotaciones de árboles [27] (dos para la inserción). Aunque las operaciones de inserción y eliminación son complicadas, sus tiempos siguen siendo, dónde es el número de objetos en el árbol.
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 de Ben Pfaff [28] (v2.0.3 a partir de junio de 2019).
Los detalles de las operaciones de inserción y eliminación se demostrarán con un código C ++ de ejemplo . El código de ejemplo puede invocar las funciones auxiliares a continuación para encontrar los nodos padre, abuelo, tío, hermano y sobrino y para rotar un subárbol a la izquierda o la derecha:
// Definiciones de tipos básicos:enum color_t { NEGRO , ROJO };struct RBnode { // nodo del árbol rojo-negro RBnode * parent ; // == NULL si la raíz del árbol RBnode * child [ 2 ]; // == NIL si el niño está vacío // El índice es: // LEFT: = 0, if (key key) // RIGHT: = 1, if (key> parent-> key) enum color_t color ; int clave ; };#define NIL NULL // puntero nulo o puntero al nodo centinela #define LEFT 0 #define RIGHT 1 #define left child [LEFT] #define right child [RIGHT]struct RBtree { // árbol rojo-negro RBnode * root ; // == NIL si el árbol está vacío };// Obtener la dirección secundaria (∈ {IZQUIERDA, DERECHA}) // del nodo RB no root que no es NIL * N: #define childDir (N) (N == (N-> parent) -> right? RIGHT: IZQUIERDA )// Funciones auxiliares:RBnode * GetParent ( RBnode * N ) { // El padre del nodo raíz se establece en NULL. return N == NULL ? NULL : N -> padre ; }RBnode * GetGrandParent ( RBnode * N ) { // Devolverá NULL si N es root o hijo de root return GetParent ( GetParent ( N )); }RBnode * GetSibling ( RBnode * N ) { RBnode * P = GetParent ( N ); // Ningún padre significa que no hay hermanos: assert ( P ! = NULL ); return P -> child [ 1 - childDir ( N )]; } // Si el directorio principal P y el directorio secundario están disponibles, igual que: // P-> secundario [1-dir]RBnode * GetUncle ( RBnode * N ) { RBnode * P = GetParent ( N ); // Ningún padre significa que no hay tío: assert ( P ! = NULL ); return GetSibling ( P ); }RBnode * GetCloseNephew ( RBnode * N ) { RBnode * P = GetParent ( N ); int dir ; RBnode * S ; afirmar ( P ! = NULL ); dir = childDir ( N ); S = P -> hijo [ 1 - dir ]; // hermano de N assert ( S ! = NIL ); return S -> hijo [ dir ]; // el sobrino cercano a N }RBnode * GetDistantNephew ( RBnode * N ) { RBnode * P = GetParent ( N ); int dir ; RBnode * S ; afirmar ( P ! = NULL ); dir = childDir ( N ); S = P -> hijo [ 1 - dir ]; // hermano de N assert ( S ! = NIL ); return S -> hijo [ 1 - dir ]; // el sobrino distante de N }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 ; afirmar ( S ! = NIL ); // se requiere puntero al nodo verdadero C = S -> child [ dir ]; P -> hijo [ 1 - dir ] = C ; si ( C ! = NIL ) C -> padre = P ; S -> niño [ dir ] = P ; P -> padre = S ; S -> padre = G ; if ( G ! = NULL ) G -> child [ P == G -> right ? DERECHA : IZQUIERDA ] = S ; si no T -> raíz = S ; return S ; // nueva raíz del subárbol }#define RotateDir (N, dir) RotateDirRoot (T, N, dir) #define RotateLeft (N) RotateDirRoot (T, N, LEFT) #define RotateRight (N) RotateDirRoot (T, N, RIGHT)
- Notas para insertar y eliminar diagramas
La propuesta desglosa tanto la inserción como la eliminación (sin mencionar algunos casos muy simples), en seis configuraciones de nodos, bordes y colores, que se denominan casos. El código que repara (reequilibra) un caso a veces utiliza el código de un caso posterior. La propuesta contiene tanto para la inserción como para la extracción, exactamente un caso que avanza un nivel de negro más cerca de la raíz y los bucles, los otros cinco casos reequilibran el árbol propio. Los casos más complicados se muestran en un diagrama.
- La variable
N
denota el nodo actual, que está etiquetado como N en los diagramas. - simboliza un nodo rojo y un nodo negro (no NIL) (de altura negra ≥ 1), puede ser rojo o negro, pero del mismo color en el mismo diagrama.
- Un diagrama muestra tres columnas y de dos a cuatro pasos.
- La columna de la izquierda muestra la primera iteración, la columna de la derecha las iteraciones más altas, la columna del medio muestra la segmentación de un caso en sus diferentes pasos.
Observación: La columna de la izquierda contiene muchos menos nodos que la de la derecha, especialmente para su eliminación. Esto indica que se puede ganar algo de eficiencia para insertar y eliminar sacando la primera iteración de los bucles, haciendo así, por ejemplo, muchas pruebas para hojas NIL obsoletas.
- El primer paso está etiquetado como "entrada" y muestra el inicio del caso y allí la configuración y los colores de los nodos que violan algunos de los requisitos .
Un borde azul suena el nodo actual N y los otros nodos se etiquetan según su relación con N . - Si una rotación se considera útil, se muestra en el siguiente paso, que se denomina "rotación".
- Si se considera útil algún cambio de color, esto se muestra en el siguiente paso, que está etiquetado como "color". [29]
- Si todavía hay alguna necesidad de reparación, la configuración satisface el invariante de bucle respectivo con el nodo actual N recién asignado , que luego lleva nuevamente un anillo azul. Posiblemente algunos otros nodos están también recién asignado en relación con N . Este paso está etiquetado como "reasignar".
Las acciones posteriores reutilizan el código de los otros casos que también pueden ser una iteración un nivel negro más cerca de la raíz.
- La columna de la izquierda muestra la primera iteración, la columna de la derecha las iteraciones más altas, la columna del medio muestra la segmentación de un caso en sus diferentes pasos.
- Un triángulo posiblemente numerado con un círculo negro encima representa un subárbol rojo-negro (conectado a su padre según el requisito 3) con una altura de negro 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 numerado representa un subárbol rojo-negro con una altura de negro uno menos, es decir, su padre tiene una altura de negro cero en la segunda iteración.
Inserción
La inserción comienza colocando el nuevo nodo (no NIL), digamos N , en la posición en el árbol de búsqueda binaria de una hoja NIL cuya clave predecesora en orden se compara menos que la clave del nuevo nodo, que a su vez 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 P
junto con una dirección dir
con P->child[dir] == NIL
). El nodo recién insertado se colorea temporalmente en rojo para que todas las rutas contengan el mismo número de nodos negros. como antes. Pero si su padre, digamos P , también es rojo, entonces esta acción introduce una infracción roja .
void RBinsert1 ( RBtree * T , // -> estructura de árbol rojo – negro RBnode * P , // -> nodo padre de N ( puede ser NULL ) struct RBnode * N , // -> nodo a insertar byte dir ) / / lado de P en el cual a insertar N ( ∈ { LEFT , RIGHT }) { struct RBnode * G ; // -> nodo padre de P struct RBnode * U ; // -> tío de N N -> color = ROJO ; N -> izquierda = NULO ; N -> derecha = NULO ; N -> padre = P ; if ( P == NULL ) { // No hay padre T -> root = 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 // pasa al bucle
El bucle de reequilibrio tiene el siguiente invariante :
- El nodo actual N es rojo al comienzo de cada iteración.
- La propiedad 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 (incluida la propiedad 4) se satisfacen en todo el árbol.
- Notas a los diagramas de inserción
- En los diagramas, P se usa para el padre de N , G para el abuelo y U indicará el tío de N.
- Los diagramas muestran el nodo padre P como el hijo izquierdo de su padre G , aunque es posible que P esté en cualquier lado. Los ejemplos de código cubren ambas posibilidades mediante la variable lateral
dir
. - N es el nodo de inserción, pero a medida que avanza la operación, otros nodos pueden volverse actuales (ver caso 1).
- Los diagramas muestran los casos en los que P también es rojo, la infracción roja. [dieciséis]
Inserte el caso 3: el padre P del nodo actual es negro, por lo que la propiedad 3 (ambos hijos de cada nodo rojo son negros) se mantiene. La propiedad 4 también se mantiene de acuerdo con el invariante de bucle .
// inicio del bucle (do while): do { if ( P -> color == BLACK ) { // I_case_3 (P black): return ; // inserción completa } // A partir de ahora, P es rojo. if (( G = GetParent ( P )) == NULL ) goto I_case_6 ; // 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 -> hijo [ 1 - dir ]; // tío if ( U == NIL || U -> color == BLACK ) // considerado negro goto I_case_45 ; // P rojo && U negro
Inserte el caso 1: Si tanto el padre P como el tío U son rojos, ambos pueden volver a pintarse de negro y el abuelo G se vuelve rojo para mantener la propiedad 4 (todos los caminos desde un nodo a las hojas contienen el mismo número de nodos negros ). Dado que cualquier camino a través del padre o del tío debe pasar por el abuelo, el número de nodos negros en estos caminos no ha cambiado. Sin embargo, el abuelo G ahora puede violar la propiedad 3 (Ambos hijos de cada nodo rojo son negros) si tiene un padre rojo. Después de volver a etiquetar G a N el invariante bucle se cumple de manera que el procedimiento de reequilibrio se puede repetir en un nivel de negro (= 2 niveles de árboles) superior.
// I_case_1 (P + U rojo): P -> color = NEGRO ; U -> color = NEGRO ; G -> color = ROJO ; N = G ; // nuevo nodo actual // itera 1 nivel de negro (= 2 niveles de árbol) más alto } while (( P = N -> parent ) ! = NULL ); // fin de (do while) -loop // cae hasta I_case_2
Insertar caso 2: el nodo actual N es la raíz del árbol. A continuación, todas las propiedades están satisfechos con la raíz rojo N .
// I_case_2 (P == NULL): return ; // inserción completa
Inserte el caso 4: 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 de G). el hijo izquierdo de G ). A dir
-rotation en P conmuta las funciones del nodo actual N y su matriz P . La rotación agrega rutas a través de N (aquellas en el subárbol etiquetado como 2 , ver diagrama) y elimina las rutas a través de P (aquellas en el subárbol etiquetado como 4 ). Pero tanto P como N son rojos, por lo que la propiedad 4 (todos los caminos desde un nodo hasta sus hojas contienen el mismo número de nodos negros) se conserva. La propiedad 3 (ambos hijos de cada nodo rojo son negros) se restaura en el caso 5.
I_case_45 : // P rojo && U negro: if ( N == P -> hijo [ 1 - dir ]) { // I_case_4 (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 -> hijo [ dir ]; // nuevo padre de N // pasa a I_case_5 }
Inserte el caso 5: El nodo actual N ahora seguramente será un nieto "externo" de G (a la izquierda del hijo izquierdo o a la derecha del hijo derecho). Ahora (1-dir)
-Girar en G , poniendo P en lugar de G y haciendo P la matriz de N y G . G es negro y su antiguo hijo P es rojo, ya que se violó la propiedad 3. Después de cambiar los colores de P y G, el árbol resultante satisface la propiedad 3 (un nodo rojo tiene hijos negros). La propiedad 4 (todos los caminos desde un nodo hasta sus hojas contienen el mismo número de nodos negros) también permanece satisfecha, ya que todos los caminos que pasaron por la G negra ahora pasan por la P negra .
// I_case_5 (P rojo && U negro && N nieto externo de G): RotateDirRoot ( T , G , 1 - dir ); // G puede ser la raíz P -> color = BLACK ; G -> color = ROJO ; volver ; // inserción completa
Inserte el caso 6: El padre P es rojo y la raíz. Debido a que N también es rojo, se viola la propiedad 3 (un nodo rojo tiene hijos negros). Pero después de cambiar el color de P , el árbol tiene forma de RB. La altura negra del árbol aumenta en 1.
I_case_6 : // P es la raíz y rojo: P -> color = BLACK ; volver ; // inserción completa } // fin de RBinsert1
Debido a que el algoritmo transforma la entrada sin usar una estructura de datos auxiliar y usando solo una pequeña cantidad de espacio de almacenamiento adicional para las variables auxiliares, está en su lugar .
Las rotaciones ocurren en los casos 4 y 5, todos fuera del bucle. Por lo tanto, se producen como máximo dos rotaciones en total.
En el algoritmo anterior, todos los casos se ejecutan solo una vez, excepto el caso 1, en el que la implementación iterativa efectúa un bucle con el nodo abuelo como actual. Debido a que el problema de reparación en ese caso se eleva dos niveles más cada vez, se necesita el máximo 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 de inserción es constante en promedio, de hecho, se amortiza constante .
Eliminación: casos simples
La etiqueta N indica el nodo actual que en la entrada es el nodo que se eliminará.
Si N es la raíz que no tiene un hijo que no sea NIL, se reemplaza por una hoja NIL, después de lo cual el árbol está vacío y en forma RB.
Si N tiene dos hijos que no son NIL, una navegación adicional al elemento máximo en su subárbol izquierdo (que es el predecesor en orden) o al elemento mínimo en su subárbol derecho (que es el sucesor en orden) encuentra un nodo sin ningún otro nodo en el medio (como se muestra aquí ). Sin tocar los datos de usuario de este nodo, todos los punteros de árbol rojo-negro de este nodo y N se intercambian para que N ahora tenga como máximo un hijo que no sea NIL.
Si N tiene exactamente un hijo que no es NIL, debe ser un hijo rojo, porque si fuera negro, la propiedad 4 forzaría a un segundo hijo negro que no sea NIL.
Si N es un nodo rojo, no puede tener un hijo que no sea NIL, porque este tendría que ser negro según la propiedad 3. Además, no puede tener exactamente un hijo negro como se argumentó anteriormente. Como consecuencia, el nodo rojo N no tiene ningún hijo y simplemente se puede eliminar.
Si N es un nodo negro, puede tener un hijo rojo o ningún hijo que no sea NIL. Si N tiene un niño rojo, simplemente se reemplaza con este niño después de pintar el último de negro.
Eliminación de una hoja negra sin raíz
El caso complejo es cuando N no es la raíz, de color negro y no tiene un hijo que no sea NIL. En la primera iteración, N se reemplaza por NIL.
void RBdelete2 ( RBtree * T , // -> estructura de árbol rojo – negro RBnode * N ) // -> nodo a eliminar { struct RBnode * P = N -> padre ; // -> nodo padre de N byte dir ; // lado de P en el que se encuentra N (∈ {IZQUIERDA, DERECHA}) struct RBnode * S ; // -> hermano de N struct RBnode * C ; // -> cerrar sobrino 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 // Reemplaza N en su padre P por NIL: P -> child [ dir ] = NIL ; goto Start_D ; // saltar al bucle
El bucle de reequilibrio tiene el 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 más altas.
- El número de nodos negros en las rutas a través de N es uno menos que antes, mientras que no cambia en todas las demás rutas, por lo que hay una violación de negro en N si existen otras rutas.
- Todas las demás propiedades (incluida la propiedad 3) se satisfacen en todo el árbol.
- Notas para eliminar diagramas
- En los siguientes diagramas, P se utiliza para N ‘padre s, S para el hermano de N , C (es decir, cerca Nephew) para S ‘niño s en la misma dirección que N , y D (que significa distante Nephew) para S 's otro hijo ( S no puede ser una hoja NIL en la primera iteración, porque tiene que tener la altura negra uno, que era la altura negra de N antes de su eliminación, pero C y D pueden ser hojas NIL).
- Al comienzo (en la primera iteración) de la eliminación, N es la hoja NIL que reemplaza el nodo que se eliminará. Debido a que su ubicación en el nodo principal es más importante que su valor, está simbolizado poren la columna izquierda de los diagramas de eliminación. A medida que avanza la operación, también otros nodos (de altura negra ≥ 1) pueden volverse actuales (ver, por ejemplo, eliminar el caso 1).
- Los diagramas muestran el nodo actual N como el hijo izquierdo de su padre P aunque es posible que N esté en cualquier lado. Los ejemplos de código cubren ambas posibilidades mediante la variable lateral
dir
. - Contando las balas negras se puede observar que los caminos a través de N tienen una bala menos que los otros caminos, lo cual es una violación negra. [dieciséis]
// 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) if ( S -> color == RED ) goto D_case_3 ; // S rojo ===> P + C + D negro // S es negro: D = S -> child [ 1 - dir ]; // sobrino lejano if ( D ! = NIL && D -> color == RED ) // no se considera negro goto D_case_6 ; // D rojo && S negro C = S -> hijo [ dir ]; // sobrino cercano if ( C ! = NIL && C -> color == RED ) // no se considera negro goto D_case_5 ; // C rojo && S + D negro // Aquí ambos sobrinos son == NIL (primera iteración) o negros (después). if ( P -> color == RED ) goto D_case_4 ; // P rojo && C + S + D negro // P + C + S + D negro: caen a D_case_1
Elimine el caso 1: 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 todas las rutas en el subárbol enraizado por P tienen el mismo número de nodos negros, pero uno menos que las rutas que no pasan por P , por lo que la propiedad 4 (todas las rutas desde cualquier nodo dado a sus nodos hoja contienen el mismo número de nodos negros nodos) aún pueden ser violados. Después de volver a etiquetar P a N el invariante bucle se cumple de manera que el procedimiento de reequilibrio se puede repetir en un nivel de negro (= 1 nivel de árbol) superior.
// D_case_1 (P + C + S + D negro): S -> color = RED ; N = P ; // nuevo nodo actual (tal vez la raíz) // iterar 1 nivel de negro (= 1 nivel de árbol) más alto } while (( P = N -> parent ) ! = NULL ); // fin de (hacer while) -loop
Eliminar caso 2: 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.
// D_case_2 (P == NULL): return ; // eliminación completa
Elimine el caso 3: el hermano S es rojo, por lo que P y los sobrinos C y D tienen que ser negros. La dir
rotación A 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 sigue siendo un nodo negro corto. Pero N tiene un padre rojo y un hermano negro, por lo que las transformaciones en los casos 4, 5 o 6 pueden restaurar la forma RB.
D_case_3 : // S rojo && P + C + D negro: RotateDirRoot ( T , P , dir ); // P puede ser la raíz P -> color = RED ; S -> color = NEGRO ; S = C ; //! = NIL // ahora: P rojo && S negro // caen
Elimine el caso 4: Los hermanos S y los hijos de S son negros, pero P es rojo. El intercambio de colores de S y P no afecta la cantidad de nodos negros en las rutas que pasan por S , pero agrega uno a la cantidad de nodos negros en las rutas que pasan por N , compensando el nodo negro eliminado en esas rutas.
D = S -> hijo [ 1 - dir ]; // sobrino lejano if ( D ! = NIL && D -> color == RED ) // no se considera negro goto D_case_6 ; // D rojo && S negro C = S -> hijo [ dir ]; // sobrino cercano if ( C ! = NIL && C -> color == RED ) // no se considera negro goto D_case_5 ; // C rojo && S + D negro D_case_4 : // P rojo && S negro && C + D considerado negro: S -> color = RED ; P -> color = NEGRO ; volver ; // eliminación completa
Caso Delete 5: El hermano S es negro, S ‘s cerca niño C es rojo, y S ‘distante niño 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. Se intercambian los colores de S y C. Todos los caminos todavía tienen el mismo número de nodos negros, pero ahora N tiene un hermano negro cuyo hijo distante es rojo, por lo que la configuración es adecuada para el caso 6. Ni N ni su padre P se ven afectados por esta transformación, y P puede ser rojo. o negro.
D_case_5 : // C rojo && S + D negro: RotateDir ( S , 1 - dir ); // S nunca es la raíz S -> color = RED ; C -> color = NEGRO ; D = S ; S = C ; // ahora: D rojo && S negro // caen a D_case_6
Elimine el caso 6: el hermano S es negro, el hijo distante D de S es rojo. Después de un -rotation en P el hermano S se convierte en la matriz de P y S ‘s distante niño D . Los colores de P y S se intercambian y D se vuelve negro. El subárbol todavía tiene el mismo color en su raíz, es decir, rojo o negro (dir
en el diagrama), que se refiere al mismo color antes y después de la transformación. De esta forma se conserva la propiedad 3 (Ambos hijos de cada nodo rojo son negros). Los caminos en el subárbol que no pasan por N (iow que pasan por D y el nodo 3 en el diagrama) pasan por el mismo número de nodos negros que antes, pero N ahora tiene un antepasado negro adicional: o P se ha vuelto negro, o era black y S se agregaron como abuelos negros. Por lo tanto, las rutas que pasan por N pasan a través de un nodo negro adicional, de modo que la propiedad 4 (Todas las rutas desde cualquier nodo dado a sus nodos hoja contienen el mismo número de nodos negros) se restaura y el árbol total tiene forma RB.
D_case_6 : // D rojo && S negro: RotateDirRoot ( T , P , dir ); // P puede ser la raíz S -> color = P -> color ; P -> color = NEGRO ; D -> color = NEGRO ; volver ; // eliminación completa } // fin de RBdelete2
Debido a que el algoritmo transforma la entrada sin usar una estructura de datos auxiliar y usando solo una pequeña cantidad de espacio de almacenamiento adicional para las variables auxiliares, está en su lugar .
Las rotaciones ocurren en los casos 3, 5 y 6, todos fuera del bucle. Por lo tanto, se producen como máximo tres rotaciones en total.
En el algoritmo anterior, todos los casos están encadenados en orden, excepto en el caso 1, que es el único caso en el que la implementación iterativa se repite de manera efectiva. En ese caso, el problema de la reparación aumenta un nivel cada vez. Por lo tanto, no más de ocurrirán iteraciones (donde es la altura del árbol). Debido a que la probabilidad de escalada disminuye exponencialmente con cada iteración, el costo de eliminación es constante en promedio, de hecho, se amortiza constante .
Mehlhorn & Sanders señalan: "Los árboles AVL no soportan costos de eliminación amortizados constantes ", pero los árboles rojo-negro sí. [17] : 165,158
Prueba de límites
Para hay un árbol rojo-negro de altura con
- nodos
y no hay un árbol rojo-negro de esta altura con menos nudos, por lo tanto, es mínimo .
Su altura negra es
- Prueba
Para que un árbol rojo-negro de cierta altura tenga un número mínimo de nodos, debe tener exactamente un camino más largo con el número máximo de nodos rojos, para lograr una altura máxima de árbol con una altura mínima de negro. Además de esta ruta, todos los demás nodos deben ser negros. [15] : 444 Bosquejo de prueba Si se quita un nodo de este árbol, pierde altura o alguna propiedad RB.
El árbol de altura RB con raíz roja es mínima. Esto está de acuerdo con
Un árbol RB mínimo (RB h en la figura 4) de alturaTiene dos hijos de diferente altura. El niño más alto 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 niño es un árbol binario perfecto de altura (negra). teniendo nodos negros. Entonces el número de nodos es por inducción.
(niño superior) | (raíz) | (segundo hijo) | ||||||||
Resultando en | ||||||||||
. ■ |
La gráfica de la funciónes convexo y lineal por partes con puntos de corte en dónde La función se ha tabulado como A027383 ( h –1) para (secuencia A027383 en la OEIS ).
- Resolviendo la función para
La desigualdad lleva a eso, por extraño , lleva a
- ,
cuyos rendimientos
para todos (pares e impares). Entonces está en el intervalo
(árbol binario perfecto) | (árbol mínimo rojo-negro) |
con como el número de nodos. [30]
- Conclusión
Un árbol rojo-negro con nodos (llaves) tiene una altura
Establecer operaciones y operaciones masivas
Además de las operaciones de inserción, eliminación y búsqueda de un solo elemento, se han definido varias operaciones de conjuntos en árboles rojo-negro: unión , intersección y diferencia de conjuntos . Luego, se pueden implementar operaciones masivas rápidas en inserciones o eliminaciones basadas en estas funciones establecidas. Estas operaciones de conjunto se basan en dos operaciones auxiliares, Split y Join . Con las nuevas operaciones, la implementación de árboles rojo-negro puede ser más eficiente y altamente paralelizable. [31] Esta implementación permite una raíz roja.
- Unir : La función Unir está en dos árboles rojo-negro 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 de t 1 , t 2 y k .
- Si los dos árboles tienen la misma altura negra, Join simplemente crea un nuevo nodo con el subárbol izquierdo t 1 , la raíz k y el subárbol derecho t 2 . Si tanto t 1 como t 2 tienen raíz negra, establezca k en rojo. De lo contrario, k se pone en negro.
- Si las alturas de negro son desiguales, suponga que t 1 tiene una altura de negro mayor que t 2 (el otro caso es simétrico). Join sigue la columna derecha de t 1 hasta un nodo negro c , que se equilibra con t 2 . En este punto, se crea un nuevo nodo con el hijo izquierdo c , la raíz k (establecida en rojo) y el hijo derecho t 2 para reemplazar 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 de doble rojo se propaga a la raíz, la raíz se establece en negro, restaurando las propiedades. El costo de esta función es la diferencia de las alturas de negro entre los dos árboles de entrada.
- Dividir : Para dividir un árbol rojo-negro en dos árboles más pequeños, los más pequeños que la clave x y los más grandes que la clave x , primero dibuje un camino 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 de la izquierda, 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 , orden de la altura del árbol. Este algoritmo en realidad no tiene nada que ver con ninguna propiedad especial de un árbol rojo-negro, y puede usarse en cualquier árbol con una operación de unión , como un árbol AVL .
El algoritmo de unión es el siguiente:
función joinRightRB (T L , k, T R ) si r (T L ) = ⌊r (T L ) / 2⌋ × 2: return Node (T L , ⟨k, red⟩, T R ) else (L ', ⟨K ', c'⟩, R') = exponer (T L ) T '= Nodo (L', ⟨k ', c'⟩, joinRightRB (R', k, T R ) si (c '= negro) y (T'.right.color = T'.right.right.color = rojo): T'.right.right.color = negro; return rotateLeft (T ') else return T'función joinLeftRB (T L , k, T R ) / * simétrico para joinRightRB * /función join (T L , k, T R ) si ⌊r (T L ) / 2⌋> ⌊r (T R ) / 2⌋ × 2: T '= joinRightRB (T L , k, T R ) si (T'.color = red) y (T'.right.color = red): T'.color = negro volver T ' de lo contrario, si ⌊r (T R ) / 2⌋> ⌊r (T L ) / 2⌋ × 2 / * simétrico * / else if (T L .color = negro) y (T R .color = negro) Nodo (T L , ⟨k, red⟩, T R ) más Nodo (T L , ⟨k, black⟩, T R )
Aquí de un nodo significa el doble de la altura negra de un nodo negro y el doble de la altura negra de un nodo rojo. exponer (v) = (l, ⟨k, c⟩, r) significa extraer un nodo de árbolhijo dejado , la clave del nodo , el color del nodo y el niño adecuado . Node (l, ⟨k, c⟩, r) significa crear un nodo de hijo izquierdo, clave , color y niño correcto .
El algoritmo de división es el siguiente:
función split (T, k) if (T = nil) return (nil, false, nil) (L, (m, c), R) = exponer (T) si (k = m) devuelve (L, verdadero, R) si (k(L ', b, R') = dividir (L, k) return (L ', b, join (R', m, R)) si (k> m) (L ', b, R') = dividir (R, k) volver (unirse (L, m, L '), b, R))
La unión de dos árboles de color rojo-negro T 1 y T 2 conjuntos que representan A y B , es un árbol rojo-negro t que representa A ∪ B . La siguiente función recursiva calcula esta unión:
unión de funciones (t 1 , t 2 ): si t 1 = nil: devuelve t 2 si t 2 = nil: devuelve t 1 t < , t > ← split t 2 en t 1 .root return join (t 1 .root, unión (izquierda (t 1 ), t < ), unión (derecha (t 1 ), t > ))
Aquí, se supone que Split devuelve dos árboles: uno que sostiene las teclas menos su tecla de entrada, otro que sostiene las teclas mayores. (El algoritmo no es destructivo , pero también existe una versión destructiva in situ).
El algoritmo de intersección o diferencia es similar, pero requiere la rutina auxiliar Join2 que es la misma que Join pero sin la tecla del medio. Según las nuevas funciones de unión, intersección o diferencia, se puede insertar o eliminar una o varias teclas del árbol rojo-negro. Dado que Split llama a Join, pero no se ocupa de los criterios de equilibrio de los árboles rojo-negro directamente, esta implementación se suele denominar implementación "basada en uniones" .
La complejidad de cada unión, intersección y diferencia es para dos árboles de tamaño rojo-negro y . Esta complejidad es óptima en términos del número de comparaciones. Más importante aún, dado que las llamadas recursivas a unión, intersección o diferencia son independientes entre sí, se pueden ejecutar en paralelo con una profundidad paralela. . [31] Cuando, la implementación basada en uniones tiene el mismo gráfico acíclico dirigido computacionalmente (DAG) que la inserción y eliminación de un solo elemento si la raíz del árbol más grande se usa para dividir el árbol más pequeño.
Algoritmos paralelos
Los algoritmos paralelos para construir árboles rojo-negro a partir de listas ordenadas de elementos pueden ejecutarse en tiempo constante o tiempo, dependiendo del modelo de computadora, si el número de procesadores disponibles es asintóticamente proporcional al número de elementos donde . También se conocen algoritmos paralelos de búsqueda, inserción y eliminación rápidas. [32]
Los algoritmos basados en uniones para árboles rojo-negro son paralelos para operaciones masivas, incluyendo unión, intersección, construcción, filtro, reducción de mapa, etc.
Operaciones masivas paralelas
Las operaciones básicas como la inserción, eliminación o actualización se pueden paralelizar mediante la definición de operaciones que procesan grandes cantidades de elementos múltiples. También es posible procesar bultos con varias operaciones básicas, por ejemplo, los bultos pueden contener elementos para insertar y también elementos para eliminar del árbol.
Los algoritmos para operaciones masivas no solo se aplican al árbol rojo-negro, sino que también se pueden adaptar a otras estructuras de datos de secuencia ordenadas, como el árbol 2–3 , el árbol 2–3–4 y (a, b) - árbol . 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 .
Basado en uniones
Este enfoque se puede aplicar a cada estructura de datos de secuencia ordenada que admita operaciones de unión y división eficientes. [33] La idea general es dividir y en varias partes y realice las inserciones en estas partes en paralelo.
- Primero el grueso de elementos a insertar tiene que ser ordenados.
- Después de eso, el algoritmo se divide dentro partes de tamaños aproximadamente iguales.
- Siguiente el árbol tiene que ser dividido en partes en cierto modo, de modo que para cada las siguientes restricciones se mantienen:
- Ahora el algoritmo inserta cada elemento de dentro secuencialmente. Este paso debe realizarse para cada, que se puede hacer hasta procesadores en paralelo.
- 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 dividir asegúrese de que en el Paso 5 los árboles se puedan unir nuevamente y la secuencia resultante esté ordenada.
árbol inicial
dividir I y T
insertar en la división T
articulación
El pseudocódigo muestra una implementación simple de divide y vencerás del algoritmo basado en unión para inserción masiva. Ambas llamadas recursivas se pueden ejecutar en paralelo. La operación de unión que se usa aquí difiere de la versión explicada en este artículo, en su lugar se usa join2 , que pierde el segundo parámetro k.
bulkInsert (T, I, k): I.sort () bulklInsertRec (T, I, k)bulkInsertRec (T, I, k): si k = 1: forall e en I: T.insert (e) else m: = ⌊tamaño (I) / 2⌋ (T 1 , _, T 2 ): = dividir (T, I [m]) bulkInsertRec (T 1 , I [0 .. m], ⌈k / 2⌉) || bulkInsertRec (T 2 , I [m + 1 .. tamaño (I) - 1], ⌊k / 2⌋) T ← join2 (T 1 , T 2 )
Tiempo de ejecución
Clasificación no se considera en este análisis.
#niveles de recursividad | |
T (dividir) + T (unirse) | |
inserciones por hilo | |
T (insertar) | |
T (bulkInsert) con = #procesadores |
Esto se puede mejorar mediante el uso de algoritmos paralelos para dividir y unir. En este caso el tiempo de ejecución es. [34]
Trabaja
# divisiones, #uniones | |
W (dividir) + W (unirse) | |
#insertions | |
W (insertar) | |
W (inserción masiva) |
Canalización
Otro método de paralelizar las operaciones a granel es utilizar un enfoque de canalización . [35] 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 el grueso de elementos a insertar tiene que ser ordenados.
- Para cada elemento en el algoritmo ubica la posición de inserción correspondiente en . Esto se puede hacer en paralelo para cada elemento. desde no se modificará en este proceso. Ahora tiene que dividirse en subsecuencias según la posición de inserción de cada elemento. Por ejemplo es la subsecuencia de que contiene los elementos cuya posición de inserción estaría a la izquierda del nodo .
- El elemento medio de cada subsecuencia será insertado en como un nuevo nodo . Esto se puede hacer en paralelo para cada ya que por definición la posición de inserción de cada es único. Si contiene elementos a la izquierda oa la derecha de , esos estarán contenidos en un nuevo conjunto de subsecuencias como o .
- Ahora posiblemente contiene hasta dos nudos rojos consecutivos al final de los caminos que forman la raíz a las hojas, que necesita ser reparada. Tenga en cuenta que, durante la reparación, la posición de inserción de los elementosdeben actualizarse, si los nodos correspondientes se ven afectados por rotaciones.
Si dos nodos tienen diferentes antepasados negros más cercanos, se pueden reparar en paralelo. Dado que como máximo cuatro nodos pueden tener el mismo antepasado negro más cercano, los nodos del nivel más bajo pueden repararse en un número constante de pasos paralelos.
Este paso se aplicará sucesivamente a los niveles de negro anteriores hasta que está totalmente reparado. - Los pasos 3 a 5 se repetirán en las nuevas subsecuencias hasta que esta vacio. En este punto cada elementoha sido insertado. 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 por los niveles negros del árbol, se pueden paralelizar en una tubería. Una vez que una etapa ha terminado de procesar un nivel de negro, la siguiente etapa puede avanzar y continuar en ese nivel.
Árbol inicial
Encuentra posiciones de inserción
La etapa 1 inserta elementos
La etapa 1 comienza a reparar los nodos
Etapa 2 inserta elementos
La etapa 2 comienza a reparar los nodos
Etapa 3 inserta elementos
La etapa 3 comienza a reparar los nodos.
La etapa 3 continúa reparando los nodos
Tiempo de ejecución
Clasificación no se considera en este análisis. También, se supone que es menor que , de lo contrario, sería más suficiente construir el árbol resultante desde cero.
T (encontrar la posición de inserción) | |
# etapas | |
T (insertar) + T (reparar) | |
T (bulkInsert) con ~ #procesadores | |
Trabaja
W (buscar posiciones de inserción) | |
# inserciones, # reparaciones | |
W (insertar) + W (reparar) | |
W (inserción masiva) | |
Cultura popular
Un árbol rojo-negro fue referenciado correctamente en un episodio de Missing [36] como lo señaló Robert Sedgewick en una de sus conferencias: [37]
Jess : Era la puerta roja de nuevo.
Pollock : Pensé que la puerta roja era el contenedor de almacenamiento.
Jess : Pero ya no era rojo, era negro.
Antonio : ¿Entonces qué significa que el rojo se convierta en negro?
Pollock : déficit presupuestario, tinta roja, tinta negra.
Antonio : Podría ser de un árbol de búsqueda binario. El árbol rojo-negro rastrea cada camino simple desde un nodo hasta una hoja descendiente que tiene el mismo número de nodos negros.
Jess : ¿Eso te ayuda con las damas?
Ver también
- Lista de estructuras de datos
- Estructura de datos de árbol
- Rotación de árboles
- Árbol AA , una variación del árbol rojo-negro
- Árbol AVL
- B-tree ( árbol 2-3 , 2-3-4 árbol , árbol B + , B * -tree , UB-árbol )
- Árbol de chivo expiatorio
- Árbol de extensión
- Árbol en T
- Árbol WAVL
Referencias y notas
- ^ a b c d e f James Paton. "Árboles rojo-negros" .
- ^ a b Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Árboles rojo-negros". Introducción a los algoritmos (segunda ed.). Prensa del MIT. págs. 273 –301. ISBN 978-0-262-03293-3.
- ^ Morris, John (1998). "Árboles rojo-negros" . Estructuras de datos y algoritmos .
- ^ Rudolf Bayer (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 ed.). Sams Publishing. pag. 323. ISBN 978-0534376680.
- ^ a b Leonidas J. Guibas y Robert Sedgewick (1978). "Un marco dicromático para árboles equilibrados". Actas del XIX Simposio anual sobre fundamentos de la informática . págs. 8-21. doi : 10.1109 / SFCS.1978.3 .
- ^ "Árboles negros rojos" . eternamenteconfuzzled.com . Archivado desde el original el 27 de septiembre de 2007 . Consultado el 2 de septiembre de 2015 .
- ^ Robert Sedgewick (2012). BST rojo-negro . Coursera.
Mucha gente pregunta por qué usamos el nombre rojo-negro. Bueno, inventamos esta estructura de datos, esta forma de ver los árboles equilibrados, en Xerox PARC, que era el hogar de la computadora personal y muchas otras innovaciones con las que vivimos hoy, ingresando [sic] interfaces gráficas de usuario, ethernet y programaciones orientadas a objetos. [sic] 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 una impresora láser a color cercana que pudiera imprimir cosas en color y fuera 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 equilibrados simplificados" . En Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue (eds.). Algoritmos y estructuras de datos (procedimientos). Apuntes de conferencias en Ciencias de la Computación. 709 . Springer-Verlag Berlín 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 . Archivado desde el original (PS) el 26 de septiembre de 2007 . Consultado el 13 de mayo de 2007 .
- ^ 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 inclinados a la izquierda" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ a b c Sedgewick, Robert; Wayne, Kevin (2011). Algoritmos (4ª ed.). Addison-Wesley Professional. ISBN 978-0-321-57351-3.
- ^ Un b c Nota que la disyunción
U == NIL || U->color == BLACK // considered black
y la conjunciónU != NIL && U->color == RED // not considered black
está no evaluados en total siU == NIL
. Entonces en ambos casosU->color
no se toca (ver Evaluación de cortocircuito ).
A lo largo de la primera iteración, estos nodos en cuestión no existen (son hojas NULAS y se consideran negros ), mientras que en las iteraciones más altas su altura de negro es ≥ 1. - ^ a b c d 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.
- ^ a b Cormen, Thomas ; Leiserson, Charles ; Rivest, Ronald ; Stein, Clifford (2009). "13. Árboles rojo-negros". Introducción a los algoritmos (3ª ed.). Prensa del MIT . pp. 308 -309. ISBN 978-0-262-03384-8.
- ^ Usando la definición de orden de Knuth: el número máximo de niños
- ^ Sedgewick, Robert (1998). Algoritmos en C ++ . Addison-Wesley Professional. págs. 565 –575. ISBN 978-0-201-35088-3.
- ^ "La implementación de epoll (1)" . Septiembre de 2014.
- ^ Pfaff 2004
- ^ a b http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
- ^ http://www.cs.princeton.edu/courses/archive/fall08/cos226/lectures/10BalancedTrees-2x2.pdf
- ^ Demaine, ED; Harmon, 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.
- ^ Lo importante de estas rotaciones de árboles es que conservan 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 árbol de búsqueda binaria y rutinas de biblioteca de árbol equilibrado
- ^ Se han colocado rotaciones antes de volver a colorear por razones de claridad. Pero los dos se desplazan, por lo que es libre de mover la rotación hacia la cola .
- ^ La igualdad en el límite superior se mantiene para los árboles RB mínimos RB 2 k de altura uniforme con nodos y solo para esos. Entonces la desigualdad es marginalmente más precisa que la generalizadapor ejemplo, en Cormen p. 264.
Además, estos árboles son árboles binarios que admiten un solo color que se ajusta a las propiedades 1 a 4 de RB. Pero existen otros árboles de este tipo, por ejemplo, añadir un nodo hijo a una hoja negra siempre la obliga a rojo. (Un árbol RB mínimo de altura impar permite cambiar el color de la raíz de rojo a negro). - ^ a b Blelloch, Guy E .; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets" (PDF) , Simposio sobre algoritmos y arquitecturas paralelas, Proc. de 28a ACM Symp. 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, S2CID 2897793.
- ^ Park, Heejin; Park, Kunsoo (2001). "Algoritmos paralelos para árboles rojo-negro". Informática Teórica . 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 los elementos se ejecutan en tiempo con procesadores en CRCW PRAM y se ejecuta en tiempo con procesadores en el EREW PRAM.
- ^ Sanders, Peter (2019). Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (eds.). Estructuras de datos y algoritmos secuenciales y paralelos: la caja de herramientas básica . Libros electrónicos Springer. Cham: Springer. págs. 252-253. doi : 10.1007 / 978-3-030-25209-0 . ISBN 9783030252090. S2CID 201692657 .
- ^ Akhremtsev, Yaroslav; Sanders, Peter (2016). "Operaciones paralelas rápidas en árboles de búsqueda". HiPC 2016, la 23a Conferencia Internacional IEEE sobre Computación, Datos y Análisis de Alto Rendimiento, Hyderabad, India, del 19 al 22 de diciembre . IEEE, Piscataway (Nueva Jersey): 291–300. arXiv : 1510.05433 . Código bibliográfico : 2015arXiv151005433A . ISBN 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.
- ^ Missing (serie de televisión canadiense) . Red A , W (Canadá); Lifetime (Estados Unidos).
- ^ Robert Sedgewick (2012). B-Trees . Coursera . 10:37 minutos.
Así que no solo hay algo de emoción en ese diálogo, sino que también es técnicamente correcto que no se encuentra a menudo con las matemáticas en la cultura popular de la informática. Un árbol rojo-negro rastrea cada camino simple desde un nodo hasta una hoja descendiente con el mismo número de nodos negros que acertaron.
Otras lecturas
- Mathworld: árbol rojo-negro
- Universidad Estatal de San Diego: CS 660: notas de árboles rojo-negro , por Roger Whitney
- Pfaff, Ben (junio de 2004). "Análisis de rendimiento de BST en software de sistema" (PDF) . Universidad de Stanford .
enlaces externos
- [ https://github.com/hp685/rbtree/ Implementación de árbol rojo-negro en C
- Una implementación completa y funcional en C
- Conferencia de OCW MIT del Prof.Erik Demaine sobre Árboles Negros Rojos -
- Visualización de inserción de árbol de búsqueda binaria en YouTube : visualización de inserciones de datos aleatorias y preordenados, en árboles de búsqueda binaria elementales y árboles rojo-negro inclinados a la izquierda
- Un intrusivo árbol rojo-negro escrito en C ++
- BST rojo-negro en 3.3 árboles de búsqueda equilibrados
- Demostración de BST rojo-negro