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 12:59:32

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

> > 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"
> 
> So ply is defined in terms of ancestors, while depth is defined in terms of descendants, right?

Exactly.

> 
> To illustrate then, given the following tree:
> 
> ____A
> __+-+-+
> __B___C
> +-+-+
> D___E
> __+-+-+
> __F___G
> 
> ply(B) == 1, while depth(B) == 3

Correct.

The data structures I used to maintain depth information make any call
to depth() constant-time.   Updating them is O(tree-depth).   The
storage cost is bounded above by (n)log(n) on tree size.   

I can see how a tree designer might or might not be OK with adding an
(n)log(n) storage cost just to make depth() fast.  Which is an argument
for not requiring it in any interface spec, or not requiring it to be
faster than linear-time.