aspose file tools*
The moose likes Performance and the fly likes Binary Tree Forumula Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Performance
Bookmark "Binary Tree Forumula" Watch "Binary Tree Forumula" New topic
Author

Binary Tree Forumula

Cecil Phillip
Ranch Hand

Joined: Nov 05, 2001
Posts: 40
I was wondering that if the size(number of elements) in a complete binary tree were known, and numbered in a level order fashion, could their position be determined ? For instance you have the tree

1
2| |3
4| |5 6| |7

So now, is there a way that I could calculate that 7 is on the right side and that 4 is at the bottom left ?
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
With those specific values, yes. With values other than 1..n, you wouldn't know that 12 is the 5th element, so you'd still need to search the tree.
Ilja Preuss
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
Originally posted by Cecil Phillip:
I was wondering that if the size(number of elements) in a complete binary tree were known, and numbered in a level order fashion, could their position be determined ? For instance you have the tree



So now, is there a way that I could calculate that 7 is on the right side and that 4 is at the bottom left ?


Yes. For example, notice that every even number is on the left of its parent, the odd numbers are on the right side. Also notice that with every "layer" of nodes, the number of nodes doubles. That should give you some starting thoughts...


The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus
Cecil Phillip
Ranch Hand

Joined: Nov 05, 2001
Posts: 40
Thanks for the insight guys
Steven Bell
Ranch Hand

Joined: Dec 29, 2004
Posts: 1071
Also note that the number of levels corresponds to the log base 2 of the number of elements.

log2(1) = 0
log2(2) = 1
log2(4) = 2
log2(8) = 3
log2(16) = 4
...

If you have 1 element you have started the 0th row. If you have 8 elements you have started the 3rd row.
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
Originally posted by Cecil Phillip:
... and numbered in a level order fashion ...
Sorry, I took this to mean that you simply numbered each level. Please ignore my previous reply, though I'll leave it intact for comedic value.
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Inferring the number of levels from the number of entries works only if it's balanced. If you add keys in sequence to a simple tree then you only use the right hand pointers and it turns out to be exactly like a linked list ... levels == entry count. Self balancing trees are pretty tricky. A good CS assignment for sure.


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Ilja Preuss
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
Originally posted by Stan James:
Inferring the number of levels from the number of entries works only if it's balanced.


I assumed that that was what Cecil meant by "complete"...
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Is "complete" a synonym for "balanced" among people smarter about trees than me?

Borland sold a database and word processing package for Turbo Pascal 2.0. It came with source code and a great little book full of algorithms and sample code. The main thing I learned about self balancing trees is that they are tricky enough I'd buy one before writing one.
Ilja Preuss
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
Originally posted by Stan James:
Is "complete" a synonym for "balanced" among people smarter about trees than me?


More likely between people less smart than you. I didn't remember the term "balanced" before you mentioned it - my understanding of "complete" was more intuitive (= a guess)...
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
The terms "complete binary tree," "perfect binary tree," and "full binary tree" all have different meanings. Actually a complete tree is a kind of full tree and a perfect tree is a kind of complete tree. In a full tree, every node has either 0 or 2 children, never 1. In a complete tree, all leaf nodes are at either depth D or depth D+1, and the leaves at depth D+1 are all together on the left. In a perfect binary tree, all leafs are at the same depth.

Complete and perfect trees are a kind of balanced tree, but not all balanced trees are complete. In a balanced tree you have some sort of balance rule. Typically the rule is that no leaf is at a depth greater than C*log(number of elements in the tree) where C is some constant.
Steven Bell
Ranch Hand

Joined: Dec 29, 2004
Posts: 1071
It might help to know the reason behind knowing where 7 is in the tree without traversing it. It would seem to me with such requirments a List would be a better fit.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Binary Tree Forumula