Re: [Caml-list] Why AVL-tree?

[Diego Olivier Fernandez Pons <dofp.ocaml@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 5202 bytes --]

    Hi


> At the time Set was written, no efficient algorithms for whole-set
> operations (union, intersection, difference, etc) were known for
> red-black trees.  I'm not sure they are known today.
>

The answer is no and I will try to explain.

When doing a set union, at some point you will have to merge two disjoint
sets represented each by a tree

[1 .. 10] union [15 .. 22]

At that point you need to know the "size" of each tree because if both
trees are the same size you just need to append them

    return Node ([1..10], [15..22])

while if one tree is bigger than the other, you will need to cut that tree
into smaller pieces and reorganize them (a "rotation").

    divide [1..10] into [1..5], [6..10]
    return Node([1..5], Node ([6..10], [15..22]))

The AVL implementation of OCaml gives you the "size" of each tree, its the
extra int in the constructor

    'a tree = Empty | Node 'a tree * 'a * 'a tree * int <--- here

it is equal to the longest path in the tree

    f = function E -> 0 | Node (l, _, r, h) -> 1 + max (f l, fr)

If you implement Weight-balanced trees, that value is the cardinal of the
set represented by the tree.

If you use red-black or "traditional AVL" representation, that extra bit
just tells you if the tree is leaning towards the left or towards the
right, but doesn't tell you any information about the global "size" of the
tree. Which means you cannot implement set union directly. You have to
traverse full tree in O(n) to recompute that information.

There is at least one library in Haskell that implements AVL trees that
way, it uses -1 | 0 | 1 information for most operations and recomputes the
longest path for all trees when doing set operations, then discards that
info.

There is also a way to implement red black trees to do set operations just
like (non-traditional) AVLs. It is described in Olivié H.J A new class of
balanced search trees : half balanced search trees, RAIRO Informatique
Théorique 16, 51 71 - also in his PhD Thesis.

Basically a tree is red-black when shortest-branch * 2 >= longest-branch
(cf. Constructing Red-Black trees, Ralf Hinze 1999 - easier to find than
Olivié's works)

So you can implement a tree structure that memorizes both the shortest
and the longest branch in each node

    'a tree = E | N of 'a tree * 'a * 'a tree * int * int <---- shortest
and longest

From there you just follow the same scheme than the AVL implementation in
the OCaml lib, you just need to cope with a couple of triple rotation cases.



> As for performance of insert/lookup operations, Jean-Christophe
> Filliâtre has measurements showing that OCaml's 2-imbalance AVL trees
> perform better than red-black trees.  It all depends on your ratio of
> insertions to lookups, of course.  But the 2-imbalance trick makes a
> big difference with textbook AVL trees.
>


This is a bit more difficult but in short "red-black trees do not implement
truly red-black trees" and "all implementations of red-black trees
implement a different approximation of red-black trees".

Any implementation of red-black trees that uses the 1 bit trick and where
insertions are in log (n) is not surjective. You can understand that as
meaning
(1) - some red-black trees will never be built by the balancing algorithm
(2) - sometimes you will give the balancing algorithm a red-black tree (=
has a provable red-black coloring) and it will still rebalance it instead
of noticing it's already balanced and returning it untouched.

The reason is insertion in red-black trees using the 1 bit trick is linear.
Meaning if I want a balancing algorithm that never falls into (1) or (2) I
cannot avoid linear time insertion. The result is all algorithms found in
the literature are log(n) approximations of the full algorithm. The only
algorithm that is truly logarithmic is again Olivié's thanks to it's
implicit representation of the red-black coloring.

From there, comparing performance of AVLs with "red-black trees" in general
makes no sense as the person that implemented them may have implemented any
arbitrary approximation of the full algorithm. This translates in the code
as a random number of "cases" to check for balancing : 4 for Okasaki, 27 in
the CLR, etc. With double, triple, quadruple rotations, according to how
"deep" the author was willing to go. Because what these guys are doing is
"unfolding" the linear behavior of the algorithm into a constant and
falling back into rebuilding any tree they are given for all other cases.

In any case, some benchmarks I did very, very, very longtime ago showed AVL
and Weight balanced are good all-purpose implementations. The advantage of
WB being it gives you the cardinality of the set in O(1). In some sense,
AVL is the log of WB (in the same way the height of a tree is the log of
its size).

        Diego Olivier


>
> - Xavier Leroy
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 7020 bytes --]