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
Re: An Argument for the Subroot Node
Posted: Mar 11, 2008 10:14 AM

Virgil wrote:
> 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((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.

>
> 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.

So, you have no objection? That's nice. Does it appeal to you that every
node now has a parent and a leading edge, or that the number of nodes
up to each level n is now exactly equal to 2^n? Those seem like nice
simplifications to me. No "except for the root" or "-1" about it.

:)

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