From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 0714FBB83 for ; Thu, 17 Aug 2006 13:37:27 +0200 (CEST) Received: from [128.93.11.95] (estephe.inria.fr [128.93.11.95]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k7HBbPfR022026; Thu, 17 Aug 2006 13:37:25 +0200 Message-ID: <44E454F5.2040406@inria.fr> Date: Thu, 17 Aug 2006 13:37:25 +0200 From: Xavier Leroy User-Agent: Mozilla Thunderbird 1.0.6-6mdk (X11/20050322) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Brian Hurt Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] map implementation question References: <44D3A944.3060907@janestcapital.com> In-Reply-To: <44D3A944.3060907@janestcapital.com> X-Enigmail-Version: 0.92.0.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 44E454F5.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; binary:01 red-black:01 height:98 wrote:01 caml-list:01 algorithm:01 bounds:02 tradeoff:03 let:03 logic:04 brian:04 anyway:05 xavier:06 xavier:06 inria:06 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 Brian Hurt wrote: > I was just looking at the map.ml implementation, and noticed that the > logic for when to do a rotation was: > if hl > hr + 2 then begin > Isn't this supposed to be: > if hl >= hr + 2 then begin No, it was a conscious decision to use height-balanced binary trees with an height imbalance of at most 2, rather than at most 1 as in standard AVL trees. As you note, log(N) access times are still guaranteed, and it's a tradeoff between lookup time vs. rebalancing time. Light experimentation suggested that imbalance <= 2 is globally more efficient than imbalance <= 1. Didn't try with larger imbalance bounds. This said, red-black trees would probably work faster anyway, but I'll let the algorithm experts on this list comment. - Xavier Leroy