Re: [boost] [tree] Reviving the tree library

Subject: Re: [boost] [tree] Reviving the tree library
From: Erik Erlandson (eerlands_at_[hidden])
Date: 2011-05-09 10:56:28

On Mon, 2011-05-09 at 07:25 -0700, Cromwell Enage wrote:

> --- On Fri, 5/6/11, Erik Erlandson wrote:
> > ply() could easily be a free function, and would have
> > O(depth) complexity.   The problem I saw with depth()
> > as a stateless function is that its complexity would be
> > linear on the size of the (sub)tree, unless I'm missing
> > something.   (I mitigated that problem by maintaining
> > some depth-histogram structures that can be updated in
> > O(depth) time for various operations)
> 
> Interesting.  BTW, what's the difference between depth and ply?  I thought they were interchangeable (and other users might think so, too).

I should make sure to document those definitions thoroughly.    Ply is
the "layer," or distance from root.    So the ply(root) = 0.    The ply
of root's children is 1,   The ply of root's grandchildren is 2, etc.
Depth of a (sub)tree is "1 + the maximum ply"