De acuerdo con Introducción a los algoritmos, un árbol rojo-negro es un árbol de búsqueda binario con un bit de almacenamiento adicional por nodo: su color, que puede ser ROJO o NEGRO. Al restringir los colores del nodo en cualquier ruta simple desde la raíz a una hoja, los árboles rojo-negros aseguran que dicha ruta no sea más del doble que cualquier otra, de modo que el árbol esté aproximadamente equilibrado.
Cada nodo del árbol ahora contiene los atributos color, clave, izquierda, derecha y p. Si no existe un elemento secundario o principal de un nodo, el atributo de puntero correspondiente del nodo contiene el valor NIL. Consideraremos que estos NIL son punteros a las hojas (nodos externos) del árbol de búsqueda binario y los nodos normales con clave como nodos internos del árbol.
Un árbol rojo-negro es un árbol binario que satisface las siguientes propiedades rojo-negro:
- Cómo determinar la complejidad de esta recurrencia T (n) = 16 * T (n / 4) + n! usando el teorema maestro
- Cómo escribir un programa que ingrese n números y diga el más pequeño y el más grande
- ¿Qué es el diagrama de flujo?
- ¿En qué debe centrarse un estudiante de ingeniería informática, proyectos o estructuras de datos y algoritmos?
- Cómo utilizar el algoritmo Hidden Markov Model Viterbi para el etiquetado de secuencias
1. Cada nodo es rojo o negro.
2. La raíz es negra.
3. Cada hoja (NIL) es negra.
4. Si un nodo es rojo, sus dos hijos son negros.
5. Para cada nodo, todas las rutas simples desde el nodo hasta las hojas descendientes contienen el mismo número de nodos negros.
Confundido todavía?
No es más que un árbol de búsqueda binario (BST), con un poco de datos adicionales agregados a cada nodo para facilitar el “auto-equilibrio”.
Un BST de altura h puede admitir cualquiera de las operaciones básicas de conjuntos dinámicos, como BÚSQUEDA, PREDECESOR, SUCESOR, MÍNIMO, MÁXIMO, INSERTAR y ELIMINAR, en tiempo O (h). Por lo tanto, las operaciones de configuración son rápidas si la altura del árbol de búsqueda es pequeña. Sin embargo, si su altura es grande, las operaciones de configuración pueden ejecutarse no más rápido que con una lista vinculada. Los árboles rojo-negros son uno de los muchos esquemas de árbol de búsqueda que están “equilibrados” para garantizar que las operaciones básicas de conjuntos dinámicos tarden O (lg n) en el peor de los casos.
