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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 25F6EBC57 for ; Fri, 14 May 2010 20:47:41 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ah0DAMQ37UvRVdvbe2dsb2JhbACDGJpkCBUBARYiAx+tWDmCAIUDLohNAQEDBYEggwFqBA X-IronPort-AV: E=Sophos;i="4.53,232,1272837600"; d="scan'208";a="59369912" Received: from mail-ew0-f219.google.com ([209.85.219.219]) by mail1-smtp-roc.national.inria.fr with ESMTP; 14 May 2010 20:47:40 +0200 Received: by ewy19 with SMTP id 19so931962ewy.22 for ; Fri, 14 May 2010 11:47:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from :user-agent:mime-version:to:cc:subject:references:in-reply-to :x-enigmail-version:openpgp:content-type:content-transfer-encoding; bh=g6mCf7/D3AdMhno9SxWInKNoS33Mxw0Ij9sUh3utKp4=; b=Dg4myI8Is2C/EK/C9fFW+RRj54JqwmmZO/uFkyBr5gZ26GWg6iD7T01cJIjz0BOZnB 6l9lZ+fOQD6B+0eWg4XCPX/j28IV2UAYyrb09cRG6KBCfEGNuKIEooAPACz6w4n0DV0Q TOQDBj+JNN8XLC557S+3X1yj6RrdGitD+tmlw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:x-enigmail-version:openpgp:content-type :content-transfer-encoding; b=mHDBkF2tY2oawmHn1Eh+7YsosKsZOl3HM1NLPrp768Y068MMZeXC/DYi099qEge4fU 6hYRJOXJcggXzwmFpOFhXbKIZJ2cnDQu1I+ROT33YcTOQfclCbQXpZB2ITsVnd/vAlQK YL9HqhWTQGiz8OzJ0e/eHSsDfBpBAfw1MsdHY= Received: by 10.213.73.65 with SMTP id p1mr852238ebj.65.1273862860703; Fri, 14 May 2010 11:47:40 -0700 (PDT) Received: from [192.168.0.41] (53-mo6-3.acn.waw.pl [82.210.166.53]) by mx.google.com with ESMTPS id 15sm1408017ewy.8.2010.05.14.11.47.40 (version=TLSv1/SSLv3 cipher=RC4-MD5); Fri, 14 May 2010 11:47:40 -0700 (PDT) Message-ID: <4BED9B03.4080101@gmail.com> Date: Fri, 14 May 2010 20:48:35 +0200 From: =?UTF-8?B?IlN0YW5pc8WCYXcgVC4gRmluZGVpc2VuIg==?= User-Agent: Mozilla-Thunderbird 2.0.0.24 (X11/20100328) MIME-Version: 1.0 To: Yoriyuki Yamagata Cc: Caml List Subject: Re: [Caml-list] Balancing algorithm of Set/Map implementation References: In-Reply-To: X-Enigmail-Version: 0.95.0 OpenPGP: id=3B31FE8A; url=http://eisenbits.homelinux.net/~stf/key-stf.txt Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; yoriyuki:01 yamagata:01 node:01 node:01 ocaml:01 ord:01 ord:01 wikipedia:01 wiki:01 stf:01 stf:01 height:98 height:98 wrote:01 rec:01 On 2010-05-14 08:17, Yoriyuki Yamagata wrote: > When I read the balancing function of stdlib's Set/Map several years > ago, I thought I have understand how it works. But now, I read it again > and I'm less confident now. Could someone answer my questions? Here is > the snippet of the code. > > let bal l v r = > let hl = match l with Empty -> 0 | Node(_,_,_,h) -> h in > let hr = match r with Empty -> 0 | Node(_,_,_,h) -> h in > if hl > hr + 2 then begin > match l with > > Empty -> invalid_arg "Set.bal" > | Node(ll, lv, lr, _) -> > if height ll >= height lr then > create ll lv (create lr v r) > else begin > match lr with > > Empty -> invalid_arg "Set.bal" > | Node(lrl, lrv, lrr, _)-> > create (create ll lv lrl) lrv (create lrr v r) > end > end else if hr > hl + 2 then begin > > match r with > Empty -> invalid_arg "Set.bal" > | Node(rl, rv, rr, _) -> > if height rr >= height rl then > create (create l v rl) rv rr > else begin > > match rl with > Empty -> invalid_arg "Set.bal" > | Node(rll, rlv, rlr, _) -> > create (create l v rll) rlv (create rlr rv rr) > end > > end else > Node(l, v, r, (if hl >= hr then hl + 1 else hr + 1)) [...] > Another question is that why OCaml implementation allows > a balancing factor up to *2*, which is usually allowed only up to 1? I guess the balancing factor of -2/+2 can only occur temporarily during insert/delete operations (and such). See for instance (set.ml): let rec add x = function Empty -> Node(Empty, x, Empty, 1) | Node(l, v, r, _) as t -> let c = Ord.compare x v in if c = 0 then t else if c < 0 then bal (add x l) v r else bal l v (add x r) let rec remove x = function Empty -> Empty | Node(l, v, r, _) -> let c = Ord.compare x v in if c = 0 then merge l r else if c < 0 then bal (remove x l) v r else bal l v (remove x r) This is what bal is for: to fix the balance in the tree root. I guess this: http://en.wikipedia.org/wiki/AVL_tree#Operations is more or less correct. :-) STF http://eisenbits.homelinux.net/~stf/ OpenPGP: DFD9 0146 3794 9CF6 17EA D63F DBF5 8AA8 3B31 FE8A