(Mathematical expressions are simplified in this html-document)
Footnote: log denotes the logarithm to the base 2 and n denotes the number of elements stored in the tree.
First we present a generalization of
symmetric binary B-trees,
SBB(k)-trees.
The obtained structure has a
height of only ceiling( (1+1/k)log(n+1) ),
where k may be chosen to be
any positive
integer.
The maintenance algorithms require
only a constant number of rotations
per updating operation in the worst case.
These properties together with the fact
that the structure is relatively simple
to implement makes it a useful
alternative to other search trees
in practical applications.
Then, by
using an SBB(k)-tree with a varying
k we achieve a structure with a logarithmic
amortized cost per update
and a height of log n + o(log n).
This result is an improvement of the upper bound
on the height of a dynamic binary search
tree.
By maintaining two trees simultaneously the amortized
cost is transformed into a worst-case cost.
Thus, we have improved the worst-case complexity of the dictionary problem.