vlestivill@watdragon.waterloo.edu (Vlad (Vladimir Estivill-Castro)) (08/14/89)
DATA STRUCTURING GROUP MEETING Wednesday August 16th, 1989. noon. DC-1304 Arne Andersson Department of Computer Science Lund University Lund, Sweden will speak on Optimal Bounds on the Dictionary Problem ABSTRACT Some new efficient solutions to the dictionary problem are presented. First, we introduce the SBB(k)-tree, a generalization of the symmetric binary B-tree. The obtained structure has a maximum height of (1+1/k)log n, where k may be any positive integer. The maintenance algorithms require only a constant amount of restructuring work per updating operation in the worst case. These properties together with the fact that the structure is easy to implement makes it a useful data structure for practical applications. Second, we give an improved upper bound on the dictionary problem. Using a modification of the SBB(k)-tree we achieve a structure with logarithmic cost per update and a maximum height of log n + o(log n), which is optimal in the leading term. Finally, we present a new data structure, the epsilon-tree. This tree is based on the k-neighbor tree and allows updates to be performed in Theta(log n) time in the worst case. The number of comparisons required per operation is log n + 1 + epsilon where epsilon is an arbitrary positive constant. Thus, we have given an upper bound on the dictionary problem which is only a small additive constant from the lower bound.