Árbol rojo-negro
Este cumple la función de hoja para todas las ramas del árbol.
Esto no es necesario, ya que puede hacerse una referencia nula (NIL) en el final de cada rama.
En adelante, se dice que un nodo es rojo o negro haciendo referencia a dicho atributo.
Además de los requisitos impuestos a los árboles binarios de búsqueda convencionales, se deben satisfacer las siguientes reglas para tener un árbol rojo-negro válido: Estas reglas producen una regla crucial para los árboles rojo-negro: el camino más largo desde la raíz hasta una hoja no es más largo que dos veces el camino más corto desde la raíz a una hoja.
Para comprobarlo basta ver que ningún camino puede tener dos nodos rojos seguidos debido a la propiedad 4.
Es posible presentar los árboles rojo-negro en este paradigma, pero cambian algunas de las propiedades y se complican los algoritmos.
Los árboles rojo-negro ofrecen un peor caso con tiempo garantizado para la inserción, el borrado y la búsqueda.
Por ejemplo, muchas estructuras de datos usadas en geometría computacional pueden basarse en árboles rojo-negro.
Para conservar las propiedades que debe cumplir todo árbol rojo-negro, en ciertos casos de la inserción y la eliminación será necesario reestructurar el árbol, si bien no debe perderse la ordenación relativa de los nodos.
En las imágenes pueden verse de forma simplificada cómo se llevan a cabo las rotaciones simples hacia la izquierda y hacia la derecha en cualquier árbol binario de búsqueda, en particular en cualquier árbol rojo-negro.
Si el elemento a localizar coincide con el de la raíz, la búsqueda ha concluido con éxito.
Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente y representa una función logarítmica.
Lo que sucede después depende del color de otros nodos cercanos.
Conviene notar que: Al contrario de lo que sucede en otros árboles como puede ser el Árbol AVL, en cada inserción se realiza un máximo de una rotación, ya sea simple o doble.
La propiedad 5 (todos los caminos desde cualquier nodo dado a sus hojas contiene igual número de nodos negros) se mantiene, porque el nuevo nodo N tiene dos hojas negras como hijos, pero como N es rojo, los caminos a través de cada uno de sus hijos tienen el mismo número de nodos negros que el camino hasta la hoja que reemplazó, que era negra, y así esta propiedad se mantiene satisfecha.
Su implementación: Caso 3: Si el padre P y el tío U son rojos, entonces ambos nodos pueden ser repintados de negro y el abuelo G se convierte en rojo para mantener la propiedad 5 (todos los caminos desde cualquier nodo dado hasta sus hojas contiene el mismo número de nodos negros).
Como cualquier camino a través del padre o el tío debe pasar a través del abuelo, el número de nodos negros en esos caminos no ha cambiado.
Sin embargo, el abuelo G podría ahora violar la propiedad 2 (la raíz es negra) o la 4 (ambos hijos de cada nodo rojo son negros), en el caso de la 4 porque G podría tener un padre rojo.
Para solucionar este problema, el procedimiento completo se realizará de forma recursiva hacia arriba hasta alcanzar el caso 1.
El código en C quedaría de la siguiente forma: Caso 4: El nodo padre P es rojo pero el tío U es negro; también, el nuevo nodo N es el hijo derecho de P, y P es el hijo izquierdo de su padre G. En este caso, una rotación a la izquierda que cambia los roles del nuevo nodo N y su padre P puede ser realizada; entonces, el primer nodo padre P se ve implicado al usar el caso 5 de inserción (re etiquetando N y P ) debido a que la propiedad 4 (ambos hijos de cada nodo rojo son negros) se mantiene aún incumplida.
La rotación causa que algunos caminos (en el sub-árbol etiquetado como “1”) pasen a través del nuevo nodo donde no lo hacían antes, pero ambos nodos son rojos, así que la propiedad 5 (todos los caminos desde cualquier nodo dado a sus hojas contiene el mismo número de nodos negros) no es violado por la rotación, después de completado este caso, se puede notar que aún se incumple la propiedad número 4 (ambos hijos de cada nodo rojo son de color negro), esto se resuelve pasando al caso 5.
Una posible implementación en C es la siguiente: En un árbol binario de búsqueda normal, cuando se borra un nodo con dos nodos internos como hijos, tomamos el máximo elemento del subárbol izquierdo o el mínimo del subárbol derecho, y movemos su valor al nodo que es borrado (como se muestra aquí).
Si borramos un nodo rojo, podemos simplemente reemplazarlo con su hijo, que debe ser negro.
El caso complejo es cuando el nodo que va a ser borrado y su hijo son negros.
Una posible implementación en el lenguaje de programación C sería la siguiente: Caso 2: S es rojo.
Aunque todos los caminos tienen todavía el mismo número de nodos negros, ahora N tiene un hermano negro y un padre rojo, así que podemos proceder a al paso 4, 5 o 6 (este nuevo hermano es negro porque este era uno de los hijos de S, que es rojo).
Su implementación en C: Caso 4: S y los hijos de este son negros, pero P es rojo.
En este caso rotamos a la derecha S, así su hijo izquierdo se convierte en su padre y en el hermano de N. Entonces intercambiamos los colores de S y su nuevo padre.
El nodo blanco en diagrama puede ser rojo o negro, pero debe tener el mismo color tanto antes como después de la transformación.
Usando este lema podemos mostrar que la altura del árbol es algorítmica.
