caa a22 4500 467989664 CHVBK 20180323112541.0 cr unu---uuuuu 170328e19900201xx s 000 0 eng 10.1007/BF01237235 doi (NATIONALLICENCE)springer-10.1007/BF01237235 Binary search trees of almost optimal height [Elektronische Daten] [Arne Andersson, Christian Icking, Rolf Klein, Thomas Ottmann] Summary: First we present a generalization of symmetric binary B-trees, SBB(k)-trees. The obtained structure has a height of only $$\left[ {\left( {1 + \frac{1}{k}} \right)\log (n + 1)} \right]^1 $$ , wherek 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 varyingk we achieve a structure with a logarithmic amortized cost per update and a height of logn+o(logn). 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. Springer-Verlag, 1990 Andersson Arne Department of Computer Science, Lund University, Box 118, S-22100, Lund, Sweden aut Icking Christian FB 6/Praktische softwareorientierte Informatik, Universität-Gesamthochschule Essen, Schützenbahn 70, W-4300, Essen 1, Federal Republic of Germany aut Klein Rolf FB 6/Praktische softwareorientierte Informatik, Universität-Gesamthochschule Essen, Schützenbahn 70, W-4300, Essen 1, Federal Republic of Germany aut Ottmann Thomas Institut für Informatik, Universität Freiburg, Rheinstrasse 10-12, W-7800, Freiburg, Federal Republic of Germany aut Acta Informatica Springer-Verlag 28/2(1990-02-01), 165-178 0001-5903 28:2<165 1990 28 236 https://doi.org/10.1007/BF01237235 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01237235 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Andersson Arne Department of Computer Science, Lund University, Box 118, S-22100, Lund, Sweden aut NATIONALLICENCE 700 1- Icking Christian FB 6/Praktische softwareorientierte Informatik, Universität-Gesamthochschule Essen, Schützenbahn 70, W-4300, Essen 1, Federal Republic of Germany aut NATIONALLICENCE 700 1- Klein Rolf FB 6/Praktische softwareorientierte Informatik, Universität-Gesamthochschule Essen, Schützenbahn 70, W-4300, Essen 1, Federal Republic of Germany aut NATIONALLICENCE 700 1- Ottmann Thomas Institut für Informatik, Universität Freiburg, Rheinstrasse 10-12, W-7800, Freiburg, Federal Republic of Germany aut NATIONALLICENCE 773 0- Acta Informatica Springer-Verlag 28/2(1990-02-01), 165-178 0001-5903 28:2<165 1990 28 236 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer