From: Brian Hurt <bhurt@spnz.org>
To: David Monniaux <David.Monniaux@ens.fr>
Cc: caml-list <caml-list@yquem.inria.fr>
Subject: Re: [Caml-list] tree balancing in Set and Map
Date: Sat, 21 Oct 2006 20:15:12 -0400 (EDT) [thread overview]
Message-ID: <Pine.LNX.4.64.0610212012160.21800@localhost> (raw)
In-Reply-To: <453AB54C.50201@ens.fr>
On Sun, 22 Oct 2006, David Monniaux wrote:
> I wonder about something: the first balanced tree data structure described in
> algorithmics courses is generally the AVL tree, where the heights of the
> subtrees differ by at most 1. In Caml's implementation, they are allowed to
> differ by at most 2.
Heh. I asked this question myself a couple of months back. The response
was basically that yes, it was a delibert decision- by allowing heights to
differ by more, this limits the amount of rebalancing that is needed,
making inserts faster. Testing the two different approachs showed that
the increase in speed for inserts was enough to justify the slight slowing
of finds.
A comment to this effect in the code might not be a bad idea...
Brian
prev parent reply other threads:[~2006-10-22 0:13 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2006-10-22 0:03 David Monniaux
2006-10-22 0:15 ` Brian Hurt [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Pine.LNX.4.64.0610212012160.21800@localhost \
--to=bhurt@spnz.org \
--cc=David.Monniaux@ens.fr \
--cc=caml-list@yquem.inria.fr \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).