Skiplist (2016)

Apunte Español
Universidad Universidad Autónoma de Barcelona (UAB)
Grado Ingeniería Informática - 2º curso
Asignatura Laboratori de Programació
Año del apunte 2016
Páginas 1
Fecha de subida 27/06/2017
Descargas 0
Subido por

Vista previa del texto

SKIPLIST NODOS Una SkipList está formada por: - Nodos de cabecera: contienen dos apuntadores: o Down: apuntador al nivel inferior o Next: apuntador al siguiente nodo del mismo nivel - Nodos de datos: contiene los siguientes datos o Key: valor de clave o Value: valor del nodo o Down: apuntador al nivel inferior o Next: apuntador al siguiente nodo del mismo nivel ANÁLISIS SKIPLIST - Lista ordenada tiene una eficacia de O(n).
Torre más alta tendrá una altura log 2 (𝑛) + 1 → 𝑂(log(𝑛)).
El movimiento down implica log(n) niveles.
Eficacia para búsqueda => log 2 (𝑛).
Eficacia para inserir => log 2 (𝑛).
...