Thread: Building Binary Trees

  1. #1
    Master n00b Matty_Alan's Avatar
    Join Date
    Jun 2007
    Location
    Bloody Australia Mate!
    Posts
    96

    Building Binary Trees

    Hiya,
    Im trying to construct a binary tree and im not quite sure how to do it so that it's well ballanced. I have a fair idea on how a binary tree works, just putting it together is troubling me, i tryed a google and it spat quite alot of math at me that i didn't quite undersand so I was hoping that if someone explained it as far as code goes i'd get it.

    Basicly say you have the data between 1 and 20 and it's all in sequence, what order would you place the data, i figgurd the root node should be 10 and that would probably branch into 5 and 15 but from there im a little stuck

  2. #2
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Matty_Alan View Post
    Basicly say you have the data between 1 and 20 and it's all in sequence, what order would you place the data, i figgurd the root node should be 10 and that would probably branch into 5 and 15 but from there im a little stuck
    Why do you get stuck there? Just keep doing what you're doing. In other words, split the range in half. Split the halves in half. Split those in half. Until you get to single elements.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  3. #3
    Registered User
    Join Date
    Jun 2008
    Posts
    62
    Quote Originally Posted by Matty_Alan View Post
    Hiya,
    Im trying to construct a binary tree and im not quite sure how to do it so that it's well ballanced. I have a fair idea on how a binary tree works, just putting it together is troubling me, i tryed a google and it spat quite alot of math at me that i didn't quite undersand so I was hoping that if someone explained it as far as code goes i'd get it.

    Basicly say you have the data between 1 and 20 and it's all in sequence, what order would you place the data, i figgurd the root node should be 10 and that would probably branch into 5 and 15 but from there im a little stuck
    AVL tree - Wikipedia, the free encyclopedia
    Red-black tree - Wikipedia, the free encyclopedia

    Start with the AVL tree, as it is probably the simplest form of tree balancing. Go to the Red-black tree, as it provides pretty good performance, and is a specific form of the very common B-tree.

    The basic idea to understanding an AVL tree (which stays perfectly balanced) is that each node has a weight. Insertion goes the same as a binary tree, except you keep track of the weight. If the weight is 2 or -2, you rotate the node left or right to rebalance the tree. Balancing is done during insertion (You don't want to do all the insertions then balance, rather you want to balance as you insert)

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by brewbuck View Post
    Why do you get stuck there? Just keep doing what you're doing. In other words, split the range in half. Split the halves in half. Split those in half. Until you get to single elements.
    Oh and in case you hadn't gealmed it from the above, you'll want to use a recursive function for this.
    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"

  5. #5
    Master n00b Matty_Alan's Avatar
    Join Date
    Jun 2007
    Location
    Bloody Australia Mate!
    Posts
    96
    Why do you get stuck there? Just keep doing what you're doing. In other words, split the range in half. Split the halves in half. Split those in half. Until you get to single elements.

    I didn't think it was going to work because i was dividing and I thought that the .5's would mess something up but i went over it again and it works rounded


    Quote Originally Posted by iMalc View Post
    Oh and in case you hadn't gealmed it from the above, you'll want to use a recursive function for this.
    Thats a good idea I didn't think of that, cheers

  6. #6
    Registered User
    Join Date
    Jun 2008
    Posts
    62
    Quote Originally Posted by iMalc View Post
    Oh and in case you hadn't gealmed it from the above, you'll want to use a recursive function for this.
    Not for this, you can do binary searching without using recursion, and just as clean as recursion. The overhead of recursion is pretty bad.

    Recursion should be reserved for splitting data, IE, doing a postfix traversal of a tree.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Cogman View Post
    Not for this, you can do binary searching without using recursion, and just as clean as recursion. The overhead of recursion is pretty bad.

    Recursion should be reserved for splitting data, IE, doing a postfix traversal of a tree.
    Your wasting your breath if you're trying to explain binary search to me. You may as well be telling a fish how to swim. You can read the article I wrote about binary search on my website if you want to see barely half of what I know about it.

    If my instinct is correct, the original poster is asking how to construct a pre-balanced binary tree, not implement a self-balancing binary tree. In which case, your initial reply was not what he was looking for. Perhaps if you had pointed him at the Scapegoat self-banalcing tree technique (in which pre-balanced binary trees are used), then your post might have been more relevant. However I suppose the poster might be happy with either.

    Do you understand the nature of the problem of constructing a pre-balanced binary tree. The problem itself is naturally doubly-recursive by nature. One of the recursive calls can be turned into a loop, but both cannot. To do it without recursion would require you to maintain an explicit stack, and that is where I draw the line at reducing a recursive functions into an iterative one. So yes you definitely want to use recursion for the technique brewbuck and I were describing!

    Finally I shall contradict myself and state that yes there is a completely different way to do it purely iteratively that I'm not going to go into details of, because it is very unelegant and ultimately not worth considering.

    Matty_Alan: The rounding doesn't matter. Whenever there is an even number of items at the split, the resulting tree will be equally balanced whichever of the middle two items you pick as the splitter. E.g. for four items
    Code:
        3        2
       / \      / \
      2   4    1   3
     /              \
    1                4
    Last edited by iMalc; 04-23-2010 at 02:56 AM.
    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"

  8. #8
    Registered User
    Join Date
    Jun 2008
    Posts
    62
    Quote Originally Posted by iMalc View Post
    Your wasting your breath if you're trying to explain binary search to me. You may as well be telling a fish how to swim. You can read the article I wrote about binary search on my website if you want to see barely half of what I know about it.

    If my instinct is correct, the original poster is asking how to construct a pre-balanced binary tree, not implement a self-balancing binary tree. In which case, your initial reply was not what he was looking for. Perhaps if you had pointed him at the Scapegoat self-banalcing tree technique (in which pre-balanced binary trees are used), then your post might have been more relevant. However I suppose the poster might be happy with either.

    Do you understand the nature of the problem of constructing a pre-balanced binary tree. The problem itself is naturally doubly-recursive by nature. One of the recursive calls can be turned into a loop, but both cannot. To do it without recursion would require you to maintain an explicit stack, and that is where I draw the line at reducing a recursive functions into an iterative one. So yes you definitely want to use recursion for the technique brewbuck and I were describing!

    Finally I shall contradict myself and state that yes there is a completely different way to do it purely iteratively that I'm not going to go into details of, because it is very unelegant and ultimately not worth considering.

    Matty_Alan: The rounding doesn't matter. Whenever there is an even number of items at the split, the resulting tree will be equally balanced whichever of the middle two items you pick as the splitter. E.g. for four items
    Code:
        3        2
       / \      / \
      2   4    1   3
     /              \
    1                4
    Dang it, I just had a long post saying you were right, and somehow my cookies got cleared .

    Anyways, the gist of it was "You were right, I didn't understand what was being said, and I prefer a self-balancing tree over doing a pre-balancing build for the ability to insert/delete nodes on the fly"

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I too have noticed that if I take a long time to post then it fails and I have to log in again to post. Many curses later, I've learned to always copy the entire post before clicking the button to submit it.

    I can certainly understand the ease at which one could assume the poster is after self-balancing binary trees, and indeed even if that wasn't what was being asked about, they still might be happy with them as a solution anyway. I probably should have reviewed my post before posting, as looking back at it now, I went a tad overboard to say the least.
    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"

  10. #10
    Registered User
    Join Date
    Jun 2008
    Posts
    62
    Quote Originally Posted by iMalc View Post
    I too have noticed that if I take a long time to post then it fails and I have to log in again to post. Many curses later, I've learned to always copy the entire post before clicking the button to submit it.

    I can certainly understand the ease at which one could assume the poster is after self-balancing binary trees, and indeed even if that wasn't what was being asked about, they still might be happy with them as a solution anyway. I probably should have reviewed my post before posting, as looking back at it now, I went a tad overboard to say the least.
    NP. One thing that I did confuse when I was posting was the fact that somehow my brain triggered binary searching from your post. So, when I was saying it could be done simply, and iteratively, I was thinking of a binary search (for whatever reason). Obviously very different from traversing a binary tree

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting From Binary Tree to Threaded Binary Trees
    By elton_fan in forum C Programming
    Replies: 15
    Last Post: 11-08-2007, 11:41 PM
  2. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM