Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Binary Tree Forumula

 
Cecil Phillip
Ranch Hand
Posts: 40
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1646
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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...
 
Cecil Phillip
Ranch Hand
Posts: 40
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the insight guys
 
Steven Bell
Ranch Hand
Posts: 1071
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1646
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1071
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic