Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Binary Search Tree
Search Trees
Subscribe
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
Edit
Binary Search Trees of Almost Optimal Height
(
Citations: 18
)
BibTex

RIS

RefWorks
Download
Arne Andersson I
,
Christian Icking
,
Rolf Klein
,
Thomas Ottmann
First we present a generalization of symmetric binary Btrees, 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. 165178, 1990
DOI:
10.1007/BF01237235
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
More »
Citation Context
(7)
...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 kneighbor 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 AVLtrees [1], symmetric binary Btrees [6] (also denoted redblack trees [8]), SBB(k)trees [
4
], weightbalanced trees [11], halfbalanced trees [12], and kneighbour trees [9]...
...Using the terminology in [
4
], we say that a node in a 23 tree is represented by a pseudonode 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 redblack updating algorithms of [11] fall within this framework; CLC updating algorithms for the redhblack 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 Ottmann
,
et al.
How to Update a Balanced Binary Tree with a Constant Number of Rotatio...
References
(22)
Efficient algorithms to globally balance a binary search tree
(
Citations: 33
)
Hsi Chang
,
S. Sitharama Iyangar
Journal:
Communications of The ACM  CACM
, vol. 27, no. 7, pp. 695702, 1984
Updating a Balanced Search Tree in O(1) Rotations
(
Citations: 49
)
Robert Endre Tarjan
Journal:
Information Processing Letters  IPL
, vol. 16, no. 5, pp. 253257, 1983
A Dichromatic Framework for Balanced Trees
(
Citations: 315
)
Leonidas J. Guibas
,
Robert Sedgewick
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 821, 1978
An algorithm for the organization of information
(
Citations: 155
)
G. M. Skii
,
Ye. M. Landis
Published in 1962.
Organization and Maintenance of Large Ordered Indices
(
Citations: 575
)
Rudolf Bayer
,
Edward M. McCreight
Journal:
Acta Informatica  ACTA
, vol. 1, pp. 173189, 1972
Sort by:
Citations
(18)
Combinatorial Auctions, an Example of Algorithm Theory in Real Life
Arne Andersson
Conference:
Birthday ...
, pp. 1321, 2003
General Balanced Trees
(
Citations: 28
)
Arne Andersson
Journal:
Journal of Algorithms  JAL
, vol. 30, no. 1, pp. 118, 1999
Optimal Binary Search Trees
(
Citations: 8
)
S. V. Nagaraj
Journal:
Theoretical Computer Science  TCS
, vol. 188, no. 12, pp. 144, 1997
Binary Search Trees: How Low Can You Go?
(
Citations: 5
)
Rolf Fagerberg
Conference:
Scandinavian Workshop on Algorithm Theory  SWAT
, pp. 428439, 1996
Confluently Persistent Deques via DataStructural Bootstrapping
(
Citations: 23
)
Adam L. Buchsbaum
,
Robert Endre Tarjan
Journal:
Journal of Algorithms  JAL
, vol. 18, no. 3, pp. 513547, 1995