En un árbol rojo-negro, cada nodo puede tener dos colores diferentes: rojo o negro. Los árboles rojo-negro siempre cumplen las siguientes cinco condiciones:
Los árboles rojo-negro pueden rotar, agregar nodos y eliminar nodos. La operación de rotación se divide en operación con la mano izquierda y operación con la mano derecha. La mano izquierda significa que el nodo hoja derecho del nodo padre original se convierte en el nuevo nodo padre, y el nodo padre original se convierte en el nodo hoja izquierda del nuevo nodo padre. Al girar a la izquierda, debido al cambio de punteros entre nodos, la posición del subárbol izquierdo del nodo hoja derecho original está ocupada por el nodo padre original, y se debe encontrar un nuevo nodo padre para él. Obviamente, debido a que los valores de todos los nodos en este subárbol son más pequeños que el nodo hoja derecho original y más grandes que el nodo padre original, se puede utilizar como el subárbol derecho del nodo padre original. Básicamente ocurre lo mismo con la rotación a la derecha.
La operación de inserción del árbol rojo-negro es más complicada que la del árbol de búsqueda binario ordinario porque necesita mantener cinco atributos del árbol rojo-negro, que cambiarán durante la inserción. La primera mitad de la operación de inserción es básicamente la misma que la de un árbol de búsqueda binario normal. Continúe buscando en el árbol hasta que encuentre una ubicación adecuada para insertar el nuevo nodo en el árbol como un nodo hoja. Luego, el nodo se marca en rojo. El trabajo restante es ajustar el color de cada nodo del árbol rojo-negro para mantener las propiedades del árbol rojo-negro.
Insertar un nodo rojo debajo de un nodo puede resultar en la siguiente situación:
Para el segundo caso, es fácil de manejar, simplemente cambie el color del nodo a negro. La primera situación es más complicada.
Dependiendo del método de procesamiento, se puede dividir en tres situaciones según el color de los nodos hermanos del nodo padre:
La eliminación del árbol rojo-negro también es más complicada que el árbol binario. Si se elimina/mueve un nodo rojo, es básicamente consistente con un árbol de búsqueda binario, ya que no destruye ninguna propiedad de un árbol rojo-negro. Si elimina un nodo negro, la altura negra de su nodo principal será inconsistente.
Al eliminar, además de eliminar el árbol de búsqueda binario, también debe registrar el color inicial del nodo eliminado/movido. El color del nodo movido se convertirá en el color del nodo eliminado.
A continuación, el nodo que se va a mover se indica como Y. El nodo que ocupa la posición original del nodo Y se representa como Al nodo se le asigna un negro intenso (este negro intenso es el negro heredado del nodo Y original), de modo que tenga dos colores al mismo tiempo. De esta manera, el número de nodos negros del camino simple a través de X puede considerarse temporalmente sin cambios y las propiedades permanecen sin cambios. 5. En este momento, el color del nodo X puede tener dos situaciones: doble negro o rojo y negro. Si x es rojo y negro, establezca x en negro. Porque esto no afectará las propiedades de x ni de ninguno de sus nodos secundarios. Si x es doble negro, es necesario asignar negros adicionales a otros nodos. A continuación, se puede dividir en las siguientes situaciones: