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
(6)
Binary Search Tree
Design Space
Potential Function
Time Use
Bottom Up
Top Down
Related Publications
(2)
Balanced Search Trees Made Simple
Deletion Without Rebalancing in Balanced Binary Trees
Subscribe
Academic
Publications
RankBalanced Trees
RankBalanced Trees,10.1007/9783642033674_31,Bernhard Haeupler,Siddhartha Sen,Robert Endre Tarjan
Edit
RankBalanced Trees
(
Citations: 4
)
BibTex

RIS

RefWorks
Download
Bernhard Haeupler
,
Siddhartha Sen
,
Robert Endre Tarjan
Since the invention of AVL trees in 1962, a wide variety of ways to balance
binary search
trees have been proposed. Notable are redblack trees, in which bottomup rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worstcase. But the
design space
of balanced trees has not been fully explored. We introduce the rankbalanced tree, a relaxation of AVL trees. Rankbalanced trees can be rebalanced bottomup after an insertion or deletion in O(1) amortized time and at most two rotations worstcase, in contrast to redblack trees, which need up to three rotations per deletion. Rebalancing can also be done topdown with fixed lookahead in O(1) amortized time. Using a novel analysis that relies on an exponential potential function, we show that both bottomup and topdown rebalancing modify nodes exponentially infrequently in their heights.
Conference:
Workshop on Algorithms and Data Structures  WADS
, pp. 351362, 2009
DOI:
10.1007/9783642033674_31
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
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(4)
...For all existing forms of balanced trees, of which there are many [3, 4, 5, 9,
10
, 12, 13, 16], deletion is at least a little more complicated than insertion, although for some kinds of balanced search trees, notably redblack trees [9] and the recently introduced rankbalanced trees [10], rebalancing after a deletion can be done in O(1) rotations...
...For all existing forms of balanced trees, of which there are many [3, 4, 5, 9, 10, 12, 13, 16], deletion is at least a little more complicated than insertion, although for some kinds of balanced search trees, notably redblack trees [9] and the recently introduced rankbalanced trees [
10
], rebalancing after a deletion can be done in O(1) rotations...
...To obtain our bounds we use an exponential potential function, an idea we have also used [
10
] to analyze rankbalanced trees...
...needed in AVL [2], rankbalanced [
10
], and redblack trees [9]...
...Our tree terminology is the same as in [
10
]...
...An exponential potential function of the kind rst used by us to analyze another kind of balanced tree [
10
] gives our most important result: a ravl tree built from an empty tree has height logarithmic in the number of insertions, even if deletions are intermixed arbitrarily...
...These results hold for rankbalanced trees and redblack trees, but the constant factors are worse [
10
]; they do not hold for AVL trees subject to intermixed insertions and deletions...
...In our preliminary experiments, we compared ravl trees (without periodic rebuilding) to standard redblack trees [9] and rankbalanced trees [
10
] on typical input sequences...
Siddhartha Sen
,
et al.
Deletion Without Rebalancing in Balanced Binary Trees
...Some of them guarantee an O(1) worstcase number of structural changes (pointers/fields modifications) after an insertion or a deletion operation [12,19,
11
,13,10,6]...
Prosenjit Bose
,
et al.
Skip Lift: A Probabilistic Alternative to RedBlack Trees
...We use exponential potential functions similar to those we have used to analyze balanced binary trees [
9
, 19]...
...We have obtained similar results for balanced binary trees [
9
, 19]...
Siddhartha Sen
,
et al.
Deletion without Rebalancing in Multiway Search Trees
...For all existing forms of balanced trees, of which there are many [3, 4, 5, 9,
10
, 12, 13, 16], deletion is at least a little more complicated than insertion, although for some kinds of balanced search trees, notably redblack trees [9] and the recently introduced rankbalanced trees [10], rebalancing after a deletion can be done in O(1) rotations...
...For all existing forms of balanced trees, of which there are many [3, 4, 5, 9, 10, 12, 13, 16], deletion is at least a little more complicated than insertion, although for some kinds of balanced search trees, notably redblack trees [9] and the recently introduced rankbalanced trees [
10
], rebalancing after a deletion can be done in O(1) rotations...
...To obtain our bounds we use an exponential potential function, an idea we have also used [
10
] to analyze rankbalanced trees...
...needed in AVL [2], rankbalanced [
10
], and redblack trees [9]...
...Our tree terminology is the same as in [
10
]...
...An exponential potential function of the kind rst used by us to analyze another kind of balanced tree [
10
] gives our most important result: a ravl tree built from an empty tree has height logarithmic in the number of insertions, even if deletions are intermixed arbitrarily...
...These results hold for rankbalanced trees and redblack trees, but the constant factors are worse [
10
]; they do not hold for AVL trees subject to intermixed insertions and deletions...
...In our preliminary experiments, we compared ravl trees (without periodic rebuilding) to standard redblack trees [9] and rankbalanced trees [
10
] on typical input sequences...
Siddhartha Sen
,
et al.
Deletion Without Rebalancing in Balanced Binary Trees
References
(10)
Balanced Search Trees Made Simple
(
Citations: 13
)
Arne Andersson
Conference:
Workshop on Algorithms and Data Structures  WADS
, pp. 6071, 1993
Binary BTrees for Virtual Memory
(
Citations: 21
)
Rudolf Bayer
Conference:
International Conference on Management of Data  SIGMOD
, pp. 219235, 1971
Symmetric Binary BTrees: Data Structure and Maintenance Algorithms
(
Citations: 131
)
Rudolf Bayer
Journal:
Acta Informatica  ACTA
, vol. 1, no. 4, pp. 290306, 1972
A Storage Scheme for HeightBalanced Trees
(
Citations: 6
)
Mark R. Brown
Journal:
Information Processing Letters  IPL
, vol. 7, no. 5, pp. 231232, 1978
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
Sort by:
Citations
(4)
Deletion Without Rebalancing in Balanced Binary Trees
(
Citations: 1
)
Siddhartha Sen
,
Robert Endre Tarjan
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 14901499, 2010
Skip Lift: A Probabilistic Alternative to RedBlack Trees
Prosenjit Bose
,
Karim Douïeb
,
Pat Morin
Published in 2010.
Deletion without Rebalancing in Multiway Search Trees
(
Citations: 2
)
Siddhartha Sen
,
Robert Endre Tarjan
Conference:
International Symposium on Algorithms and Computation  ISAAC
, pp. 832841, 2009
Deletion Without Rebalancing in Balanced Binary Trees
Siddhartha Sen
,
Robert E. Tarjan