tree balancing in Set and Map

tree balancing in Set and Map

[David Monniaux]

I wonder about something: the first balanced tree data structure 
described in algorithmics courses is generally the AVL tree, where the 
heights of the subtrees differ by at most 1. In Caml's implementation, 
they are allowed to differ by at most 2.

A quick analysis of the functions h1(n) and h2(n) governing the maximal 
height of a tree with n nodes with respectively maximal height 
differences of 1 and 2 shows that asymptotically h2(n) is about 1.25 
times h1(n).

Why this choice then? Was it easier to implement? Is there some hidden 
effect like rotations not being needed as often? How about some 
bibliographic references? :-)

(Yes, you may have guessed, I'm not an algorithmician.)

Re: [Caml-list] tree balancing in Set and Map

[Brian Hurt]

On Sun, 22 Oct 2006, David Monniaux wrote:

> I wonder about something: the first balanced tree data structure described in 
> algorithmics courses is generally the AVL tree, where the heights of the 
> subtrees differ by at most 1. In Caml's implementation, they are allowed to 
> differ by at most 2.

Heh.  I asked this question myself a couple of months back.  The response 
was basically that yes, it was a delibert decision- by allowing heights to 
differ by more, this limits the amount of rebalancing that is needed, 
making inserts faster.  Testing the two different approachs showed that 
the increase in speed for inserts was enough to justify the slight slowing 
of finds.

A comment to this effect in the code might not be a bad idea...

Brian