Árbol rojo-negro: árboles de búsqueda binarios autoequilibrados explicados con ejemplos

¿Qué es un árbol rojo-negro?

El árbol rojo-negro es un tipo de árbol de búsqueda binaria (BST) autoequilibrado. En un árbol rojo-negro, cada nodo sigue estas reglas:

  1. Cada nodo tiene dos hijos, de color rojo o negro.
  2. Cada nodo de la hoja del árbol es siempre negro.
  3. Cada nodo rojo tiene sus dos hijos de color negro.
  4. No hay dos nodos rojos adyacentes (un nodo rojo no puede tener un padre rojo o un hijo rojo).
  5. Cada camino desde la raíz hasta un nodo de hoja de árbol tiene el mismo número de nodos negros (llamado "altura negra").

Insertar en árboles rojo-negro

Un nodo se inserta inicialmente en un árbol rojo-negro al igual que cualquier árbol de búsqueda binaria. Luego, el nuevo nodo recibe un color rojo. Una vez que se ha insertado ese nodo, el árbol debe validarse para garantizar que ninguna de las cinco propiedades haya sido violada. Si se ha violado una propiedad, hay tres casos potenciales que requieren una rotación a la izquierda, una rotación a la derecha y / o un cambio de color de los nodos. Los casos dependen del "tío" del nodo actual. Específicamente, si el nodo "tío" es negro o rojo. Para obtener más información sobre la inserción, los tres casos se pueden encontrar aquí.

Árbol rojo-negro inclinado a la izquierda

Un árbol rojo-negro inclinado hacia la izquierda (LLRB) es un tipo de árbol de búsqueda binaria autoequilibrado. Es una variante del árbol rojo-negro y garantiza la misma complejidad asintótica para las operaciones, pero está diseñado para ser más fácil de implementar.

Propiedades de los árboles rojo-negros inclinados hacia la izquierda

Todos los algoritmos de árbol rojo-negro que se han propuesto se caracterizan por un tiempo de búsqueda en el peor de los casos limitado por un pequeño múltiplo constante de log N en un árbol de N claves, y el comportamiento observado en la práctica es típicamente ese mismo múltiplo más rápido que el límite del peor de los casos, cercano a los nodos log N óptimos examinados que se observarían en un árbol perfectamente equilibrado.

Específicamente, en un árbol 2-3 rojo-negro inclinado a la izquierda construido a partir de N claves aleatorias: -> Una búsqueda aleatoria exitosa examina log2 N- 0.5 nodos. -> La altura media de los árboles es aproximadamente2 log2 N