• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Binary Tree Forumula

 
Ranch Hand
Posts: 40
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 ?
 
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for the insight guys
 
Ranch Hand
Posts: 1071
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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)...
 
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Surfs up space ponies, I'm making gravy without this lumpy, tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic