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 A284EBC29 for ; Fri, 4 Aug 2006 22:08:42 +0200 (CEST) Received: from janestcapital.com ([66.155.124.107]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k74K8dmL012267 for ; Fri, 4 Aug 2006 22:08:41 +0200 Received: from [192.168.250.117] [209.213.205.130] by janestcapital.com with ESMTP (SMTPD32-8.13) id A94537ED00C2; Fri, 04 Aug 2006 16:08:37 -0400 Message-ID: <44D3A944.3060907@janestcapital.com> Date: Fri, 04 Aug 2006 16:08:36 -0400 From: Brian Hurt User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: caml-list@yquem.inria.fr Subject: map implementation question Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 44D3A947.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; worst-case:01 inserting:01 bug:01 minor:01 tree:02 tree:02 latter:03 element:03 element:03 logic:03 balanced:04 brian:04 brian:04 correct:08 41%:88 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 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 ? The latter will cause more rotations, but keep the tree more balanced. The worst-case access of the >= version is log base 3/2, while the > is log base 4/3, which means that the >= will be about 41% (log(3/2)/log(4/3) ~ 1.41). Both are correct in that they return the right answer and are still O(log(N)) performance, it's a question of performance of looking up an element in the tree vr.s the cost of inserting an element into the tree. Was there a reason it was done this way, or is this a (minor) bug? Brian