Article ID Journal Published Year Pages File Type
431382 Journal of Discrete Algorithms 2006 36 Pages PDF
Abstract

We consider the problem of maintaining a dynamic ordered set of n integers in a universe U under the operations of insertion, deletion and predecessor queries. The computation model used is a unit-cost RAM, with a word length of w   bits, and the universe size is |U|=w2|U|=2w. We present a data structure that uses O(|U|/log|U|+n)O(|U|/log|U|+n) space, performs all the operations in O(loglog|U|)O(loglog|U|) time and needs O(loglog|U|/logloglog|U|)O(loglog|U|/logloglog|U|) structural changes per update operation. The data structure is a simplified version of the van Emde Boas' tree introducing, in its construction and functioning, new concepts, which help to keep the important information for searching along the path of the tree, in a more compact and organized way.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,