New Dynamic Balanced Search Trees with Worst-Case Constant Update Time

We present new search trees with worst-case O(1) update time and O(log n) search time, storing n elements in linear space, in the Pointer Machine (PM) model of computation. In addition, these trees can easily support finger searches in time O(log d) and update operations in worst-case O(log* n) time. The parameter d represents the number of elements (distance) between the search element and an element pointed to by a pointer termed finger. Our data structure is based on a previous result by Fleischer that exhibits the same asymptotic time and space complexities for simple search trees. We improve on this result by handling deletions in an explicit way without using the standard trick of global rebuilding. This is the first search tree that combines worst-case update times with a local rebalancing scheme without using global rebuilding to tackle deletions. In addition, insight is acquired from the construction of these trees as to why deletions are considered more difficult than insertions in the (a,b)-trees setting. Finally, we hope that these techniques may lead to a simpler version of the constant update finger search tree presented recently by Brodal et al. [5].