Thread: Suggestions on how to calculate something

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    55

    Suggestions on how to calculate something

    I am trying to calculate the height of nodes in a tree. I think that if I take the closest power of 2 that is larger than the number of nodes in a tree and subtract one from it, that would be the height of the node. For example,
    if a tree has 15 nodes, the closest power of 2 higher than 15 is 4, so the height of that node with respect to the node is 3. So it seems that it works, but I am having trouble coding it. Can anyone provide tips or suggestions to get me on track? Thanks.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    What kind of tree are you talking about? For example, a binary search tree could degenerate into a linked list type of structure, and a multiway tree could have 15 child nodes for the root, so the height would just be 1.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    That would certainly work for a heap, but won't be 100% accurate for a binary tree. Even an AVL tree with 15 nodes can be a tiny bit unbalanced.

    I guess the question is, do you want it to be accurate, or just fast?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    55
    It is for an AVL Tree and my class already has methods for rebalancing the tree. However, I am trying to store the height information within the node struct of each node, so that I can later get the internal path length of the tree.
    Last edited by Bnchs; 11-09-2007 at 07:09 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Free Book Suggestions!
    By valaris in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 10-08-2008, 10:25 AM
  2. how to calculate all files in disk?
    By kirmelyte in forum C Programming
    Replies: 1
    Last Post: 04-30-2006, 02:47 PM
  3. Small program that has to calculate miles per gallon
    By Guti14 in forum C++ Programming
    Replies: 6
    Last Post: 01-06-2004, 02:47 PM
  4. Math Book Suggestions
    By curlious in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 10-09-2003, 10:43 AM