En informática , una estructura de datos implícita o estructura de datos eficiente en el 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 llaman "implícitos" porque la posición de los elementos conlleva significado y relación entre elementos; esto 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 significa gastos generales constantes; en notación O grande , O (1) gastos generales. Una definición menos restrictiva es una estructura de datos sucinta , que permite una mayor sobrecarga.
Una estructura de datos implícita es aquella con una sobrecarga de espacio O (1) constante (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 aquella "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 vagos en la definición, definiéndola más estrictamente como una matriz única, con solo el tamaño retenido (un solo número de gastos generales), [1] o más vagamente como una estructura de datos con gastos generales constantes ( 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 estructura de datos sucinta , tal como la define Jacobson (1988); Munro y Suwanda (1980) lo denominaron semiimplícito . [3]
Una distinción fundamental es entre estructuras de datos estáticas (de solo lectura) y estructuras de datos dinámicas (que pueden modificarse). 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 se realizan operaciones de modificación (como la inserción en el caso de una lista ordenada). ineficiente.
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 enlazada , que tiene un puntero asociado a 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). 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 simple representar una matriz multidimensional como una única matriz unidimensional, junto con sus dimensiones. Por ejemplo, representar una matriz m × n como una lista única de longitud m·n , junto con los números myn (en lugar de como una matriz unidimensional de punteros a cada submatriz unidimensional). No es necesario que los elementos sean del mismo tipo, y una tabla de datos (una lista de registros ) también puede representarse 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 utilizar un tamaño único por campo, no por registro).
Un ejemplo menos trivial es representar una lista ordenada mediante una matriz ordenada , que permite realizar búsquedas 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 búsquedas en tiempo logarítmico, pero requiere punteros. Una matriz ordenada sólo es eficiente como estructura de datos estática, ya que la modificación de la lista es lenta (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, es decir, raíz, primer hijo izquierdo, primer hijo derecho, primer hijo izquierdo del primer hijo izquierdo, etc. para una tabla de ascendencia hasta una profundidad determinada, 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 estructura de datos implícita, concretamente 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 una 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 del 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 generalmente se considera la lista ordenada, utilizada para la búsqueda binaria, que fue introducida por John Mauchly en 1946, en las Conferencias de la Escuela Moore , el primer conjunto de conferencias sobre cualquier tema relacionado con la computadora. tema. [4] [5] El montón binario fue introducido en Williams (1964) para implementar heapsort . [5] 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 . [5]
Véanse las publicaciones de Hervé Brönnimann, J. Ian Munro y Greg Frederickson.
![{\displaystyle [0,N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/703d57dca548a7f9d927247c2a27b67666aebdd5)