[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: intervals.c: About interval tree

From: Stefan Monnier
Subject: Re: intervals.c: About interval tree
Date: Mon, 15 Apr 2013 10:02:15 -0400
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3.50 (gnu/linux)

> It seems the tree that is used is "mostly balanced tree".  I am
> wondering what sort of "balancedness" we are talking about i.e.. what
> invariant does the tree satisfy?

If you look at balance_an_interval, I think it's just "balanced" in the
sense that the left and right subtrees cover (as much as possible) the
same text-size.

So it's different from the usual literature, where "balanced" refers to
the depth of the tree.

        Stefan "who replaced it with a splay-tree at some point"

reply via email to

[Prev in Thread] Current Thread [Next in Thread]