Re: Help with Deletion (not lazy) from AVL Trees

["Joel VanLaven" <jvl@nospam.ocsystems.com>]

Nick Roberts wrote in message <7c7co9$nvt$3@plug.news.pipex.net>...
>Two things occur to me: it's funny how the same algorithm
>can be expressed in so many (largely cosmetically) different ways, even in
>the same language; most people use red-black trees rather than AVL trees
>these days (often as a matter of fashion, I reckon), since (allegedly) RBTs
>generally have better (search?) performance.

Hmm.  It is my impression that the two common balanced binary tree
algorithms (well, the two I have run into) are AVL trees and 2-3-4 trees.
Both can be implemented as red-black trees.  Assuming the red-black
implementation of each, I believe that 2-3-4 trees are simpler and can be
optimized for faster insertion (and deletion ?)  Whereas AVL trees have a
better worst-case height (and hence in theory seach speed) but have more
complicated insertion.

In fact, I worked it out once and the worst case height of an AVL tree is
related to the Fibonnaci (why can't I spell that) sequence and through it
the golden ratio for about >
log base (1+sqrt(5))/2 (n) height where n is the number of nodes

On the other hand, red-black 2-3-4 trees are something like 2*log base 2 (n)
or rather log base sqrt(2) (n)

What is more, I belive that most 2-3-4 implementations will yield the worst
case in normal situations like sorted-order insertion whereas AVL trees will
not, it is a "wacky" order insertion that yields the worst case.  I'm not
positive of that though.

-- Joel VanLaven