
In computer science, Iacono's working set structure〔 is a comparison based dictionary. It supports insertion, deletion and access operation to maintain a dynamic set of $n$ elements. The working set of an item $x$ is the set of elements that have been accessed in the structure since the last time that $x$ was accessed (or inserted if it was never accessed). Inserting and deleting in the working set structure takes $O(\backslash log\; n)$ time while accessing an element $x$ takes $O(\backslash log\; w(x))$. Here, $w(x)$ represents the size of the working set of $x$. ==Structure== To store a dynamic set of $n$ elements, this structure consists of a series of ''Red–black trees'', or other ''Selfbalancing binary search trees'' $T\_1,\; T\_2,\; \backslash ldots,\; T\_k$, and a series of ''deques'' (Doubleended queues) $Q\_1,\; Q\_2,\; \backslash ldots\; Q\_k$, where $k\; =\; \backslash lceil\; \backslash log\backslash log\; n\backslash rceil$. For every $1\backslash leq\; i\backslash leq\; k$, tree $T\_i$ and deque $Q\_i$ share the same contents and pointers are maintained between their corresponding elements. For every $i\; <\; k$, the size of $T\_i$ and $Q\_i$ is $2^$. Tree $T\_k$ and deque $Q\_k$ consist of the remaining elements, i.e., their size is $n\; \; \backslash sum\_^\; 2^$. Therefore, the number of items in all trees and the number of elements in all deques both add up to $n$. Every element that has been inserted in the data structure is stored in exactly one of the trees and its corresponding deque. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Iacono's working set structure」の詳細全文を読む スポンサード リンク
