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 mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 93827BC57 for ; Fri, 14 May 2010 08:17:25 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnsDAH+H7EvRVdQ2emdsb2JhbACDGJl+ZAgVAQEUJAMfrB0BPYIAhHouiE0BAQMFhB5tBIM+ X-IronPort-AV: E=Sophos;i="4.53,227,1272837600"; d="scan'208";a="50612671" Received: from mail-vw0-f54.google.com ([209.85.212.54]) by mail3-smtp-sop.national.inria.fr with ESMTP; 14 May 2010 08:17:24 +0200 Received: by vws1 with SMTP id 1so1987218vws.27 for ; Thu, 13 May 2010 23:17:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:date:message-id :subject:from:to:content-type; bh=pb3Zw6/DO/f7kinwkAe26rMU1XLEBbXmAdwlE0Z3+Y4=; b=MOyS9jw3KUFimR6CnngFL1RaQVNmkVLxpBGNDOsuE7/wh4ii8saVWP1XiV3vCaDW0w cueJipWzLWaDCkY0Hn6+TlUIVzj3xY84gi/ROVqA5YWKE1qYjrSuA9a/IaF/te1H3PDO mrmfrt1fzmZKNTu2oRZbVtKtdUb/HiYR4dN90= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:date:message-id:subject:from:to:content-type; b=Zzw5evMVuXqATAoi0zziQ2678EirnQkph7fHrOqa2TmFwoiit9QMGaINBBaGkecA5S rrmQSQ2EG8mSkfQosgEAJHeW9bzjkYDTsg76+12Tzq2/mJ17ay+8mgZW1+NUVHj/wTO9 2etuZVLliq+qC6hl2ZtbU/Q0oa1ed9ueMG9J8= MIME-Version: 1.0 Received: by 10.220.47.219 with SMTP id o27mr271775vcf.209.1273817843557; Thu, 13 May 2010 23:17:23 -0700 (PDT) Received: by 10.220.112.3 with HTTP; Thu, 13 May 2010 23:17:23 -0700 (PDT) Date: Fri, 14 May 2010 15:17:23 +0900 Message-ID: Subject: Balancing algorithm of Set/Map implementation From: Yoriyuki Yamagata To: Caml List Content-Type: multipart/alternative; boundary=0016e647615412e70b048687d48c X-Spam: no; 0.00; yoriyuki:01 yamagata:01 yoriyuki:01 node:01 node:01 unbalanced:01 ocaml:01 yamagata:01 unbalanced:01 ocaml:01 height:98 height:98 algorithm:01 tree:02 tree:02 X-Attachments: cset="ISO-2022-JP" --0016e647615412e70b048687d48c Content-Type: text/plain; charset=ISO-8859-1 Hi, list. 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)) I have two question. | Node(ll, lv, lr, _) -> if height ll >= height lr then create ll lv (create lr v r) else begin Is this code right? If r is Empty and lr and ll are huge trees, doesn't it create a massively unbalanced tree? Another question is that why OCaml implementation allows a balancing factor up to *2*, which is usually allowed only up to 1? Maybe my question is naive one, but I would appreciate if your could comment it. Regards, -- Yoriyuki Yamagata yoriyuki.y@gmail.com --0016e647615412e70b048687d48c Content-Type: text/html; charset=ISO-2022-JP Content-Transfer-Encoding: base64 SGksIGxpc3QuPGJyPjxicj5XaGVuIEkgcmVhZCB0aGUgYmFsYW5jaW5nIGZ1bmN0aW9uIG9mIHN0 ZGxpYiYjMzk7cyBTZXQvTWFwIHNldmVyYWwgeWVhcnMgYWdvLCBJIHRob3VnaHQgSSBoYXZlIHVu ZGVyc3RhbmQgaG93IGl0IHdvcmtzLiZuYnNwOyBCdXQgbm93LCBJIHJlYWQgaXQgYWdhaW4gYW5k IEkmIzM5O20gbGVzcyBjb25maWRlbnQgbm93LiZuYnNwOyBDb3VsZCBzb21lb25lIGFuc3dlciBt eSBxdWVzdGlvbnM/Jm5ic3A7IEhlcmUgaXMgdGhlIHNuaXBwZXQgb2YgdGhlIGNvZGUuPGJyPgo8 cHJlPiBsZXQgYmFsIGwgdiByID08YnI+ICAgICAgbGV0IGhsID0gbWF0Y2ggbCB3aXRoIEVtcHR5 IC0mZ3Q7IDAgfCBOb2RlKF8sXyxfLGgpIC0mZ3Q7IGggaW48YnI+ICAgICAgbGV0IGhyID0gbWF0 Y2ggciB3aXRoIEVtcHR5IC0mZ3Q7IDAgfCBOb2RlKF8sXyxfLGgpIC0mZ3Q7IGggaW48YnI+ICAg ICAgaWYgaGwgJmd0OyBociArIDIgdGhlbiBiZWdpbjxicj4gICAgICAgIG1hdGNoIGwgd2l0aDxi cj4KICAgICAgICAgIEVtcHR5IC0mZ3Q7IGludmFsaWRfYXJnICZxdW90O1NldC5iYWwmcXVvdDs8 YnI+ICAgICAgICB8IE5vZGUobGwsIGx2LCBsciwgXykgLSZndDs8YnI+ICAgICAgICAgICAgaWYg aGVpZ2h0IGxsICZndDs9IGhlaWdodCBsciB0aGVuPGJyPiAgICAgICAgICAgICAgY3JlYXRlIGxs IGx2IChjcmVhdGUgbHIgdiByKTxicj4gICAgICAgICAgICBlbHNlIGJlZ2luPGJyPiAgICAgICAg ICAgICAgbWF0Y2ggbHIgd2l0aDxicj4KICAgICAgICAgICAgICAgIEVtcHR5IC0mZ3Q7IGludmFs aWRfYXJnICZxdW90O1NldC5iYWwmcXVvdDs8YnI+ICAgICAgICAgICAgICB8IE5vZGUobHJsLCBs cnYsIGxyciwgXyktJmd0Ozxicj4gICAgICAgICAgICAgICAgICBjcmVhdGUgKGNyZWF0ZSBsbCBs diBscmwpIGxydiAoY3JlYXRlIGxyciB2IHIpPGJyPiAgICAgICAgICAgIGVuZDxicj4gICAgICBl bmQgZWxzZSBpZiBociAmZ3Q7IGhsICsgMiB0aGVuIGJlZ2luPGJyPgogICAgICAgIG1hdGNoIHIg d2l0aDxicj4gICAgICAgICAgRW1wdHkgLSZndDsgaW52YWxpZF9hcmcgJnF1b3Q7U2V0LmJhbCZx dW90Ozxicj4gICAgICAgIHwgTm9kZShybCwgcnYsIHJyLCBfKSAtJmd0Ozxicj4gICAgICAgICAg ICBpZiBoZWlnaHQgcnIgJmd0Oz0gaGVpZ2h0IHJsIHRoZW48YnI+ICAgICAgICAgICAgICBjcmVh dGUgKGNyZWF0ZSBsIHYgcmwpIHJ2IHJyPGJyPiAgICAgICAgICAgIGVsc2UgYmVnaW48YnI+CiAg ICAgICAgICAgICAgbWF0Y2ggcmwgd2l0aDxicj4gICAgICAgICAgICAgICAgRW1wdHkgLSZndDsg aW52YWxpZF9hcmcgJnF1b3Q7U2V0LmJhbCZxdW90Ozxicj4gICAgICAgICAgICAgIHwgTm9kZShy bGwsIHJsdiwgcmxyLCBfKSAtJmd0Ozxicj4gICAgICAgICAgICAgICAgICBjcmVhdGUgKGNyZWF0 ZSBsIHYgcmxsKSBybHYgKGNyZWF0ZSBybHIgcnYgcnIpPGJyPiAgICAgICAgICAgIGVuZDxicj4K ICAgICAgZW5kIGVsc2U8YnI+ICAgICAgICBOb2RlKGwsIHYsIHIsIChpZiBobCAmZ3Q7PSBociB0 aGVuIGhsICsgMSBlbHNlIGhyICsgMSkpPGJyPjxicj5JIGhhdmUgdHdvIHF1ZXN0aW9uLjxicj48 L3ByZT48cHJlPiAgICAgICAgfCBOb2RlKGxsLCBsdiwgbHIsIF8pIC0mZ3Q7PGJyPiAgICAgICAg ICAgIGlmIGhlaWdodCBsbCAmZ3Q7PSBoZWlnaHQgbHIgdGhlbjxicj4gICAgICAgICAgICAgIGNy ZWF0ZSBsbCBsdiAoY3JlYXRlIGxyIHYgcik8YnI+CiAgICAgICAgICAgIGVsc2UgYmVnaW48YnI+ PGJyPklzIHRoaXMgY29kZSByaWdodD8gIElmIHIgaXMgRW1wdHkgYW5kIGxyIGFuZCBsbCBhcmUg aHVnZSB0cmVlcywgPGJyPmRvZXNuJiMzOTt0IGl0IGNyZWF0ZSBhIG1hc3NpdmVseSB1bmJhbGFu Y2VkIHRyZWU/IDxicj48YnI+QW5vdGhlciBxdWVzdGlvbiBpcyB0aGF0IHdoeSBPQ2FtbCBpbXBs ZW1lbnRhdGlvbiBhbGxvd3MgPGJyPmEgYmFsYW5jaW5nIGZhY3RvciB1cCB0byAqMiosIHdoaWNo IGlzIHVzdWFsbHkgYWxsb3dlZCBvbmx5IHVwIHRvIDE/PGJyPgo8YnI+TWF5YmUgbXkgcXVlc3Rp b24gaXMgbmFpdmUgb25lLCBidXQgSSB3b3VsZCBhcHByZWNpYXRlIGlmIHlvdXIgY291bGQgY29t bWVudCBpdC48YnI+PGJyPlJlZ2FyZHMsPGJyPjwvcHJlPgotLSA8YnI+WW9yaXl1a2kbJEIhIRso QllhbWFnYXRhPGJyPjxhIGhyZWY9Im1haWx0bzp5b3JpeXVraS55QGdtYWlsLmNvbSI+eW9yaXl1 a2kueUBnbWFpbC5jb208L2E+PGJyPgo= --0016e647615412e70b048687d48c--