Red-black tree

Red-black tree es una especie de árbol binario equilibrado. Tiene buenas propiedades. Los nodos del árbol están ordenados y, como está equilibrado, también se busca. No hay una situación muy mala y la complejidad temporal de las operaciones basadas en árboles binarios es O (log (N)). El kernel de Linux usa un árbol rojo-negro para mantener los bloques de memoria al administrar vm_area_struct.

Primero vea include /linux /rbtree.h para ver algunas definiciones de árboles rojo-negros, como sigue:

struct rb_node

{

sin signo long rb_parent_color;

#define RB_RED 0

#define RB_BLACK 1

struct rb_node * rb_right;

struct rb_node * rb_left;

} __attribute __ ((alineado (sizeof (long)))))

struct rb_root es solo un contenedor para struct rb_node * La ventaja es que no parece pasar el puntero secundario. Sí, muy simple. Mira las siguientes macros importantes. Cuidado, encontrarás que rb_parent_color no es tan simple. Andrea Arcangeli usa un pequeño truco aquí, pero es genial. Como su nombre lo indica, este miembro realmente contiene un puntero al padre y el color de este nodo. ¿Cómo lo hizo? Muy simple, la alineación funciona. Dado que es la alineación del tamaño (largo), entonces en el IA-32, los dos bits más bajos de la dirección de cualquier estructura rb_node deben ser cero. En lugar de estar vacío, es mejor usarlos para representar el color. De hecho, uno es suficiente.

De esta forma, para extraer el puntero principal, simplemente borre los dos bits inferiores del miembro rb_parent_color:

#define rb_parent (r) (( Struct rb_node *) ((r) - > rb_parent_color &~ 3))

Para tomar el color, mire el último bit:

# define rb_color (r) ((r) - > rb_parent_color &1)

La prueba de colores y la configuración de colores también es una cuestión de rutina. Se hace mención especial a la siguiente función en línea:

estática en línea void rb_link_node (struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link);

Establece el padre en el nodo padre del nodo y permite que rb_link apunte al nodo.

Nos centramos en lib /rbtree.c y observamos algunos de los algoritmos importantes asociados con los árboles rojo-negros. Antes de comenzar, recordemos las reglas del árbol rojo-negro:

1. Cada nodo es rojo o negro;

2. El nodo raíz debe ser Negro;

3. Nodos rojos Si los niños tienen hijos, sus hijos deben ser negros;

4. Cada ruta desde el nodo raíz a la hoja debe contener el mismo número de nodos negros. .

Estas cuatro reglas pueden limitar un árbol de clasificación para equilibrarlo.

__rb_rotate_left es una rotación a la izquierda del nodo nodo en el árbol de raíz, y __rb_rotate_right es a la derecha. Estas dos funciones son para servicios posteriores de inserción y eliminación, en lugar de proporcionar una interfaz al exterior.

Los nodos recién insertados se configuran en hojas, teñidas de rojo, si las reglas anteriores se rompen después de la inserción, el color y la rotación se pueden restaurar, y el árbol binario se reequilibra. La función de interfaz para la operación de inserción es

void rb_insert_color (struct rb_node * node, struct rb_root * root);

Coloca el nodo padre determinado El nodo nodo del punto está integrado en el árbol rojo-negro arraigado en la raíz. El análisis del algoritmo específico puede referirse a la Sección 14.3 en [1]. La implementación aquí es casi exactamente la misma que la del libro. La forma de determinar el nodo primario del nodo se debe hacer manualmente llamando a rb_insert_color. Vale la pena señalar que aunque la operación de inserción requiere una iteración de bucle, el número total de rotaciones no excederá dos veces. Así que la eficiencia sigue siendo muy optimista.

La operación de eliminación es más o menos problemática. Primero debe realizar la eliminación y " como el árbol de búsqueda binario normal, y luego juzgar si se debe ejecutar más según el color del nodo eliminado. La operación La interfaz que se eliminará es:

void rb_erase (struct rb_node * node, struct rb_root * root);

De hecho, en realidad no elimina el nodo En su lugar, simplemente deje que se separe del árbol arraigado en la raíz, y finalmente tiene que decidir si llamar a __rb_erase_color para ajustarlo. Para obtener una explicación del algoritmo específico, consulte las Secciones 13.3 y 14.4 de [1], RB-DELETE-FIXUP en el libro correspondiente de __rb_erase_color, y la implementación aquí es básicamente la misma que la del libro.

Las interfaces restantes son más simples.

struct rb_node * rb_first (struct rb_root * root);

Encuentra y devuelve el más pequeño en el árbol rooteado en la raíz Nodo, siempre que vayas desde el nodo raíz a la izquierda.

struct rb_node * rb_last (struct rb_root * root);

es buscar y devolver el más grande, siga hacia la derecha.

struct rb_node * rb_next (struct rb_node * node);

Devolver la sucesión de nodo en el árbol es un poco más complicado. Si el elemento secundario derecho del nodo no está vacío, solo necesita devolver el nodo más pequeño en el subárbol derecho del nodo; si está vacío, debe buscar y encontrar el nodo del elemento secundario izquierdo del padre del nodo superpuesto, regresar Nodo padre Si lo anterior ha alcanzado el nodo raíz, devuelve NULL.

struct rb_node * rb_prev (struct rb_node * node);

Devuelve el precursor del nodo y es simétrico con la operación en rb_next.

void rb_replace_node (struct rb_node * victim, struct rb_node * new, struct rb_root * root);

Reemplace root por root El nodo víctima en el árbol.

Un ejemplo típico de una interfaz de árbol rojo-negro es el siguiente:

página de estructura en línea estática * rb_search_page_cache (struct inode * inode,

desplazamiento largo sin signo)

{

struct rb_node * n = inode- > i_rb_page_cache.rb_node;

struct page * page;

while (n)

{

page = rb_entry (n, struct page, rb_page_cache);

if (offset < page- > offset)

n = n- > rb_left;

else if (offset > page- > offset)

n = n- > rb_right;

else

return page;