Saltar al contenido

Estructuras de datos 2: listas de omisión

septiembre 23, 2021
1LcOwJEnyNVYw9 NP9Hav4Q

Estructuras de datos 2: listas de omisión

Una alternativa probabilística a los árboles equilibrados

Gunavaran Brihadiswaran

25 de julio de 2020·6 min de lectura

1*LcOwJEnyNVYw9 NP9Hav4Q

Introducción

Los árboles binarios se pueden utilizar para representar tipos de datos abstractos, como diccionarios y listas ordenadas. Howsiempre, cuando insertamos elementos en orden, hay una alta tendencia a que terminemos con una estructura de datos degenerada que funcione mal (por ejemplo, insertando 2,3,4,5,6,7,8 en orden en un árbol binario) . Es por eso que a menudo usamos estructuras de árbol balanceadas que reorganizan la estructura de árbol a medida que se llevan a cabo las operaciones. Las listas de omisión se pueden utilizar como alternativas a los árboles equilibrados (incluso podrían funcionar bien según las restricciones). Dado que no son tan populares como las estructuras de árbol equilibradas, pensé que escribir este artículo como el segundo de mi serie Estructura de datos podría ser útil.

Listas vinculadas

Lista enlazada es una estructura de datos muy familiar que es simple y fácil de implementar. El siguiente diagrama ilustra una lista enlazada individualmente ordenada donde cada nodo contiene un puntero a su vecino derecho.

1*XIjKdwi2nsOZc2uqzMR6PQ

Imagen del autor

Operaciones de lista enlazada ordenada y complejidad del tiempo

Las operaciones comunes que buscamos son Buscar, Insertar y Eliminar. Echemos un vistazo a los pseudocódigos.

Buscar (lista, clave de búsqueda)
// encontrar la clave de búsqueda a través de una búsqueda lineal

Insert (nodo, newNode) // inserta newNode como el vecino derecho del nodo
newnode.next ← node.next
node.next ← newNode

Delete (nodo) // elimina el vecino correcto del nodo
obsoleteNode ← node.next
node.next ← node.next.next
free (obsoleteNode)

En consecuencia, las complejidades promedio del tiempo de caso serían,
– Buscar : Θ (norte)
– Insertar: Θ (1)
– Borrar : Θ (1)

dónde norte es la longitud de la lista vinculada (o el número de nodos en la lista vinculada)

Los inconvenientes

  • La búsqueda no es eficiente. Difícil de buscar en menos de O (n) tiempo
  • El recorrido es lento porque debe atravesar un nodo a la vez, comenzando desde el primer nodo hasta el nodo de interés. No se puede saltar directamente al medio.

los Saltar listas proporcionar la solución a estos inconvenientes.

Listas de omisión perfectas

Hagamos algunas modificaciones a nuestra lista enlazada. En nuestra lista vinculada original, cada nodo tiene un puntero solo a su vecino derecho. Para todos los demás nodos, agreguemos un puntero al nodo que está dos por delante. El siguiente diagrama daría una mejor idea.

close