2022-30-05

En esta clase veremos representaciones alternativas de diccionarios, que nos ayudarán a caracterizar el concepto de algoritmos probabilísticos.

Skip Lists

Perfectas

• Diccionarios sobre listas enlazadas ordenadas

• Para hacer una búsqueda más eficiente linkeamos los nodos con “saltos” entre sí.

  

  Llevando esta idea al límite, cada $2^i$-ésimo nodo posee una referencia al nodo $2^i$ posiciones más adelante en la lista.

• El primer nodo es una especie de “menor absoluto” que nos permite acceder al primer nodo de cada uno de los niveles.

• En relación a una lista enlazada ordenada simple, sólo tenemos el doble de punteros en una skip list del mismo tamaño $n$.

• Podemos tener $\log n$ listas apiladas de esta forma.

• La complejidad en el caso promedio de la búsqueda de un elemento cualquiera en una skip list de tamaño $n$ construida hasta el último nivel (es decir, hasta la $(\log n)$-ésima lista) es de $O(\log_2 n)$, ya que como máximo se examinan esa cantidad de nodos.

Este tipo de estructura tiene una gran desventaja: es muy rígida, no soporta bien el caso dinámico, se vuelve difícil de mantener.

No Perfectas

Podemos aleatorizar el requerimiento y asignar el nivel de cada nodo probabilísticamente (por ejemplo, librándolo al azar).

Si usamos una moneda para determinar qué tanto elevamos el nodo que vamos a insertar, probabilísticamente cada lista sucesiva va a tener la misma cantidad de nodos que en el caso perfecto (50% de posibilidades de que un nodo se inserte al segundo nivel, 25% de que se inserte al tercero, y así sucesivamente…).

De esta manera el costo de búsqueda en el caso promedio tenderá a ser $O(\log n)$.