Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem |
| |
Authors: | George Lagogiannis Christos Makris Athanasios Tsakalidis |
| |
Institution: | aDepartment of Computer Engineering and Informatics, University of Patras, 26500 Patras, Greece;bComputer Technology Institute, P.O. Box 1192, 26110 Patras, Greece |
| |
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|=2w. We present a data structure that uses O(|U|/log|U|+n) space, performs all the operations in O(loglog|U|) time and needs 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. |
| |
Keywords: | Data structures Worst case complexity Predecessor problem Lower bounds Search trees |
本文献已被 ScienceDirect 等数据库收录! |
|