A unified access bound on comparison-based dynamic dictionaries

AbstractWe 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) distinct elements have been accessed since the last access to element y, and d(x,y) denotes the rank distance between x and y among the current set of elements, then the amortized cost to access element x is O(minylog[w(y)+d(x,y)+2]). This property generalizes the working-set and dynamic-finger properties of splay trees