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"