• La estructura original fue creada por Rudolf Bayer en 1972, que le dio el nombre de árboles-B binarios simétricos, pero tomó su nombre moderno en un trabajo de Leo J. Guibas y Robert Sedgewick realizado en 1978.

• Los árboles rojo-negro son un subtipo de árbol binario de búsqueda en el que cada nodo tiene un atributo de color cuyo valor es rojo o negro.

• Garantiza un tiempo de ejecución de \(O(logn)\), donde n es el número total de elementos en el árbol.

• Un nodo es Rojo o Negro.

• La raíz siempre es negra.

• Un nodo Rojo siempre tendrá hijos negros (Un apuntador Null se tomará en consideración para hacer referencia a un nodo Negro).

• El número de nodos negros es el mismo en cualquier camino que vaya de la raíz a la hoja.

Las rotaciones son necesarias para que cumpla las propiedades de un árbol rojo-negro, ya que en los casos como inserción y eliminación, al final hay ocasiones que se necesita restructurar el árbol, por lo cual existen la rotación:

• La Rotación izquierda.

• La Rotación derecha.

Es la misma rotación que ocupan los arboles binarios de búsqueda.

• Altura de un nodo(h): el número de bordes en el camino más largo a una hoja.
• Altura de un nodo negro(bh): es igual a la altura del nodo cuando sólo se tienen en cuenta los nodos negros (incluida la hoja) del subárbol cuya raíz es el nodo.

El árbol sigue siendo rojo-negro. por lo que no hay que realizar ningún ajuste.

• Nodo a Negro con hermano rojo (nodo d)

• A hermano se le pinta negro (nodo d), a padre de rojo (nodo b) y rotar a la izquierda.

• Un nodo a y hermano negro (nodo d), el hijo derecho de hermano negro (nodo e) y el izquierdo rojo.

• Al hijo izquierdo del hermano (nodo c) se le pinta negro y a hermano de rojo (nodo d)

• Rotar a la derecha para equilibrar.