Academic
Publications
Balanced Search Trees Made Simple

Balanced Search Trees Made Simple,10.1007/3-540-57155-8_236,Arne Andersson

Balanced Search Trees Made Simple   (Citations: 13)
BibTex | RIS | RefWorks Download
. 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...
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.
    • ...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 red-black trees [9] and the recently introduced rank-balanced 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 Senet 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 B-trees [3] and Sedgewick’s related left-leaning red-black trees [4,11]...

    Bernhard Haeupleret al. Rank-Balanced 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 2-3 trees...

    Prabhakar Ragde. The chilling descent: making the transition to a conventional curricul...

    • ...AA trees [2] (see also [28, §18.6]) Report/Search-trees...

    Jyrki Katajainen. Mini-project: Safe standard-library containers

    • ...According to (Andersson, 1993), even algorithms taught in introductory university courses are not used in practice if they are too complex...

    Franjo Plavecet al. On Digital Search Trees - A Simple Method for Constructing Balanced Bi...

Sort by: