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.
Árbol rojo-negro inclinado hacia la izquierda | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | árbol | ||||||||||||||||||||
Inventado | 2008 | ||||||||||||||||||||
Inventado por | Robert Sedgewick | ||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||
|
Propiedades de un árbol rojo-negro inclinado a 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 log 2 N - 0.5 nodos.
- La altura promedio de los árboles es de aproximadamente 2 log 2 N
- El tamaño promedio del subárbol izquierdo exhibe un comportamiento de oscilación logarítmica.
enlaces externos
Documentos
- Robert Sedgewick. Árboles rojo-negros inclinados a la izquierda . Enlace directo a PDF .
- Robert Sedgewick. Árboles rojo-negros inclinados a la izquierda (diapositivas). Dos versiones:
- Linus Ek, Ola Holmström y Stevan Andjelkovic. 19 de mayo de 2009. Formalización de árboles de Arne Andersson y árboles rojo-negros de izquierda en Agda
- Julien Oster. 22 de marzo de 2011. Una implementación Agda de la eliminación en árboles rojo-negro inclinados a la izquierda
- Kazu Yamamoto. 2011.10.19. Árboles rojo-negro puramente funcionales que se inclinan hacia la izquierda
Implementaciones
Autor | Fecha | Idioma | Variante | Notas | Enlace |
---|---|---|---|---|---|
Robert Sedgewick | 2008 | Java | De este documento de Sedgewick | ||
David Anson | 2 junio 2009 | C# | Mantener el equilibrio: una implementación de árbol rojo-negro versátil para .NET | ||
kazu-yamamoto | 2011 | Haskell | llrbtree ( Data.Set.LLRBTree ) | ||
Lee Stanza | 2010 | C ++ | Incluye discusión | Árboles equilibrados, parte 4: árboles rojo-negro inclinados hacia la izquierda | |
Jason Evans | 2010 | C | 2-3 | rb.h | |
Nicola Bortignon | 8 de diciembre de 2010 | ActionScript 3 | Implementación y discusión de AS3 | ||
william en 25thandClement.com | 2011 | C | 2-3 variante usando iteración con punteros principales | llrb.h: Árbol rojo-negro inclinado a la izquierda | |
Maciej Piechotka | 2009 | Vala | Gee.TreeMap | ||
Petar Maymounkov | 2010 | Ir | 2-3 | GoLLRB | |
Sebastien Chapuis | 2015 | C | C - Implementación rbtree inclinada a la izquierda | ||
Seungyoung Kim | 2015 | C | Variante 2-3-4 | Implementación de C | |
Robin Heggelund Hansen | 2018 | Olmo | Implementación de olmo | ||
R Pratap Chakravarthy | 2019 | Oxido | Implementación de óxido | ||
Valeriano Della Longa | 2021 | Rápido | 2-3 | Conformidad con el protocolo BidirectionalCollection con complejidad O (1) para firstIndex, endIndex, first, last, min y max. | Implementación rápida |
Filza y Ahmed | 2021 | Pitón | https://www.youtube.com/channel/UCm68_MratG7meGtzTbkS_3g/featured |
Otro
- Robert Sedgewick. 20 de abril de 2008. Animaciones de las operaciones de LLRB
- Estructuras de datos abiertos - Sección 9.2.2 - Árboles rojo-negros inclinados a la izquierda , Pat Morin
- Árboles rojo-negros inclinados a la izquierda considerados nocivos