Estructura de datos implícita - Implicit data structure

En informática , una estructura de datos implícita o una estructura de datos eficiente en el espacio es una estructura de datos que almacena muy poca información además de los datos principales o requeridos: una estructura de datos que requiere una baja sobrecarga . Se les llama "implícitos" porque la posición de los elementos conlleva significado y relación entre los elementos; esto se contrasta con el uso de punteros para dar una relación explícita entre elementos. Las definiciones de "gastos generales bajos" varían, pero generalmente significan gastos generales constantes; en notación O grande , O (1) sobrecarga. Una definición menos restrictiva es una estructura de datos sucinta , que permite una mayor sobrecarga.

Definición

Una estructura de datos implícita es una con una sobrecarga de espacio constante O (1) (por encima del límite inferior de la teoría de la información ).

Históricamente, Munro y Suwanda (1980) definieron una estructura de datos implícita (y algoritmos que actúan sobre una) como una "en la que la información estructural está implícita en la forma en que se almacenan los datos, en lugar de explícita en los indicadores". Son algo vagas en la definición, definiéndola más estrictamente como una sola matriz, con solo el tamaño retenido (un solo número de sobrecarga), o más libremente como una estructura de datos con sobrecarga constante ( O (1) ). Esta última definición es hoy más estándar, y la noción aún más flexible de una estructura de datos con una sobrecarga no constante pero pequeña o (n) se conoce hoy como una estructura de datos sucinta , como la define Jacobson (1988) ; se denomina semi-implícita por Munro y Suwanda (1980) .

Una distinción fundamental es entre estructuras de datos estáticas (solo lectura) y estructuras de datos dinámicas (que pueden modificarse). Las estructuras de datos implícitas simples, como representar una lista ordenada como una matriz, pueden ser muy eficientes como estructura de datos estáticos, pero ineficaces como estructura de datos dinámica, debido a que las operaciones de modificación (como la inserción en el caso de una lista ordenada) son ineficiente.

Ejemplos de

Un ejemplo trivial de una estructura de datos implícita es una estructura de datos de matriz , que es una estructura de datos implícita para una lista y solo requiere la sobrecarga constante de la longitud; a diferencia de una lista vinculada , que tiene un puntero asociado con cada elemento de datos, que proporciona explícitamente la relación de un elemento al siguiente. De manera similar, una cadena terminada en nulo es una estructura de datos implícita para una cadena (lista de caracteres). Estos se consideran muy simples porque son estructuras de datos estáticas (solo lectura), y solo admiten la operación simple de iteración sobre los elementos.

Similarmente simple es representar una matriz multidimensional como una única matriz unidimensional, junto con sus dimensiones. Por ejemplo, lo que representa un m × n matriz como una sola lista de longitud m · n , junto con los números m y n (en lugar de como una matriz de 1-dimensional de punteros a cada submatriz 1-dimensional). No es necesario que los elementos sean del mismo tipo, y una tabla de datos (una lista de registros ) se puede representar de manera similar implícitamente como una lista plana (unidimensional), junto con la longitud de cada campo , siempre que cada campo tenga tamaño uniforme (por lo que se puede usar un solo tamaño por campo, no por registro).

Un ejemplo menos trivial es la representación de una lista ordenada por una matriz ordenada , que permite la búsqueda en tiempo logarítmico mediante búsqueda binaria . Contraste con un árbol de búsqueda , específicamente un árbol de búsqueda binario , que también permite la búsqueda en tiempo logarítmico, pero requiere punteros. Una matriz ordenada solo es eficiente como una estructura de datos estática, ya que modificar la lista es lento, a diferencia de un árbol de búsqueda binario, pero no requiere el espacio de un árbol.

Un ejemplo importante de una estructura de datos implícita es representar un árbol binario perfecto como una lista, en orden creciente de profundidad, por lo que la raíz, el primer hijo izquierdo, el primer hijo derecho, el primer hijo izquierdo del primer hijo izquierdo, etc. para una tabla de ancestros a una profundidad dada, y la representación implícita se conoce como Ahnentafel (tabla de ancestros).

Esto se puede generalizar a un árbol binario completo (donde el último nivel puede estar incompleto), lo que produce el ejemplo más conocido de una estructura de datos implícita, a saber, el montón binario , que es una estructura de datos implícita para una cola de prioridad . Esto es más sofisticado que los ejemplos anteriores porque permite múltiples operaciones y es una estructura de datos dinámica eficiente (permite la modificación eficiente de los datos): no solo arriba , sino también insertar y pop .

Las estructuras de datos implícitas más sofisticadas incluyen el beap (montón bi-parental).

Historia

Los ejemplos triviales de listas o tablas de valores datan de la prehistoria, mientras que las estructuras de datos implícitas históricamente no triviales se remontan al menos al Ahnentafel, que fue introducido por Michaël Eytzinger en 1590 para su uso en genealogía. En informática formal, generalmente se considera que la primera estructura de datos implícita es la lista ordenada, utilizada para la búsqueda binaria, que fue introducida por John Mauchly en 1946, en las Moore School Lectures , la primera serie de conferencias sobre cualquier tema relacionado con la informática. tema. El montón binario se introdujo en Williams (1964) para implementar el heapsort . La noción de una estructura de datos implícita se formalizó en Munro y Suwanda (1980) , como parte de la introducción y análisis del beap .

Referencias

Otras lecturas

Véanse las publicaciones de Hervé Brönnimann , J. Ian Munro y Greg Frederickson .