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.