🚀 go-pugleaf

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.