Un árbol rojo-negro con inclinación a la izquierda ( LLRB ) es un tipo de árbol binario de búsqueda autoequilibrado , introducido por Robert Sedgewick . 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. [1]
Un árbol rojo-negro inclinado hacia la izquierda satisface todas las propiedades de un árbol rojo-negro:
Además, la propiedad de tendencia izquierdista establece que:
La propiedad de inclinación a la izquierda reduce la cantidad de casos que deben considerarse al implementar operaciones de árbol de búsqueda.
Los árboles LLRB son árboles isomorfos 2–3–4 . A diferencia de los árboles rojo-negros convencionales, los 3 nodos siempre se inclinan hacia la izquierda, lo que hace que esta relación sea una correspondencia 1 a 1. Esto significa que para cada árbol LLRB, hay un árbol 2–3–4 correspondiente único, y viceversa.
Si imponemos el requisito adicional de que un nodo no puede tener dos hijos rojos, los árboles LLRB se vuelven isomorfos a los árboles 2–3 , ya que los árboles de 4 nodos ahora están prohibidos. Sedgewick señala que las implementaciones de los árboles LLRB 2–3 y LLRB 2–3–4 difieren solo en la posición de una sola línea de código. [1]
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, cerca del log N óptimo de los nodos examinados que se observarían en un árbol perfectamente equilibrado.
En concreto, en un árbol rojo-negro 2-3 con inclinación hacia la izquierda construido a partir de N claves aleatorias, los experimentos de Sedgewick sugieren que: