Структура рабочего набора Яконо

Структура данных рабочего набора Яконо
Изобретенный	2001
Изобретён	Джон Яконо
Асимптотическая сложность в большой записи О
Космос	На ) ​ ​
Поиск	О (журнал w(x) )
Вставлять	О ( войти )
Удалить	О ( войти )

В информатике структура рабочего набора Яконо. основанный на сравнении словарь, . Он поддерживает операции вставки, удаления и доступа для поддержания динамического набора $n$ элементы. Рабочий набор элемента $x$ — это набор элементов, к которым осуществлялся доступ в структуре с момента последнего использования $x$ был доступен (или вставлен, если к нему никогда не обращались). Вставка и удаление в структуре рабочего набора занимает $O(\log n)$ время при доступе к элементу $x$ берет $O(\log w(x))$. Здесь, $w(x)$ представляет размер рабочего набора $x$.

Структура

Пример поиска по $x$ в структуре рабочего набора. После нахождения $x$, он удален из $T_{4}$ и вставлен в $T_{1}$. Наконец, выполняется сдвиг от 1 к 4, при котором элемент удаляется из $T_{i}$ и вставлен в $T_{i+1}$ для $1\leq i<4$.

Чтобы сохранить динамический набор $n$ элементы, эта структура состоит из серии красно-черных деревьев или других самобалансирующихся бинарных деревьев поиска. $T_{1},T_{2},\ldots ,T_{k}$и серия деков (двусторонние очереди) $Q_{1},Q_{2},\ldots Q_{k}$, где $k=\lceil \log \log n\rceil$. Для каждого $1\leq i\leq k$, дерево $T_{i}$ и поэтому $Q_{i}$ имеют одинаковое содержимое, и между соответствующими элементами сохраняются указатели. Для каждого $i<k$, размер $T_{i}$ и $Q_{i}$ является $2^{2^{i}}$. Дерево $T_{k}$ и поэтому $Q_{k}$ состоят из остальных элементов, т. е. их размер равен $n-\sum _{i=1}^{k-1}2^{2^{i}}$. Таким образом, количество элементов во всех деревьях и количество элементов во всех деках в сумме составляют $n$. Каждый элемент, вставленный в структуру данных, сохраняется ровно в одном из деревьев и соответствующем ему деке.

Рабочий набор Инвариант

В деках этой структуры элементы хранятся в отсортированном порядке в соответствии с размером их рабочего набора. Формально элемент $x$ лежит после $y$ в двухстороннем порядке $Q_{i}$ тогда и только тогда, когда $w(x)<w(y)$. Более того, для каждого $1\leq i<k$, элементы в деке $Q_{i}$ иметь меньшие рабочие наборы, чем элементы в деке $Q_{i+1}$. Это свойство называется инвариантом рабочего набора. Каждая операция в структуре данных поддерживает инвариант рабочего набора.

Операции

Основная операция в этой структуре называется сдвигом от $h$ к $j$, где $h$ и $j$ являются индексами некоторых деревьев в структуре. Два дела рассматриваются в порядке перехода от $h$ к $j$: Если $h<j$, то для каждого $h\leq i<j$, взятый в порядке возрастания, элемент выводится из очереди $Q_{i}$ и поставлен в очередь $Q_{i+1}$. Соответствующий элемент удален из $T_{i}$ и вставлен в $T_{i+1}$. Время выполнения этой операции $O(\sum _{i=h}^{j}\log |T_{i}|)=O(\sum _{i=h}^{j}\log 2^{2^{i}})=O(2^{j})$. Аналогично, если $j<h$, то для каждого $j<i\leq h$, взятый в порядке убывания, элемент выводится из очереди $Q_{i}$ и поставлен в очередь $Q_{i-1}$. Соответствующий элемент удален из $T_{i}$ и вставлен в $T_{i-1}$. Время выполнения этой операции $O(\sum _{i=j}^{h}\log |T_{i}|)=O(\sum _{i=j}^{h}\log 2^{2^{i}})=O(2^{h})$. В любом случае, после смены размер $T_{h}$ уменьшается на единицу, тогда как размер $T_{j}$ увеличивается на единицу. Поскольку элементы в деках сортируются по размерам их рабочих наборов, операция сдвига сохраняет рабочий набор инвариантным.

Поиск

Чтобы найти элемент $x$, искать $x$ в $T_{1},T_{2},\ldots T_{k}$, в порядке возрастания, пока не будет найдено дерево $T_{j}$ содержащий $x$. Если дерево не найдено, поиск не увенчался успехом. Если $x$ найден, он удаляется из $T_{j}$ а затем вставил в $T_{1}$, т. е. он перемещается к передней части конструкции. Поиск завершается переходом от $1$ к $j$ который восстанавливает размер каждого дерева и каждой деки до их размера до операции поиска. Время выполнения этого поиска $O(\sum _{i=1}^{j}\log 2^{2^{i}})=O(2^{j})$ если поиск был успешным, или $O(\sum _{i=j}^{k}\log 2^{2^{i}})=O(2^{k})=O(\log n)$ в противном случае. По свойству Рабочее множество каждый элемент в деревьях $T_{1},T_{2},\ldots ,T_{j-1}$ принадлежит рабочему множеству $x$. В частности, каждый элемент в $T_{j-1}$ принадлежит рабочему множеству $x$ и, следовательно, $w(x)>|T_{j-1}|=2^{2^{j-1}}$. Таким образом, время успешного поиска равно $O(2^{j})=O(\log 2^{2^{j-1}})=O(\log w(x))$.

Вставлять

Вставка элемента $x$ в структуру осуществляется путем вставки $x$ в $T_{1}$ и постановка его в очередь $Q_{1}$. Вставка завершается сдвигом от $1$ к $k$. Чтобы избежать переполнения, если $|T_{k}|=2^{2^{k}}$ до сдвига, т. е. если последнее дерево заполнено, то $k$ увеличивается и появляется новый пустой $T_{k}$ и $Q_{k}$ создан. Во время выполнения этой операции преобладает переход от $1$ к $k$ чье время работы $O(2^{k})=O(2^{\log \log n})=O(\log n)$. Поскольку элемент $x$, чей рабочий набор наименьший, ставится в очередь $Q_{1}$, инвариант рабочего набора сохраняется после сдвига.

Удалить

Удаление элемента $x$ делается путем поиска $x$ на каждом дереве структуры в порядке возрастания, пока не будет найдено дерево $T_{j}$ который его содержит (если он не найден, удаление не удалось). Элемент $x$ удаляется из $T_{j}$ и $Q_{j}$. Наконец, переход от $k$ к $j$ сохраняет размер $T_{j}$ равный $2^{2^{j}}$. Время выполнения этой операции $O(2^{k})=O(\log n)$. Инвариант рабочего набора сохраняется, поскольку удаление элемента не меняет порядок рабочего набора элементов.

Обсуждение

Деревья Splay — это самонастраивающиеся деревья поиска, представленные Sleator и Tarjan. в 1985 году. Используя эвристику реструктуризации, деревья расширения могут выполнять операции вставки и удаления в $O(\log n)$ амортизированное время, без хранения какой-либо информации о балансе на узлах. Более того, теорема о рабочем наборе для расширенных деревьев утверждает, что стоимость доступа к элементу в расширенном дереве равна $O(\log w(x))$ амортизируется . Структура рабочего набора Iacono обеспечивает одинаковое время поиска, вставки и удаления в худшем случае. Поэтому предлагаем альтернативу раскидистым деревьям.