Academic
Publications
Binary Search Trees of Almost Optimal Height

Binary Search Trees of Almost Optimal Height,10.1007/BF01237235,Acta Informatica,Arne Andersson I,Christian Icking,Rolf Klein,Thomas Ottmann

Binary Search Trees of Almost Optimal Height   (Citations: 18)
BibTex | RIS | RefWorks Download
First we present a generalization of symmetric binary B-trees, SBB(k)-trees. The obtained structure has a height of only\Sigma(1 +1k ) log(n + 1)\Upsilon1, where k may be chosen to be any positive integer. The maintenancealgorithms require only a constant number of rotations per updatingoperation in the worst case. These properties together with the factthat the structure is relatively simple to implement makes it a usefulalternative to other search trees in practical...
Journal: Acta Informatica - ACTA , vol. 28, no. 2, pp. 165-178, 1990
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Within each list, the sets are sorted according to increasing cost (for example by keeping them in a binary search tree [1])...

    Arne Andersson. Combinatorial Auctions, an Example of Algorithm Theory in Real Life

    • ...In a paper from 1976 [16], Maurer et al. present a search tree, the k-neighbor tree, with a maximal height of c. log(n), where c can be chosen arbitrarily close to 1. The update time is O(log n), with the constant depending on c. Amazingly, no further progress on the problem seems to have been made until around 1990, when Lai and Andersson addressed it in their theses [3, 13] and in resulting papers [2, 4, 5, 6, 14], some of which are with ...

    Rolf Fagerberg. Binary Search Trees: How Low Can You Go?

    • ...Until recently, all solutions have been based on balanced search trees, such as AVL-trees [1], symmetric binary B-trees [6] (also denoted red-black trees [8]), SBB(k)-trees [4], weightbalanced trees [11], half-balanced trees [12], and k-neighbour trees [9]...
    • ...Using the terminology in [4], we say that a node in a 2-3 tree is represented by a pseudo-node containing one or two binary nodes...

    Arne Andersson. Balanced Search Trees Made Simple

    • ...It took almost a decade until really different classes of trees were found, which were also CLC [2]...

    Thomas Ottmann. Trees - A Personal View

    • ...The usefulness of this general result on CLC updating operations is demonstrated by showing that the red-black updating algorithms of [11] fall within this framework; CLC updating algorithms for the red-h-black trees of Icking et al. [7] (independently discovered by Ande~sson [2]) are obtained; and, finally, CLC updating algorithms for the classes of e~-balanced trees of Olivi~ [9] are derived, thereby solving (at least partially) a ...

    Thomas Ottmannet al. How to Update a Balanced Binary Tree with a Constant Number of Rotatio...

Sort by: