Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
tree balancing in Set and Map
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2006-10-22 (00:13)
From: Brian Hurt <bhurt@s...>
Subject: Re: [Caml-list] tree balancing in Set and Map

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...