This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.
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
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
Joined: Jul 11, 2001
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"...
Joined: Jan 29, 2003
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.
Joined: Jul 11, 2001
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)...
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.
Joined: Dec 29, 2004
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.