
An Argument for the Subroot Node
Posted:
Mar 11, 2008 12:44 AM


Hi All
I have alluded to the subroot node in the binary tree, and been coy about it, but it appears to need some explication, so please allow me to lay it out in the simplest possible terms.
Say we have a tree, consisting of a set of nodes, most of which have a single associated edge (excepting one, the root, in most schemes), such that we have a countable set of nodes, and thus, edges. If we associate each of those nodes in the countable set with an element of N as normally conceived, then we may start with either 0 or 1, and can number the nodes at each level starting with the next after the last of the previous level. That's pretty normal.
If we make the root 0, and its children are 1 and 2, and 1's children are 3 and 4, and 2's are 5 and 6, and so forth, x's children are equal to 2x+1 and 2x+2. On the other hand, if we start with root node 1, and child nodes 2 and 3, etc., then node x has children 2x and 2x+1. Then node 2 has children 4 and 5, and 3 has 6 and 7. In the first case the parent of x is floor((x1)/2), and in the second, floor(x/2). If we inquire as to the parent of the root, we get node 1 in the first case and node 0 in the second. That rather makes sense. If we look at the children of this subroot node, they include the root, as well as the subroot itself. That's an interesting...twist, or loop, as one might call it.
In general, if we number the root node with n in N, and count up in the same way, starting the left side of each row with the next after the right side of the last row, then the children of node x are 2xn+1 and 2xn+2, and the parent of x is floor((x1+n)/2), which is always its own parent.
So, in conclusion, the "complete" binary tree includes not only a root node, but a subroot node, which is its own parent, akin to the missing fifth of a point on the top of the pyramid.
Peace,
:)
Tony

