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

Subject: Re: [boost] [tree] Reviving the tree library
From: Cromwell Enage (sponage_at_[hidden])
Date: 2011-05-09 13:34:13

--- 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.)

Ah, I see now.  In that case, storing the depth variable as part of the tree node would make the depth() member function most efficient...for those applications that actually need it.  This leads to the question of whether or not applications that don't need depth() can live with the memory overhead.  I suspect so, but that's just a guess.

BTW, I've started a new discussion on container_gen, archived here:
<http://article.gmane.org/gmane.comp.lib.boost.devel/219238>

Cromwell D. Enage