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