Árbol rojo-negro de tendencia izquierdista

Un árbol rojo-negro de inclinación izquierda ( LLRB ) es un tipo de árbol de búsqueda binaria 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 ]}

Propiedades

Un árbol rojo-negro con inclinación hacia la izquierda satisface todas las propiedades de un árbol rojo-negro:

Cada nodo es rojo o negro.
Un nodo NIL se considera negro.
Un nodo rojo no tiene un hijo rojo.
Cada ruta desde un nodo dado a cualquiera de sus nodos descendientes NIL pasa por el mismo número de nodos negros.
La raíz es negra (por convención).

Además, la propiedad de tendencia izquierdista afirma que:

Si un nodo tiene un solo hijo rojo, debe ser el hijo izquierdo.

La propiedad de inclinación hacia la izquierda reduce el número de casos que deben considerarse al implementar operaciones de árbol de búsqueda.

Relación con los árboles 2–3 y 2–3–4

Los árboles LLRB son árboles 2-3-4 isomorfos . A diferencia de los árboles rojo-negro convencionales, los nodos 3 siempre se inclinan hacia la izquierda, lo que establece una correspondencia uno a uno . Esto significa que para cada árbol LLRB existe un único árbol 2-3-4 correspondiente, 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 ahora se prohíben los nodos de 4 miembros. Sedgewick señala que las implementaciones de los árboles LLRB 2-3 y LLRB 2-3-4 difieren únicamente en la posición de una sola línea de código. ^{[ 1 ]}

Análisis

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 suele ser ese mismo múltiplo más rápido que el límite del peor caso, cercano al número óptimo de nodos $log N$ examinados que se observaría en un árbol perfectamente equilibrado.

Específicamente, en un árbol rojo-negro 2-3 con tendencia a la izquierda construido a partir de $N$ claves aleatorias, los experimentos de Sedgewick sugieren que:

Una búsqueda aleatoria exitosa examina $log 2 N - 0,5$ nodos.
La altura media de los árboles es de aproximadamente 2 $ln N.$
El tamaño promedio del subárbol izquierdo presenta un comportamiento de oscilación logarítmica.

Bibliografía

Implementación en Java de LLRB por Robert Sedgewick, según su artículo de 2008.
Robert Sedgewick. 20 de abril de 2008. Animaciones de las operaciones de la LLRB.
Estructuras de datos abiertas - Sección 9.2.2 - Árboles rojo-negro con inclinación a la izquierda , Pat Morin

Referencias

1 2 Sedgewick, Robert (2008). "Árboles rojo-negro de inclinación izquierda" (PDF) . Departamento de Ciencias de la Computación, Universidad de Princeton.

Enlaces externos

Robert Sedgewick. Árboles rojo-negros de tendencia izquierdista . Enlace directo al PDF .
Robert Sedgewick. Diapositivas de Left-Leaning Red–Black Trees de octubre de 2008 .
Linus Ek, Ola Holmström y Stevan Andjelkovic. 19 de mayo de 2009. Formalización de los árboles de Arne Andersson y los árboles rojo-negro de tendencia izquierdista en Agda.
Julien Oster. 22 de marzo de 2011. Una implementación en Agda de la eliminación en árboles rojo-negro de tendencia izquierdista.
Kazu Yamamoto. 19/10/2011. Árboles rojo-negros de tendencia izquierdista puramente funcionales.
Se considera perjudicial a los árboles de color rojo y negro con inclinación hacia la izquierda.

[Sedgewick-1] 1 2 Sedgewick, Robert (2008). "Árboles rojo-negro de inclinación izquierda" (PDF) . Departamento de Ciencias de la Computación, Universidad de Princeton.

[ 1 ]