En informática , una estructura de datos implícita o estructura de datos que ahorra espacio es una estructura de datos que almacena muy poca información aparte de los datos principales o requeridos: una estructura de datos que requiere poca sobrecarga . Se denominan "implícitas" porque la posición de los elementos conlleva un significado y una relación entre elementos; esto contrasta con el uso de punteros para dar una relación explícita entre elementos. Las definiciones de "baja sobrecarga" varían, pero generalmente significa una sobrecarga constante; en notación O grande , O (1) sobrecarga. Una definición menos restrictiva es una estructura de datos sucinta , que permite una mayor sobrecarga.
Una estructura de datos implícita es una con una sobrecarga espacial constante de 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 ella) 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 punteros". Son algo vagos en la definición, definiéndola más estrictamente como una única matriz, con solo el tamaño retenido (un único número de sobrecarga), [1] o de manera más vaga como una estructura de datos con sobrecarga constante ( O (1) ). [2] Esta última definición es hoy más estándar, y la noción aún más vaga de una estructura de datos con una sobrecarga o (n) no constante pero pequeña se conoce hoy como una estructura de datos sucinta , según la definición de Jacobson (1988); Munro y Suwanda (1980) se refirieron a ella como semi-implícita . [3]
Una distinción fundamental es entre las estructuras de datos estáticas (de solo lectura) y las estructuras de datos dinámicas (que se pueden modificar). Las estructuras de datos implícitas simples, como la representación de una lista ordenada como una matriz, pueden ser muy eficientes como estructura de datos estática, pero ineficientes 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 ineficientes.
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 requiere solo la sobrecarga constante de la longitud; a diferencia de una lista enlazada , que tiene un puntero asociado con cada elemento de datos, que da explícitamente la relación de un elemento con el siguiente. De manera similar, una cadena terminada en nulo es una estructura de datos implícita para una cadena (lista de caracteres). Estas 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.
De manera similar, es sencillo representar una matriz multidimensional como una única matriz unidimensional, junto con sus dimensiones. Por ejemplo, se puede representar una matriz m × n como una única lista de longitud m·n , junto con los números m y n (en lugar de como una matriz unidimensional de punteros a cada submatriz unidimensional). Los elementos no necesitan ser del mismo tipo, y una tabla de datos (una lista de registros ) puede representarse de manera similar de manera implícita como una lista plana (unidimensional), junto con la longitud de cada campo , siempre que cada campo tenga un tamaño uniforme (de modo que se pueda usar un único 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 una búsqueda binaria . En 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 la sobrecarga de espacio de un árbol.
Un ejemplo importante de una estructura de datos implícita es la representación de un árbol binario perfecto como una lista, en orden creciente de profundidad, por ejemplo, raíz, primer hijo izquierdo, primer hijo derecho, primer hijo izquierdo del primer hijo izquierdo, etc. Un árbol de este tipo se presenta especialmente en un gráfico de ascendencia hasta una profundidad determinada, y la representación implícita se conoce como Ahnentafel (tabla de ascendencia).
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 top , sino también insert y pop .
Las estructuras de datos implícitas más sofisticadas incluyen el beap (montón biparental).
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 datan al menos de Ahnentafel, que fue introducido por Michaël Eytzinger en 1590 para su uso en genealogía. En informática formal, la primera estructura de datos implícita se considera generalmente como la lista ordenada, utilizada para la búsqueda binaria, que fue introducida por John Mauchly en 1946, en las Moore School Lectures , el primer conjunto de conferencias sobre cualquier tema relacionado con la informática. [4] [5] El montón binario fue introducido en Williams (1964) para implementar el heapsort . [5] La noción de una estructura de datos implícita fue formalizada en Munro & Suwanda (1980), como parte de la introducción y análisis del beap . [5]
Consulte las publicaciones de Hervé Brönnimann, J. Ian Munro y Greg Frederickson.
![{\estilo de visualización [0,N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/703d57dca548a7f9d927247c2a27b67666aebdd5)