2022-04-18

Motivación

• Tiempo menos dependiente de la cantidad de claves
• Rendimiento razonable en el peor caso
• Rapidez en la práctica
• Adecuados para claves de tamaño variable

Idea

No hacer comparaciones de claves completas sino en partes de ellas.

Desventajas

• Las operaciones sobre los componentes pueden ser difíciles o ineficientes
• Algunas implementaciones pueden requerir mucha memoria

Árboles de búsqueda digital

• Similares a los ABB:
  • Para guardar una clave vamos recorriendo el camino en el árbol que nos lleva a su posición
  • Pero la posición no está determinada por comparaciones de mayor y menor sino por los bits de la clave

Propiedades - Complejidad

• Peor caso mejor que el de los ABBs
• Tamaño máximo de una rama = tamaño máximo de las claves
• Longitud del camino más largo ≈ Mayor número de bits sucesivos iguales que inician una clave (prefijo)
• Búsqueda o inserción en un árbol de $n$ claves de $b$ bits necesita en promedio $\log(n)$ comparaciones de clave completa y $b$ en el peor caso.

Tries

Un trie es un árbol $(k+1)$-ario para alfabetos de $k$ elementos.

• Los ejes (conectores entre nodos) del árbol toman interés: representan componentes de las claves.
• Cada sub-árbol representa al conjunto de claves que comienza con las etiquetas de los ejes que llevan hasta él.
• Los nodos internos no contienen claves.
• Las claves o los punteros a la información se almacenan en las hojas.