Árbol rojo-negro

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 2 de noviembre de 2019; las comprobaciones requieren 32 ediciones .

árbol rojo-negro

Tipo de

árbol de búsqueda

año de invención

1972

Autor

Rodolfo Bayer

Complejidad en los símbolos O

	Promedio	Lo peor
Consumo de memoria	En)	En)
Búsqueda	O (registro n)	O (registro n)
Insertar	O (registro n)	O (registro n)
Eliminación	O (registro n)	O (registro n)

Archivos multimedia en Wikimedia Commons

El árbol rojo-negro ( eng. árbol rojo-negro , árbol RB ) es uno de los tipos de árboles de búsqueda binarios autoequilibrados que garantiza un crecimiento logarítmico de la altura del árbol a partir del número de nodos y le permite realizar rápidamente un árbol de búsqueda básico operaciones: agregar, eliminar y encontrar un nodo. El equilibrio se logra mediante la introducción de un atributo adicional del nodo del árbol: "colores". Este atributo puede tomar uno de dos valores posibles: "negro" o "rojo".

El inventor alemán Rudolf Bayer es considerado el inventor del árbol rojo-negro . El nombre “árbol rojo-negro” se le dio a la estructura de datos en un artículo de L. Gimbas y R. Sedgwick (1978). Según Gimbas, usaban bolígrafos de dos colores [1] . Según Sedgwick, el rojo se veía mejor en una impresora láser [1] [2] .

El árbol rojo-negro se utiliza para organizar datos comparables, como fragmentos de texto o números. Los nodos de hoja de los árboles rojo-negro no contienen datos, por lo que no requieren asignación de memoria; basta con escribir un puntero nulo como un puntero al hijo en el nodo antepasado. Sin embargo, en algunas implementaciones, se pueden usar nodos hoja explícitos para simplificar el algoritmo.

El principio de organización

Un árbol rojo-negro es un árbol de búsqueda binario en el que cada nodo tiene un atributo de color . Donde:

Un nodo puede ser rojo o negro y tiene dos hijos;
La raíz suele ser negra. Esta regla tiene poco efecto sobre el rendimiento del modelo, ya que el color de la raíz siempre se puede cambiar de rojo a negro;
Todas las hojas que no contienen datos son negras.
Ambos hijos de cada nodo rojo son negros.
Cualquier ruta simple desde un nodo antepasado hasta un nodo hoja secundario contiene el mismo número de nodos negros.

Debido a estas restricciones, el camino desde la raíz hasta la hoja más lejana no es más del doble que hasta la más cercana, y el árbol está aproximadamente equilibrado. Las operaciones de inserción, eliminación y búsqueda requieren, en el peor de los casos, un tiempo proporcional a la longitud del árbol, lo que permite que los árboles rojo-negro sean más eficientes en el peor de los casos que los árboles de búsqueda binarios convencionales.

Para entender cómo funciona esto, es suficiente considerar el efecto de las propiedades 4 y 5 juntas. Sea B el número de nodos negros desde la raíz hasta una hoja para un árbol T rojo-negro. Entonces, el camino más corto posible a cualquier hoja contiene B nodos, y todos son negros. Se puede construir una ruta posible más larga al incluir los nodos rojos. Sin embargo, debido a la cláusula 4, el árbol no puede tener dos nodos rojos seguidos, y de acuerdo con las cláusulas 2 y 3, el camino comienza y termina con un nodo negro. Por lo tanto, el camino más largo posible consta de 2B-1 nodos, alternativamente rojos y negros.

Si permite que un nodo que no sea hoja tenga menos de dos elementos secundarios y que un nodo hoja contenga datos, el árbol conserva las propiedades básicas, pero los algoritmos para trabajar con él se vuelven más complicados. Por lo tanto, el artículo trata solo de "nodos de hoja ficticios", que no contienen datos y simplemente sirven para indicar dónde termina el árbol. Estos nudos pueden omitirse en algunas ilustraciones. Del ítem 5, también se deduce que los descendientes del nodo rojo pueden ser dos nodos intermedios negros, o dos hojas negras, y teniendo en cuenta los ítems 3 y 4, que si uno de los descendientes del nodo negro es un nodo hoja , entonces el segundo debe ser también una hoja o el diseño descrito anteriormente de una hoja roja y dos.

También en la literatura hay una interpretación en la que no los nodos en sí, sino los bordes que conducen a ellos están pintados en colores rojo / negro, pero esto no es de gran importancia para comprender el principio de su funcionamiento.

Analogía del árbol B con el parámetro 4

Un árbol rojo-negro tiene una estructura similar a un árbol B con parámetro 4, en el que cada nodo puede contener de 1 a 3 valores y, en consecuencia, de 2 a 4 punteros a los niños. En tal árbol B, cada nodo contendrá solo un valor, correspondiente al valor del nodo negro del árbol rojo-negro, con valores opcionales antes y/o después en el mismo nodo, los cuales corresponden a los nodos rojos equivalentes del árbol rojo-negro.

Una forma de ver esta equivalencia es "elevar" los nodos rojos en la representación gráfica del árbol rojo-negro para que queden alineados horizontalmente con sus ancestros de nodos negros, formando una página. En un árbol B, o una representación gráfica modificada de un árbol rojo-negro, todos los nodos de hojas tienen la misma profundidad.

Este tipo de árbol B es más general que un árbol rojo-negro, aunque, como puede ver, se pueden obtener varios árboles rojo-negro de uno de esos árboles B con parámetro 2. Si una página de árbol B contiene solo un valor, el nodo es negro y tiene dos hijos. Si la página contiene tres valores, entonces el nodo central es negro y cada uno de sus vecinos es rojo. Sin embargo, si la página contiene dos valores, cualquier nodo puede volverse negro en el árbol rojo-negro (en cuyo caso, el segundo será rojo).

Trabajando con árboles rojo-negros

Los árboles rojo-negro son uno de los árboles de búsqueda de autoequilibrio más utilizados en la práctica. En particular, los contenedores de conjuntos y mapas en la mayoría de las implementaciones de la biblioteca C++ STL [3] , la clase Java TreeMap [4] , así como muchas otras implementaciones de matrices asociativas en varias bibliotecas, se basan en árboles rojo-negro.

Los árboles rojo-negros son más populares que los árboles perfectamente equilibrados. en el último, se pueden gastar demasiados recursos en eliminar del árbol y mantener el equilibrio necesario. Después de la inserción o eliminación, se requiere una operación de cambio de color, que requiere (O(log n ) u O(1)) cambios de color (que es bastante rápido en la práctica) y no más de tres rotaciones del árbol (no más de dos para la inserción ). Aunque la inserción y la eliminación son complejas, siguen siendo O(log n ) laboriosas.

Insertar

Se agrega un nuevo nodo en el árbol rojo-negro en lugar de una de las hojas, de color rojo, y se le adjuntan dos hojas (dado que las hojas son una abstracción que no contiene datos, agregarlas no requiere una operación adicional) . Lo que sucede a continuación depende del color de los nodos cercanos. Darse cuenta de:

La propiedad 3 (Todas las hojas son negras) siempre es verdadera.
La propiedad 4 (Ambos hijos de cualquier nodo rojo son negros) solo se puede violar agregando un nodo rojo, cambiando el color de un nodo negro a rojo o girándolo.
La propiedad 5 (todas las rutas desde cualquier nodo a los nodos de hoja contienen la misma cantidad de nodos negros) solo se puede violar agregando un nodo negro, cambiando el color de un nodo rojo a negro (o viceversa) o rotando.

Nota : La letra N denotará el nodo actual (coloreado en rojo). Primero, es el nuevo nodo que se inserta, pero este procedimiento se puede aplicar recursivamente a otros nodos (ver caso 3). P denotará al ancestro de N , G denotará al abuelo de N y U denotará al tío (el nodo que tiene un padre común con el nodo P ). Tenga en cuenta que en algunos casos los roles de los nodos pueden cambiar, pero en cualquier caso, cada designación representará el mismo nodo que al principio. Cualquier color representado en la figura se asume en este caso o se obtiene a partir de otras consideraciones.

Cada caso está cubierto con ejemplos de código C. Una definición de estructura de nodo podría verse así:

enum node_colors { ROJO , NEGRO }; nodo de estructura { struct nodo * padre , * izquierda , * derecha ; enumeración node_colors color ; clave de entrada ; _ };

El tío y el abuelo del nodo actual se pueden encontrar usando las funciones:

nodo de estructura * abuelo ( struct nodo * n ) { si (( n != NULL ) && ( n -> padre != NULL )) volver n -> padre -> padre ; más devuelve NULL ; } nodo de estructura * tío ( struct nodo * n ) { nodo de estructura * g = abuelo ( n ); si ( g == NULL ) devuelve NULL ; // Sin abuelo significa que no hay tío si ( n -> padre == g -> izquierda ) volver g -> derecha ; más volver g -> izquierda ; }

La rotación izquierda y derecha del árbol se puede hacer así:

vacío rotar_izquierda ( estructura nodo * n ) { nodo de estructura * pivote = n -> derecha ; pivote -> padre = n -> padre ; /* posiblemente haciendo pivotar la raíz del árbol */ if ( n -> padre != NULL ) { if ( n -> padre -> izquierda == n ) n -> padre -> izquierda = pivote ; más n -> padre -> derecha = pivote ; } n -> derecha = pivote -> izquierda ; if ( pivote -> izquierda != NULL ) pivote -> izquierda -> padre = n ; n -> padre = pivote ; pivote -> izquierda = n ; } vacío rotar_derecha ( estructura nodo * n ) { nodo de estructura * pivote = n -> izquierda ; pivote -> padre = n -> padre ; /* posiblemente haciendo pivotar la raíz del árbol */ if ( n -> padre != NULL ) { if ( n -> padre -> izquierda == n ) n -> padre -> izquierda = pivote ; más n -> padre -> derecha = pivote ; } n -> izquierda = pivote -> derecha ; if ( pivote -> derecha != NULL ) pivote -> derecha -> padre = n ; n -> padre = pivote ; pivote -> derecha = n ; }

Caso 1: El nodo actual N está en la raíz del árbol. En este caso, se vuelve a pintar de negro para mantener verdadera la Propiedad 2 (la raíz es negra). Dado que esta acción agrega un nodo negro a cada ruta, la propiedad 5 (todas las rutas desde cualquier nodo dado hasta los nodos hoja contienen el mismo número de nodos negros) no se viola.

vacío insert_case1 ( estructura nodo * n ) { si ( n -> padre == NULL ) n -> color = NEGRO ; más insertar_caso2 ( n ); }

Caso 2: el padre P del nodo actual es negro, es decir, la propiedad 4 (ambos hijos de cada nodo rojo son negros) no se viola. En este caso, el árbol sigue siendo correcto. La propiedad 5 (Todas las rutas de cualquier nodo dado a los nodos de hoja contienen el mismo número de nodos negros) no se viola porque el nodo actual N tiene dos hijos de hoja negros, pero dado que N es rojo, la ruta a cada uno de estos hijos contiene el mismo número de nodos negros, que es la ruta a la hoja negra que fue reemplazada por el nodo actual, por lo que la propiedad sigue siendo verdadera.

vacío insert_case2 ( estructura nodo * n ) { if ( n -> padre -> color == NEGRO ) volver ; /* El árbol sigue siendo válido */ más insert_case3 ( n ); } Nota: En los siguientes casos, se supone que N tiene un abuelo G , ya que su padre P es rojo, y si fuera una raíz, se colorearía de negro. Así N también tiene un tío U , aunque puede ser un nodo hoja en los casos 4 y 5.

Caso 3: si tanto el padre P como el tío U son rojos, ambos pueden volverse a colorear de negro y el abuelo G se vuelve rojo (para preservar la propiedad 5 (todas las rutas desde cualquier nodo dado a los nodos hoja contienen la misma cantidad de nodos negros)) . Ahora el nodo rojo actual N tiene un padre negro. Dado que cualquier ruta a través del padre o del tío debe pasar por el abuelo, la cantidad de nodos negros en estas rutas no cambiará. Sin embargo, el abuelo de G ahora puede violar las propiedades 2 (la raíz es negra) o 4 (ambos hijos de cada nodo rojo son negros) (la propiedad 4 puede violarse porque el padre de G puede ser rojo). Para solucionar esto, todo el procedimiento se realiza recursivamente en G del Caso 1.

vacío insert_case3 ( estructura nodo * n ) { nodo de estructura * u = tío ( n ), * g ; if (( u != NULL ) && ( u -> color == ROJO )) { // && (n->padre->color == ROJO) La segunda condición se prueba en insert_case2, es decir, el padre ya es rojo. n -> padre -> color = NEGRO ; u -> color = NEGRO ; g = abuelo ( n ); g -> color = ROJO ; insert_case1 ( g ); } más { insert_case4 ( n ); } } Nota: En los casos restantes, se supone que el padre P es el hijo izquierdo de su antepasado. Si este no es el caso, debe cambiar de izquierda a derecha . Los ejemplos de código se encargarán de eso.

Caso 4: El padre de P es rojo, pero el tío de U es negro. Además, el nodo actual N es el hijo derecho de P , y P a su vez es el hijo izquierdo de su antecesor G . En este caso, se puede realizar una rotación de árbol, que cambia los roles del nodo actual N y su antecesor P. Luego, para el nodo padre anterior P en la estructura actualizada, use el caso 5 porque la Propiedad 4 (Ambos hijos de cualquier nodo rojo son negros) todavía se viola. La rotación hace que algunas rutas (en el subárbol etiquetado como "1" en el diagrama) pasen por el nodo N , lo que no era el caso antes. Esto también hace que algunas rutas (en el subárbol etiquetado como "3") no pasen por el nodo P. Sin embargo, ambos nodos son rojos, por lo que la propiedad 5 (todas las rutas desde un nodo determinado hasta los nodos hoja contienen el mismo número de nodos negros) no se viola con la rotación. Sin embargo, la Propiedad 4 todavía se viola, pero ahora el problema se reduce al Caso 5.

vacío insert_case4 ( estructura nodo * n ) { nodo de estructura * g = abuelo ( n ); if (( n == n -> padre -> derecha ) && ( n -> padre == g -> izquierda )) { rotar_izquierda ( n -> padre ); n = n -> izquierda ; /* * rotar_izquierda se puede hacer de la siguiente manera, dado que ya existe *g = abuelo(n) * * struct node *saved_p=g->left, *saved_left_n=n->left; * g->izquierda=n; * n->izquierda=p guardado; * guardado_p->derecha=guardado_izquierda_n; * */ } else if (( n == n -> padre -> izquierda ) && ( n -> padre == g -> derecha )) { rotar_derecha ( n -> padre ); n = n -> derecho ; /* * "rotate_right" se puede hacer de la siguiente manera, dado que ya existe *g = grandparent(n) * * struct node *saved_p=g->right, *saved_right_n=n->right; *g->derecha=n; * n->right=guardado_p; * guardado_p->izquierda=guardado_derecho_n; * */ } insert_case5 ( n ); }

Caso 5: el padre P es rojo pero el tío U es negro, el nodo actual N es el hijo izquierdo de P y P es el hijo izquierdo de G. En este caso , el árbol es rotado por G. El resultado es un árbol en el que el anterior padre P ahora es el padre tanto del nodo actual N como del antiguo abuelo G . Se sabe que G es negro, ya que su antiguo hijo P no podría ser rojo de otro modo (sin violar la Propiedad 4). Entonces los colores de P y G cambian y como resultado el árbol satisface la Propiedad 4 (Ambos hijos de cualquier nodo rojo son negros). La propiedad 5 (Todos los caminos desde cualquier nodo dado hasta los nodos hoja contienen el mismo número de nodos negros) también sigue siendo cierta, ya que todos los caminos que pasan por cualquiera de estos tres nodos antes pasaban por G , por lo que ahora todos pasan por P. En cada caso, de estos tres nodos, solo uno es de color negro.

vacío insert_case5 ( estructura nodo * n ) { nodo de estructura * g = abuelo ( n ); n -> padre -> color = NEGRO ; g -> color = ROJO ; if (( n == n -> padre -> izquierda ) && ( n -> padre == g -> izquierda )) { rotar_derecha ( g ); } más { rotar_izquierda ( g ); } }

Eliminación

Al eliminar un nodo con dos elementos secundarios que no son hojas en un árbol de búsqueda binaria normal, buscamos el elemento más grande en su subárbol izquierdo o el elemento más pequeño en su subárbol derecho y movemos su valor al nodo que se eliminará. Luego eliminamos el nodo del que copiamos el valor. Copiar un valor de un nodo a otro no viola las propiedades del árbol rojo-negro, ya que la estructura del árbol y los colores de los nodos no cambian. Vale la pena señalar que el nuevo nodo que se elimina no puede tener dos nodos secundarios que no sean hojas a la vez, de lo contrario, no será el elemento más grande/más pequeño. Por lo tanto, resulta que el caso de eliminar un nodo que tiene dos hijos no hoja se reduce al caso de eliminar un nodo que contiene como máximo un nodo hijo no hoja. Por lo tanto, la descripción adicional procederá de la suposición de que el nodo a eliminar tiene como máximo un hijo que no es hoja.

Usaremos la notación M para el nodo a eliminar; denotamos por C al descendiente de M , al que también llamaremos simplemente "su descendiente". Si M tiene un hijo que no es hoja, tómalo como C . De lo contrario, para C tomamos cualquiera de los descendientes de la hoja.

Si M es un nodo rojo, reemplácelo con nuestro hijo C , que por definición debe ser negro. (Esto solo puede suceder cuando M tiene dos hijos hoja, porque si un nodo rojo M tiene un hijo negro que no es hoja en un lado y un hijo hoja en el otro lado, entonces el número de nodos negros en ambos lados será diferente, por lo tanto, el árbol dejará de ser válido. árbol rojo-negro debido a la violación de la propiedad 5.) Todas las rutas a través del nodo que se eliminará simplemente contendrán un nodo rojo menos, el padre y el hijo del nodo que se eliminará deben ser negros, por lo que La Propiedad 3 ("Todas las hojas son negras") y la Propiedad 4 ("Ambos hijos del nodo rojo son negros") aún se mantienen.

Otro caso sencillo es cuando M es negro y C es rojo. Simplemente eliminar un nodo negro violaría la Propiedad 4 ("Ambos hijos de un nodo rojo son negros") y la Propiedad 5 ("Cualquier ruta simple desde un nodo dado a cualquier nodo hoja contiene el mismo número de nodos negros"), pero si vuelva a colorear C negro, ambas propiedades se conservarán.

Un caso difícil es cuando tanto M como C son negros. (Esto solo puede suceder cuando se elimina un nodo negro que tiene dos hijos hoja, porque si un nodo negro M tiene un hijo negro que no es hoja en un lado y un hijo hoja en el otro, entonces el número de nodos negros en ambos lados será diferente y el árbol se convertirá en un árbol rojo-negro inválido porque se viola la propiedad 5). Comenzamos reemplazando el nodo M con su hijo C . Llamaremos a este descendiente (en su nueva posición) N , y su "hermano" (otro descendiente de su nuevo antepasado) - S. (Antes de esto, S era el "hermano" de M .) En las figuras a continuación, también usaremos la notación P para el nuevo antepasado de N (el antepasado antiguo de M ), SL para el hijo izquierdo de S , y S R para el hijo derecho de S ( S no puede ser un nodo hoja, porque si N por nuestra suposición es negro, entonces el subárbol P que contiene N es de altura dos negro y por lo tanto el otro subárbol de P que contiene S también debe ser negro de altura dos, lo que no puede ser el caso cuando S es una hoja).

Nota : En algunos casos, cambiamos los roles y las designaciones de los nodos, pero en cada caso, cualquier designación continúa significando el mismo nodo que al principio del caso. Los colores representados en la figura se suponen por casualidad o se obtienen a partir de otras suposiciones. Blanco significa un color desconocido (ya sea rojo o negro).

Buscaremos un "hermano" usando esta función:

nodo de estructura * hermano ( estructura nodo * n ) { if ( n == n -> padre -> izquierda ) volver n -> padre -> derecho ; más volver n -> padre -> izquierda ; } Nota : para que el árbol permanezca correctamente definido, necesitamos que cada hoja siga siendo una hoja después de todas las transformaciones (para que no tenga hijos). Si el nodo que estamos eliminando tiene un hijo N que no es hoja, es fácil ver que la propiedad se mantiene. Por otro lado, si N es una hoja, entonces, como puede ver en las imágenes o el código, la propiedad también se cumple.

Podemos realizar los pasos anteriores usando el siguiente código, donde la función replace_nodereemplaza childun nodo nen el árbol. Para mayor comodidad, el código de esta sección asume que las hojas nulas están representadas por objetos de nodo reales, no NULL (el código de inserción debería funcionar con la misma representación).

void replace_node ( nodo * n , nodo * hijo ) { hijo -> padre = n -> padre ; if ( n == n -> padre -> izquierda ) { n -> padre -> izquierda = hijo ; } más { n -> padre -> derecho = hijo ; } } vacío delete_one_child ( estructura nodo * n ) { /* * Condición: n tiene como máximo un hijo distinto de cero. */ struct node * child = is_leaf ( n -> right ) ? n -> izquierda : n -> derecha ; replace_node ( n , hijo ); if ( n -> color == NEGRO ) { if ( niño -> color == ROJO ) niño -> color = NEGRO ; más delete_case1 ( hijo ); } libre ( n ); } Nota : si N es una hoja nula y no queremos representar hojas nulas como objetos reales, podemos modificar el algoritmo llamando primero a delete_case1() en su padre (el nodo que eliminamos nen el código anterior) y eliminándolo después que. Podemos hacer esto porque el padre es negro y por lo tanto se comporta como una hoja nula (ya veces se le llama hoja 'fantasma'). Podemos eliminarlo con seguridad, ya que nseguirá siendo una hoja después de todas las operaciones, como se muestra arriba.

Si N y su padre actual son negros, eliminar al padre hará que los caminos que pasan por N tengan un nodo negro menos que los caminos que no pasan por él. Dado que esto viola la propiedad 5 (todas las rutas de cualquier nodo a sus nodos hoja contienen el mismo número de nodos negros), el árbol debe reequilibrarse. Hay varios casos a considerar:

Caso 1: N es una nueva raíz. En este caso, todo está hecho. Hemos eliminado un nodo negro de cada ruta y la nueva raíz es un nodo negro, por lo que se conservan las propiedades.

vacío delete_case1 ( estructura nodo * n ) { si ( n -> padre != NULL ) borrar_caso2 ( n ); } Nota : En los casos 2, 5 y 6, asumimos que N es el hijo izquierdo de su antepasado P. Si es el hijo derecho, la izquierda y la derecha deben intercambiarse en los tres casos. Una vez más, los ejemplos de código tienen esto en cuenta.

Caso 2: S es rojo. En este caso, intercambiamos los colores de P y S , y luego hacemos una rotación a la izquierda alrededor de P , haciendo que S sea el abuelo de N. Tenga en cuenta que P debe ser negro si tiene un niño rojo. El subárbol resultante todavía tiene un nodo negro menos, por lo que aún no hemos terminado con eso. Ahora N tiene un hermano negro y un padre rojo, por lo que podemos pasar a los pasos 4, 5 o 6. (Su nuevo hermano es negro porque fue descendiente de S rojo ).

En lo que sigue, S denotará al nuevo hermano N .

void delete_case2 ( estructura nodo * n ) { nodo de estructura * s = hermano ( n ); if ( s -> color == ROJO ) { n -> padre -> color = ROJO ; s -> color = NEGRO ; if ( n == n -> padre -> izquierda ) rotar_izquierda ( n -> padre ); más rotar_derecha ( n -> padre ); } borrar_caso3 ( n ); }

Caso 3: Los hijos de P , S y S son negros. En este caso, simplemente coloreamos S rojo. Como resultado, todos los caminos a través de S pero no a través de N tienen un nodo negro menos. Dado que la eliminación del padre de N hace que todos los caminos que pasan por N contengan un nodo negro menos, tales acciones igualan el equilibrio. Sin embargo, todos los caminos a través de P ahora contienen un nodo negro menos que los caminos que no pasan a través de P , por lo que la propiedad 5 (todas las rutas desde cualquier vértice a sus nodos hoja contienen el mismo número de nodos negros) todavía se viola. Para solucionar esto, aplicamos el procedimiento de reequilibrio a P a partir del caso 1.

void delete_case3 ( estructura nodo * n ) { nodo de estructura * s = hermano ( n ); si ( ( n -> padre -> color == NEGRO ) && ( s -> color == NEGRO ) && ( s -> izquierda -> color == NEGRO ) && ( s -> derecha -> color == NEGRO ) ) { s -> color = ROJO ; delete_case1 ( n -> padre ); } más eliminar_caso4 ( n ); }

Caso 4: S y sus hijos son negros, pero P es rojo. En este caso, simplemente cambiamos los colores de S y P. Esto no afecta la cantidad de nodos negros en las rutas a través de S , pero agregará uno a la cantidad de nodos negros en las rutas a través de N , restaurando así la influencia del nodo negro eliminado.

void delete_case4 ( estructura nodo * n ) { nodo de estructura * s = hermano ( n ); si ( ( n -> padre -> color == ROJO ) && ( s -> color == NEGRO ) && ( s -> izquierda -> color == NEGRO ) && ( s -> derecha -> color == NEGRO ) ) { s -> color = ROJO ; n -> padre -> color = NEGRO ; } más eliminar_caso5 ( n ); }

Caso 5: S es negro, el hijo izquierdo de S es rojo, el hijo derecho de S es negro y N es el hijo izquierdo de su padre. En este caso, rotamos el árbol a la derecha alrededor de S . Así, el hijo izquierdo de S se convierte en su padre y en el nuevo hermano de N. Después de eso, cambiamos los colores de S y su nuevo padre. Todos los caminos aún contienen el mismo número de nodos negros, pero ahora N tiene un hermano negro con un hijo derecho rojo, y pasamos al caso 6. Ni N ni su padre afectan esta transformación. (Para el caso 6, denotamos por S al nuevo hermano de N ).

void delete_case5 ( estructura nodo * n ) { nodo de estructura * s = hermano ( n ); if ( s -> color == BLACK ) { /* esta declaración if es trivial, debido al caso 2 (aunque el caso 2 cambió al hermano por el hijo de un hermano, el hijo del hermano no puede ser rojo, ya que ningún padre rojo puede tener un hijo rojo). */ /* las siguientes declaraciones solo fuerzan que el rojo esté a la izquierda de la izquierda del padre, o a la derecha de la derecha, por lo que el caso seis rotará correctamente. */ si ( ( n == n -> padre -> izquierda ) && ( s -> derecha -> color == NEGRO ) && ( s -> izquierda -> color == ROJO ) ) { /* esta última prueba también es trivial debido a los casos 2-4. */ s -> color = ROJO ; s -> izquierda -> color = NEGRO ; rotar_derecha ( s ); } más si ( ( n == n -> padre -> derecha ) && ( s -> izquierda -> color == NEGRO ) && ( s -> derecha -> color == ROJO ) ) { /* esta última prueba también es trivial debido a los casos 2-4. */ s -> color = ROJO ; s -> derecha -> color = NEGRO ; rotar_izquierda ( s ); } } eliminar_caso6 ( n ); }

Caso 6: S es negro, el hijo derecho de S es rojo y N es el hijo izquierdo de su padre P . En este caso, giramos el árbol a la izquierda alrededor de P , después de lo cual S se convierte en el padre de P y su hijo derecho. A continuación, intercambiamos los colores de P y S ( P toma el color de S , S toma el color de P ), y hacemos que el hijo derecho de S sea negro. El subárbol todavía tiene el mismo color de raíz, por lo que las propiedades 4 (Ambos hijos de cada nodo rojo son negros) y 5 (todas las rutas desde cualquier vértice a sus nodos hoja contienen el mismo número de nodos negros) no se violan. Sin embargo, N ahora tiene un antepasado negro adicional: P se volvió negro o era negro y S se agregó como abuelo negro. Así, los caminos que pasan por N pasan por un nodo negro adicional.

Mientras tanto, si el camino no pasa por N , entonces hay 2 opciones posibles:

Pasa por el nuevo hermano N. Luego, tiene que pasar por S y P , que simplemente cambiaron de color y lugar. Por lo tanto, la ruta contiene el mismo número de nodos negros.
Pasa por el nuevo tío N , hijo derecho de S . Una vez pasó por S , el padre de S y el hijo derecho de S (que era rojo), pero ahora solo pasa por S , que ha tomado el color de su anterior padre, y el hijo derecho de S , que tiene ha sido repintado de rojo a negro (Suponemos que el color S : negro). El efecto es que este camino pasa por el mismo número de nodos negros.

En cualquier caso, la cantidad de nodos negros en estos caminos no cambiará. Por lo tanto, hemos restaurado las propiedades 4 (Ambos hijos de cada nodo rojo son negros) y 5 (todos los caminos desde cualquier vértice a sus nodos hoja contienen el mismo número de nodos negros). El nodo blanco del diagrama puede ser rojo o negro, pero debe indicar el mismo color al principio y al final de la transformación.

void delete_case6 ( estructura nodo * n ) { nodo de estructura * s = hermano ( n ); s -> color = n -> padre -> color ; n -> padre -> color = NEGRO ; if ( n == n -> padre -> izquierda ) { s -> derecha -> color = NEGRO ; rotar_izquierda ( n -> padre ); } más { s -> izquierda -> color = NEGRO ; rotar_derecha ( n -> padre ); } }

Todas las llamadas a funciones recursivas se siguen y se convierten en bucles, por lo que el algoritmo requiere memoria O(1) . En el algoritmo anterior, todos los casos están conectados a su vez, excepto el caso 3, donde puede ocurrir un regreso al caso 1, que se aplica al ancestro del nodo: este es el único caso donde la implementación secuencial será un ciclo eficiente (después de uno rotación en el caso 3).

Además, la recursión de cola nunca ocurre en los nodos secundarios, por lo que un ciclo de recursión de cola solo puede moverse de los nodos secundarios a sus padres sucesivos. No habrá más de O(log n ) viajes de ida y vuelta al caso 1 (donde n es el número total de nodos en el árbol antes de la eliminación). Si ocurre una rotación en el caso 2 (la única posible en el ciclo de los casos 1-3), entonces el padre del nodo N se vuelve rojo después de la rotación y salimos del ciclo. Por lo tanto, no se realizará más de una rotación durante este ciclo. Después de salir del bucle, habrá como máximo dos rotaciones adicionales. En general, no habrá más de tres rotaciones del árbol.

Comparación con un árbol AVL balanceado

Altura del árbol

Sea h la altura del árbol, el número mínimo de vértices N. Entonces:

para el árbol AVL . Como , , N(h) crece como una sucesión de Fibonacci , por lo tanto , donde $N(h)=N(h-1)+N(h-2)+1$ $N(0)=0$ $N(1)=1$ $N(h)=\Theta (\lambda ^{h})$ $\lambda =({\sqrt {5}}+1)/2\aprox. 1,62$
para madera roja-negra $N(h)\geq 2^{{(h-1)/2}}=\Theta ({\sqrt {2}}^{h})$

Por lo tanto, con el mismo número de hojas, un árbol rojo-negro puede ser más alto que un árbol AVL, pero no más de un factor de 1. [5] $\log \lambda /\log {\sqrt {2}}\aprox. 1,388$

Buscar

Dado que el árbol rojo-negro es, en el peor de los casos, más alto, la búsqueda en él es más lenta, pero la pérdida de tiempo no supera el 39%.

Insertar

La inserción requiere hasta 2 vueltas en ambos tipos de árboles. Sin embargo, debido a la mayor altura del árbol rojo-negro, la inserción puede tardar más.

Eliminación

La eliminación de un árbol rojo-negro requiere hasta 3 rotaciones, en un árbol AVL puede requerir varias rotaciones hasta la profundidad del árbol (hasta la raíz). Por lo tanto, la eliminación de un árbol rojo-negro es más rápida que la eliminación de un árbol AVL. Sin embargo, las pruebas muestran que los árboles AVL son más rápidos que los árboles rojo-negro en todas las operaciones [6] [7] , el autor de la última prueba sugiere que los árboles rojo-negro pueden tener un mejor rendimiento con grandes cantidades de memoria [8] .

Memoria

El árbol AVL en cada nodo almacena la diferencia de altura (un número entero de −1 a +1, se necesitan 2 bits para la codificación). El árbol rojo-negro en cada nodo almacena un color (1 bit). Por lo tanto, un árbol rojo-negro puede ser más económico. (Cierto, dado que en los sistemas informáticos modernos, la memoria se asigna en múltiplos de bytes, entonces los árboles son exactamente iguales)

Sin embargo, en la práctica, ambos tipos de árboles usan números enteros, ya que trabajar con bits requiere cálculos adicionales del procesador (una instrucción del ensamblador y %al 0x10000000). Sin embargo, existen implementaciones del árbol rojo-negro que almacenan el valor del color en bits. Un ejemplo es Boost Multiindex . El propósito de almacenar el color en un bit es reducir el consumo de memoria del árbol rojo-negro ( compresión del nodo de índices ordenados ). El bit de color en esta implementación no se almacena en una variable separada, sino en uno de los punteros del nodo del árbol, convirtiéndolo en un puntero etiquetado .

Prueba de límites asintóticos

Un árbol rojo-negro que contiene n nodos internos tiene una altura de . $O(registro(n))$

Designaciones:

${\ estilo de visualización h (v)}$ es la altura del subárbol enraizado en $v$
${\ estilo de visualización bh (v)}$ es el número de nodos negros (sin contar si es negro) desde cualquier hoja en el subárbol (llamado la altura negra) $v$ $v$

Lema: un subárbol con raíz en un nodo tiene al menos nodos internos. $v$ ${\ estilo de visualización 2 ^ {bh (v)} -1}$

Prueba del lema (por inducción sobre la altura):

Base de inducción: . ${\ estilo de visualización h (v) = 0}$

Si el subárbol tiene altura cero, entonces debe ser nulo , entonces . $v$ $bh(''v'')=0$

Asi que:

2^{bh(v)}-1=2^{0}-1=1-1=0

Paso de inducción: sea un nodo tal que el subárbol también tenga al menos nodos internos. Demostremos que entonces , para lo cual , tiene al menos nodos internos. $v$ ${\ estilo de visualización h (v) = k}$ ${\ estilo de visualización 2 ^ {bh (v)} -1}$
$v'$ $h(v')=k+1$ $2^{bh(v')}-1$

Como tiene , es un nodo interno. Como tal, tiene dos hijos, ambos de altura negra , cualquiera (dependiendo de si es rojo o negro). Por la hipótesis de inducción, cada descendiente tiene al menos nodos internos y, por lo tanto, tiene al menos $v'$ $h(v')>0$ $bh(v')$ $bh(v')-1$ $v'$
${\ estilo de visualización 2^{bh(v')-1}-1}$ $v'$

2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1

nodos internos.

Usando este lema, podemos mostrar que el árbol tiene una altura logarítmica. Dado que al menos la mitad de los nodos en cualquier camino desde la raíz hasta la hoja son negros (propiedad 4 del árbol rojo-negro), la altura negra de la raíz es al menos . Por el lema tenemos: $h(raíz)/2$

n\geq 2^{{{h({\text{root))) \over 2}}}-1\leftrightarrow \;\log _{2}{(n+1)}\geq {h({\ text{root))) \over 2}\leftrightarrow \;h({\text{root)))\leq 2\log _{2}{(n+1)}.

Entonces la altura de la raíz es . $O(registro(n))$

Véase también

Primera búsqueda en profundidad
Primera búsqueda en amplitud
Árboles equilibrados (autoequilibrados):

árbol AVL
árbol matriz
Árbol perfectamente equilibrado
árbol en expansión
árboles B+
2-3-árbol
R-árbol
árbol B*

Lista de estructuras de datos (árboles)

Enlaces

Literatura

Kormen T., Leizerson C., Rivest R., Stein K. Algoritmos: construcción y análisis = Introducción a los algoritmos. - 2ª ed. - M. : Editorial "Williams" , 2011. - S. 336-364. - ISBN 978-5-8459-0857-5 .

Notas

↑ 1 2 estructuras de datos - ¿De dónde viene el término "árbol rojo/negro"? - Intercambio de pila de ingeniería de software . Consultado el 4 de enero de 2019. Archivado desde el original el 5 de enero de 2019. (indefinido)
↑ Curso "Algorithms: Design and Analysis, Part 1", conferencia "Red-Black Trees" Archivado el 25 de agosto de 2014 en Wayback Machine (Video 5:07 )
↑ Dr. Dobbs - Árboles rojo-negros de STL
↑ Clase TreeMap . Consultado el 13 de marzo de 2015. Archivado desde el original el 18 de marzo de 2015. (indefinido)
↑ en el límite para un gran número de hojas
↑ AVL vs RB Archivado el 11 de julio de 2016 en Wayback Machine .
↑ Red-Black versus AVL: benchmarks Archivado el 10 de febrero de 2015 en Wayback Machine .
↑ AVL vs. Rojo-Negro: la conclusión Archivado el 10 de febrero de 2015 en Wayback Machine .

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión