The Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
Read An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Virgil
3/11/08
Read Re: An Argument for the Subroot Node
G. Frege
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Virgil
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Virgil
3/11/08
Read Re: An Argument for the Subroot Node
G. Frege
3/11/08
Read Re: An Argument for the Subroot Node
J. Antonio Perez M.
3/11/08
Read Re: An Argument for the Subroot Node
G. Frege
3/11/08
Read Re: An Argument for the Subroot Node
G. Frege
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
briggs@encompasserve.org
3/14/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/14/08
Read Re: An Argument for the Subroot Node
David R Tribble
3/14/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
J. Antonio Perez M.
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/11/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/14/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/14/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/14/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/11/08
Read Re: An Argument for the Subroot Node
David R Tribble
3/11/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/11/08
Read Re: An Argument for the Subroot Node
LudovicoVan

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.