| A unified access bound on comparison-based dynamic dictionaries (2008) | |||||||||||||||
Abstract | |||||||||||||||
| We present a dynamic comparison-based search structure that supports insert, delete, and search 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, then the amortized cost to access element x is O(miny log(w(y) + d(x, y) + 2)), where d(x, y) denotes the rank distance between x and y among the current set of elements. This property generalizes the working-set and dynamic-finger properties of splay trees. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||