Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: An Argument for the Subroot Node
Replies: 28   Last Post: Mar 14, 2008 8:32 PM

 Messages: [ Previous | Next ]
 Tony Orlow Posts: 3,142 Registered: 8/23/06
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((x-1)/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 2x-n+1 and
2x-n+2, and the parent of x is floor((x-1+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

Date Subject Author
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 G. Frege
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 G. Frege
3/11/08 J. Antonio Perez M.
3/11/08 G. Frege
3/11/08 G. Frege
3/11/08 Tony Orlow
3/11/08 briggs@encompasserve.org
3/14/08 Tony Orlow
3/14/08 David R Tribble
3/14/08 LudovicoVan
3/11/08 Tony Orlow
3/11/08 J. Antonio Perez M.
3/11/08 Tony Orlow
3/11/08 Tony Orlow
3/11/08 Tony Orlow
3/11/08 LudovicoVan
3/11/08 LudovicoVan
3/14/08 Tony Orlow
3/14/08 LudovicoVan
3/14/08 LudovicoVan
3/11/08 David R Tribble
3/11/08 LudovicoVan
3/11/08 LudovicoVan