Virgil
Posts:
1,343
Registered:
11/12/07


Re: An Argument for the Subroot Node
Posted:
Mar 11, 2008 3:31 AM


In article <47d60e1d$1@news2.lightlink.com>, Tony Orlow <tony@lightlink.com> wrote:
> 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.
If Tony wants to attach such an appendix to his trees, fine, but no one els needs one, and Tony himself may soon need an appendectomy.

