From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Nala Ginrut Newsgroups: gmane.lisp.guile.user Subject: Re: Self balancing trees Date: Wed, 23 Aug 2017 12:00:11 +0800 Message-ID: References: <1503370332.914.5.camel@qlfiles.net> <87pobow7ed.fsf@elektro.pacujo.net> <1503378459.914.12.camel@qlfiles.net> <87fuckw5bd.fsf@elektro.pacujo.net> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Trace: blaine.gmane.org 1503460861 32710 195.159.176.226 (23 Aug 2017 04:01:01 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 23 Aug 2017 04:01:01 +0000 (UTC) Cc: Guile User To: =?UTF-8?Q?Kovacsics_R=C3=B3bert?= Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Wed Aug 23 06:00:55 2017 Return-path: Envelope-to: guile-user@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dkMqP-0007YM-3h for guile-user@m.gmane.org; Wed, 23 Aug 2017 06:00:41 +0200 Original-Received: from localhost ([::1]:60895 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dkMqU-0007qX-Dp for guile-user@m.gmane.org; Wed, 23 Aug 2017 00:00:46 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:54356) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dkMq1-0007pm-Ed for guile-user@gnu.org; Wed, 23 Aug 2017 00:00:18 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dkMq0-0002Bm-Gu for guile-user@gnu.org; Wed, 23 Aug 2017 00:00:17 -0400 Original-Received: from mail-yw0-x22b.google.com ([2607:f8b0:4002:c05::22b]:33363) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1dkMq0-0002BS-Ba for guile-user@gnu.org; Wed, 23 Aug 2017 00:00:16 -0400 Original-Received: by mail-yw0-x22b.google.com with SMTP id h127so3272048ywf.0 for ; Tue, 22 Aug 2017 21:00:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=afALp6FTpzXFUIUTToeyWHLbWwCLyPSJ9SVrxjjeWtQ=; b=kukPPiqeybolOI0vwH8A6y6fblqOkznUcd2ZcdQgccKSAuZItqKh6Yp+kiBqT6cEoV gYcL6NQiWMVSGw2P+FnIcXFbMo8V/u+LJw5SwlkgjGriIyeNKFRqQ1kEGExNNfI1m86d TozRS30T1OdzeSaD48htGiaCvNmPPhVuPnRDCNdrTyK1qnfoDnoPXmuVUcU/vinh+Wlb D1RgGjqlFgm40r0f/Q5aVwg44at1xASZw65LXgAd26Nx0qQibF88Nc7Fw+1p2Eah0Ul/ iJ9tYP+a6X8MEB1qP4z9V4fkTxSVxnvcW/DLNgtLPJLHLuqWdC0zATsvI5tFthSn9TGh ZjeA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=afALp6FTpzXFUIUTToeyWHLbWwCLyPSJ9SVrxjjeWtQ=; b=U5LroTJuc0ppJYfVpDCfuOUSVi5S3YAZMjWEtzbOn5iwF3t+Z7DA4H4CtmKyRZBkY2 hRBDjTVQ0ibrblrgeRPf6vsA073ZXtlkp8sUPLHgTnGjPD3qgBsqNaxm+ofMd8aqU3HQ DbG+4ZtttqU5RDioPOKGmP+puMkiwHDErzbKWX8j/luUvIrqzOnEA2fBD110YddFkcG3 pQhPZ2CG1vE+AiuxG5aWxYW43txMRxIA+s0KlFKaeMjjLKiY5+Lg52jmOByE063zIZS0 c7wrQoygzReBVGXnbD4CuRqAldJxUUhwxFTCXDDR6m2/r02tE4Ttdv6dl3SErR3gNpK2 mmfA== X-Gm-Message-State: AHYfb5jFbTvBryT2Zhmc1pCqgaU18GrmI/fXU+C77hyX6ZxHmx+VKtjL rxBxubktHy3hjCmgoGRDm32qtZTglA== X-Received: by 10.129.120.5 with SMTP id t5mr1006729ywc.425.1503460812123; Tue, 22 Aug 2017 21:00:12 -0700 (PDT) Original-Received: by 10.37.218.213 with HTTP; Tue, 22 Aug 2017 21:00:11 -0700 (PDT) Original-Received: by 10.37.218.213 with HTTP; Tue, 22 Aug 2017 21:00:11 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4002:c05::22b X-Content-Filtered-By: Mailman/MimeDel 2.1.21 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Original-Sender: "guile-user" Xref: news.gmane.org gmane.lisp.guile.user:14047 Archived-At: Here's mine, but I haven't updated for a while, RB tree works, please don't use it seriously, and hope it inspire you. https://github.com/NalaGinrut/nashkel/blob/master/nashkel/rbtree.scm 2017=E5=B9=B48=E6=9C=8822=E6=97=A5 =E4=B8=8B=E5=8D=885:34=EF=BC=8C"Kovacsic= s R=C3=B3bert" =E5=86=99=E9=81=93=EF=BC=9A > Sorry Marko, I didn't hit reply all, so re-sending for the benefit of the > list. > > I'd just like to point out > https://wiki.rice.edu/confluence/download/attachments/2761212/Okasaki- > Red-Black.pdf > for the simplicity of it's Red-Black tree implementation. Granted, it > uses Haskell, but you could implement it similarly simply as Guile has > pattern-matching too with (ice-9 match). Also, it hasn't got a delete > operation, that would be more messy. > >