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
(3)
Search Trees
Skip List
Theory and Practice
Related Publications
(13)
Binary BTrees for Virtual Memory
Binary search trees of bounded balance
Data structures and problem solving using Java
A Dichromatic Framework for Balanced Trees
Symmetric Binary BTrees: Data Structure and Maintenance Algorithms
Subscribe
Academic
Publications
Balanced Search Trees Made Simple
Balanced Search Trees Made Simple,10.1007/3540571558_236,Arne Andersson
Edit
Balanced Search Trees Made Simple
(
Citations: 13
)
BibTex

RIS

RefWorks
Download
Arne Andersson
. As a contribution to the recent debate on simple implementationsof dictionaries, we present new maintenance algorithms for balancedtrees. In terms of code simplicity, our algorithms compare favourablywith those for deterministic and probabilistic skip lists.1 IntroductionIt is well known that there is a huge gap between
theory and practice
in computerprogramming. While companies producing computers or cars are anxious to usethe best technology available  at least they try to...
Conference:
Workshop on Algorithms and Data Structures  WADS
, pp. 6071, 1993
DOI:
10.1007/3540571558_236
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
)
Citation Context
(9)
...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...
...At least some authors, however, have suggested storing complete rank information for balanced trees, claiming that it simplies rebalancing [
3
]...
Siddhartha Sen
,
et al.
Deletion Without Rebalancing in Balanced Binary Trees
...Since the invention of AVL trees [1] in 1962, many alternatives [
2
,3,4,5,7,10,9,11] have been proposed, with the goal of simpler implementation or better performance or both...
...Simpler implementations of balanced trees include Andersson’s implementation [
2
] of Bayer’s binary Btrees [3] and Sedgewick’s related leftleaning redblack trees [4,11]...
Bernhard Haeupler
,
et al.
RankBalanced Trees
...(We must sketch why the expected depth of a node in a random BST is logarithmic.) Without randomness, and taking deletion into account, probably the most concise and understandable imperative code is that for AA trees [
3
], which mimic 23 trees...
Prabhakar Ragde
.
The chilling descent: making the transition to a conventional curricul...
...AA trees [
2
] (see also [28, §18.6]) Report/Searchtrees...
Jyrki Katajainen
.
Miniproject: Safe standardlibrary containers
...According to (
Andersson, 1993
), even algorithms taught in introductory university courses are not used in practice if they are too complex...
Franjo Plavec
,
et al.
On Digital Search Trees  A Simple Method for Constructing Balanced Bi...
References
(14)
Skip lists: a probabilistic alternative to balanced trees
(
Citations: 526
)
William Pugh
Journal:
Communications of The ACM  CACM
, vol. 33, no. 6, pp. 668676, 1990
Binary Search Trees of Almost Optimal Height
(
Citations: 18
)
Arne Andersson I
,
Christian Icking
,
Rolf Klein
,
Thomas Ottmann
Journal:
Acta Informatica  ACTA
, vol. 28, no. 2, pp. 165178, 1990
Implementing Dictionaries Using Binary Trees of Very Small Height
(
Citations: 11
)
Hermann A. Maurer
,
Thomas Ottmann
,
Hanswerner Six
Journal:
Information Processing Letters  IPL
, vol. 5, no. 1, pp. 1114, 1976
Deterministic skip lists
(
Citations: 43
)
J. Ian Munrot
,
Thomas Papadakist
,
Robert Sedgewick
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 367375, 1992
An algorithm for the organization of information
(
Citations: 155
)
G. M. Skii
,
Ye. M. Landis
Published in 1962.
Sort by:
Citations
(13)
Deletion Without Rebalancing in Balanced Binary Trees
(
Citations: 1
)
Siddhartha Sen
,
Robert Endre Tarjan
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 14901499, 2010
RankBalanced Trees
(
Citations: 4
)
Bernhard Haeupler
,
Siddhartha Sen
,
Robert Endre Tarjan
Conference:
Workshop on Algorithms and Data Structures  WADS
, pp. 351362, 2009
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
A Survey on Maintaining Binary Search Tree in Optimal Shape
InayaturRehman
,
S.u.R. Khan
,
M. Khayal
Conference:
International Conference on Information Management and Engineering  ICIME
, 2009
The chilling descent: making the transition to a conventional curriculum
Prabhakar Ragde
Published in 2008.