Building Binary Trees

• 04-22-2010
Matty_Alan
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
• 04-22-2010
brewbuck
Quote:

Originally Posted by Matty_Alan
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.
• 04-22-2010
Cogman
Quote:

Originally Posted by Matty_Alan
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)
• 04-22-2010
iMalc
Quote:

Originally Posted by brewbuck
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.
• 04-22-2010
Matty_Alan
Quote:

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
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
• 04-22-2010
Cogman
Quote:

Originally Posted by iMalc
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.
• 04-23-2010
iMalc
Quote:

Originally Posted by Cogman
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```
• 04-24-2010
Cogman
Quote:

Originally Posted by iMalc
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"
• 04-24-2010
iMalc
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.
• 04-24-2010
Cogman
Quote:

Originally Posted by iMalc
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 :)