Binary search trees of almost optimal height (Q911247)

First we present a generalization of symmetric binary B-trees, SBB(k)- trees. The obtained structure has a height of only \(\lceil (1+\frac{1}{k})\log (n+1)\rceil\), 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.