Estadísticas del PDF: 2.4 Arboles digitales de busqueda, tries y Patricia

Análisis del caso promedio

• El plan:

– Probabilidad
– Análisis probabilista
– Árboles binarios de búsqueda construidos

aleatoriamente

– Tries, árboles digitales de búsqueda y Patricia
– Listas “skip”
– Árboles aleatorizados

Técnicas Avanzadas de Programación - Javier Campos

127

Tries, árboles digitales de búsqueda y Patricia

• Tries: motivación…

– Letras centrales de la palabra “retrieval”, recuperación

(de información).

– Diccionario de Unix: 23.000 palabras y 194.000
...