Suggestions on how to calculate something

This is a discussion on Suggestions on how to calculate something within the C++ Programming forums, part of the General Programming Boards category; I am trying to calculate the height of nodes in a tree. I think that if I take the closest ...

  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
    21,744
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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,304
    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 06: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, 01: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21