From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id D41CDBC69 for ; Sun, 22 Oct 2006 02:13:48 +0200 (CEST) Received: from barrayar.com ([216.139.135.60]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id k9M0Dlnc011393 for ; Sun, 22 Oct 2006 02:13:48 +0200 Received: from localhost (localhost [127.0.0.1]) by barrayar.com (Postfix) with ESMTP id A67E93B177; Sat, 21 Oct 2006 20:15:12 -0400 (EDT) Date: Sat, 21 Oct 2006 20:15:12 -0400 (EDT) From: Brian Hurt X-X-Sender: bhurt@localhost To: David Monniaux Cc: caml-list Subject: Re: [Caml-list] tree balancing in Set and Map In-Reply-To: <453AB54C.50201@ens.fr> Message-ID: References: <453AB54C.50201@ens.fr> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Miltered: at discorde with ID 453AB7BC.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; monniaux:01 subtrees:01 caml's:01 wrote:01 caml-list:01 slight:01 data:02 tree:02 tree:02 generally:03 heh:03 balanced:04 brian:05 brian:05 structure:06 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