Material adicional
- De tipo
general:
- Material
introductorio sobre eficiencia de algoritmos:
- Material
sobre árboles rojinegros:
- Algo de
material sobre árboles AVL (para el que quiera repasar):
- Material
sobre montículos d-arios:
- Material
sobre tries, árboles digitales y Patricia:
- Material
sobre árboles ternarios (una implementación de tries):
- Material
sobre Patricia:
- Material
sobre listas “skip”:
- Artículo
seminal de Pugh, “Skip lists: A probabilistic alternative to balanced
trees”,
[Pug90a].
- Otro
artículo del mismo autor, “A skip list cookbook”, [Pug90b].
- Artículo
de Messeguer, “Skip trees, an alternative data structure to skip lists in
a concurrent approach”, [Mes97].
- Un applet.
- Otro applet.
- Uno más (con
árboles AVL, rojinegros, AA, B, listas skip, heaps, treaps, splay…).
- Material sobre
árboles aleatorizados (“treaps”):
- Material
sobre introducción al análisis amortizado:
- Montículos
binomiales y de Fibonacci:
- Material sobre
estructuras de conjuntos disjuntos:
- Material
sobre estructuras auto-organizativas:
- Algoritmos de
búsqueda exacta de subcadenas:
- Material
sobre árboles de sufijos:
- Informe de
Gusfield, “Algorithms on strings, trees, and sequences: Introduction to
suffix trees”, similar a un capítulo del libro [Gus97].
- Otro
informe de Gusfield, “Algorithms on strings, trees, and sequences: Linear
time construction of suffix trees”.
- Capítulo
sobre árboles de sufijos del libro [MS05] de la bibliografía (acceso
mediante clave).
- Página con
demo, código, etc., de generación de árboles de sufijos: Lloyd Allison,
Monash University.
- Otra demo,
de Moritz G.
Maaß, TUM.
- Árboles de
sufijos generalizados: artículo de
la Universidad de Minesota (acceso mediante clave).
- Alternativas: suffix
arrays (Manber y Myers, 1993), suffix
vectors (Monostori et al, 2002) (acceso mediante clave).
- A
taxonomy of suffix array construction algorithms,
Simon J. Puglisi, W. F. Smyth & Andrew Turpin, ACM Computing Surveys
39-2 (2007) 1-31 (acceso mediante clave).
- 7.560.000
enlaces sobre árboles de sufijos.
- Aplicaciones
de algoritmos de búsqueda de patrones:
- Material de
la asignatura COP 5536
Advanced Data Structures del profesor Sartaj K. Sahni de la
Univ. de Florida.