A unified access bound on comparison-based dynamic dictionaries

We present a dynamic comparison-based search structure that supports insertions, deletions, and searches within the unified bound. The unified bound specifies that it is quick to access an element that is near a recently accessed element. More precisely, if w(y)$w\left(y\right)$ distinct elements have been accessed since the last access to element y$y$, and d(x,y)$d(x,y)$ denotes the rank distance between x$x$ and y$y$ among the current set of elements, then the amortized cost to access element x$x$ is O(_minylogw(y)+d(x,y)+2])$O({min}_{y}logw\left(y\right)+d(x,y)+2])$. This property generalizes the working-set and dynamic-finger properties of splay trees.