Estructura del conjunto de trabajo de Iacono

En ciencias de la computación , la estructura del conjunto de trabajo de Iacono ^{[ 1 ]} es un diccionario basado en comparaciones . Admite operaciones de inserción, eliminación y acceso para mantener un conjunto dinámico de${\displaystyle n}$elementos. El conjunto de trabajo de un elemento${\displaystyle x}$es el conjunto de elementos a los que se ha accedido en la estructura desde la última vez que${\displaystyle x}$Se accedió a él (o se insertó si nunca se había accedido). Insertar y eliminar en la estructura del conjunto de trabajo lleva${\displaystyle O(\log n)}$tiempo mientras se accede a un elemento${\displaystyle x}$acepta${\displaystyle O(\log w(x))}$. Aquí,${\displaystyle w(x)}$representa el tamaño del conjunto de trabajo de${\displaystyle x}$.

Para almacenar un conjunto dinámico de${\displaystyle n}$elementos, esta estructura consiste en una serie de árboles rojo-negro u otros árboles de búsqueda binaria autoequilibrados${\displaystyle T_{1},T_{2},\ldots ,T_{k}}$y una serie de deques (colas de doble extremo)${\displaystyle Q_{1},Q_{2},\ldots Q_{k}}$, dónde${\displaystyle k=\lceil \log \log n\rceil }$. Por cada${\displaystyle 1\leq i\leq k}$, árbol${\displaystyle T_{i}}$y deque${\displaystyle Q_{i}}$comparten el mismo contenido y se mantienen punteros entre sus elementos correspondientes. Para cada${\displaystyle i<k}$, el tamaño de${\displaystyle T_{i}}$y${\displaystyle Q_{i}}$es${\displaystyle 2^{2^{i}}}$. Árbol${\displaystyle T_{k}}$y deque${\displaystyle Q_{k}}$consta de los elementos restantes, es decir, su tamaño es${\displaystyle n-\sum _{i=1}^{k-1}2^{2^{i}}}$Por lo tanto, el número de elementos en todos los árboles y el número de elementos en todas las deques suman ambos${\displaystyle n}$Cada elemento que se ha insertado en la estructura de datos se almacena en exactamente uno de los árboles y su correspondiente deque.

En las deques de esta estructura, los elementos se mantienen ordenados según el tamaño de su conjunto de trabajo . Formalmente, el elemento${\displaystyle x}$mentiras después${\displaystyle y}$en deque${\displaystyle Q_{i}}$si y solo si${\displaystyle w(x)<w(y)}$. Además, por cada${\displaystyle 1\leq i<k}$, los elementos en deque${\displaystyle Q_{i}}$tienen conjuntos de trabajo más pequeños que los elementos en deque${\displaystyle Q_{i+1}}$Esta propiedad se conoce como invariante del conjunto de trabajo. Cada operación en la estructura de datos mantiene la invariante del conjunto de trabajo.

La operación básica en esta estructura se llama desplazamiento de${\displaystyle h}$a${\displaystyle j}$, dónde${\displaystyle h}$y${\displaystyle j}$son índices de algunos árboles en la estructura. Se consideran dos casos en un cambio de${\displaystyle h}$a${\displaystyle j}$: Si${\displaystyle h<j}$, entonces para cada${\displaystyle h\leq i<j}$, tomados en orden ascendente, se extrae un elemento de la cola.${\displaystyle Q_{i}}$y puesto en cola en${\displaystyle Q_{i+1}}$El elemento correspondiente se elimina de${\displaystyle T_{i}}$y se insertó en${\displaystyle T_{i+1}}$El tiempo de ejecución de esta operación es${\displaystyle O(\sum _{i=h}^{j}\log |T_{i}|)=O(\sum _{i=h}^{j}\log 2^{2^{i}})=O(2^{j})}$. De forma análoga, si${\displaystyle j<h}$, entonces para cada${\displaystyle j<i\leq h}$, tomados en orden descendente, se extrae un elemento de la cola.${\displaystyle Q_{i}}$y puesto en cola en${\displaystyle Q_{i-1}}$El elemento correspondiente se elimina de${\displaystyle T_{i}}$y se insertó en${\displaystyle T_{i-1}}$El tiempo de ejecución de esta operación es${\displaystyle O(\sum _{i=j}^{h}\log |T_{i}|)=O(\sum _{i=j}^{h}\log 2^{2^{i}})=O(2^{h})}$. Independientemente del caso, después de una operación de turno, el tamaño de${\displaystyle T_{h}}$disminuye en uno mientras que el tamaño de${\displaystyle T_{j}}$aumenta en uno. Dado que los elementos en las deques están ordenados con respecto a los tamaños de sus conjuntos de trabajo, una operación de desplazamiento mantiene el conjunto de trabajo invariante.

Los árboles splay son árboles de búsqueda autoajustables introducidos por Sleator y Tarjan ^{[ 2 ]} en 1985. Utilizando la heurística de reestructuración, los árboles splay pueden realizar operaciones de inserción y eliminación en${\displaystyle O(\log n)}$tiempo amortizado , sin almacenar ninguna información de saldo en los nodos. Además, el Teorema del Conjunto de Trabajo para árboles splay establece que el costo de acceder a un elemento en un árbol splay es${\displaystyle O(\log w(x))}$Amortizado . La estructura del conjunto de trabajo de Iacono obtiene el mismo tiempo de ejecución para búsqueda, inserción y eliminación en el peor de los casos. Por lo tanto, ofrece una alternativa a los árboles splay.