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"
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk