I am having a difficulty to convert my knowledge that is about balancing a tree on paper into C codes. I need to write a function to balance a tree than find the height of it. Any help is appreciated.
Printable View
I am having a difficulty to convert my knowledge that is about balancing a tree on paper into C codes. I need to write a function to balance a tree than find the height of it. Any help is appreciated.
Thanks for the reply, I know how it works on paper, just having a difficulty to code.
If you can step yourself through the process of balancing the tree, you should be able to code it. What exactly are you looking for? What part of coding it are you having trouble with?
Well, what do you expect from us exactly? Your post can be summarized to "I understand the concept of AVL trees but I can't implement it, help!".
You don't specify what part you're having problems with, the general structure, adding/searching/deleting items ... or whatever your problem is. Maybe you're expecting a link, maybe a tutorial covering all the theory about AVL trees, maybe finished C code that you can simply copy&paste?
So, what exactly do you want?
Sorry I wasn't clear enough. I just need some idea about the coding stage to balancing a tree than finding the height of it.
For example the input is 3,4,5,6,7,8,9
-----6
---/---\
--4----8
-/-\---/-\
3--5-7--9
the balanced tree should be like this, right? I was wondering do I need to use a loop to compare each item one by one or a different method? I don't know, I just couldn't make start for it, if I can make a start, it will be much easier for me.
Recursion is probably the easiest way to handle it instead of doing it iteratively with loops.
I still couldn't figure out how to write a function that builds a balanced tree from a sorted array.
Code:int height(node_ptr tree)
{
int top = 0;
int left = 0;
int right = 0;
if(tree == NULL)
{
return 0;
}
else
{
height(tree->left);
tree->left = tree->data_item;
left= tree->left;
printf("left:%d\n", left);
height(tree->data_item);
top = tree->data_item;
printf("top:%d\n", top);
height(tree->right);
tree->right = tree->data_item;
right = tree->right;
printf("right:%d\n", right);
}
return d;
}
Am I on the right track? What should I do?Thanks
Why are you speaking of balancing a tree and at the same post a function called "height()" that is far from working correctly.
You said earlier that you knew how to construct a balanced tree, well...you don't. If you knew, you probably would know that you insert items and perform rotations afterwards to keep the tree balanced and that the critical point is the insertion/deletion/rotations.
I suggest you take a good bottle of red wine, you print out this tutorial about AVL trees and make yourself a nice evening. Then either copy the code in the tutorial or try a better approach to constructing a balanced tree.
Thanks for the quick reply.Shouldn't I need to balance the tree to get the height right?
http://cboard.cprogramming.com/showthread.php?t=88462
http://cis.stvincent.edu/html/tutori.../avltrees.htmlQuote:
The height of a binary tree is the maximum path length from the root to a leaf. A single-node binary tree has height 0, and an empty binary tree has height -1.
If you're just trying to find the height, then something like the above should work. I'm not sure what you're actually trying to do, though.Code:int height(node_ptr tree)
{
if(tree == NULL)
{
return -1;
}
return max(height(tree->left),height(tree->right)) + 1;
}
The tree is balanced during creation, not during the height calculation. The height calculation is the same for every tree type, using the function from MacGyver above.Quote:
Originally Posted by BoneXXX
What you need to do is verify during item insertion/deletion if the tree gets unbalanced and react accordingly, thus, when you calculate the height, the tree is already balanced.
In my program I get random inputs from a user
Just one thing left that is I need to write a function to find the height of the tree.Code:You can now put some integers into a BST
Enter a series of positive integers terminated by zero
For example: 8 6 4 3 5 7 0
5
9
1
0
The BST now contains:
1 5 9
The number of items in the tree is: 3
The height of the tree is: ?
The BST in pre-order:5 1 9
The BST in post-order:1 9 5
You can now delete some integers from the BST
Enter a series of positive integers terminated by zero
For example: 8 6 4 3 5 7 0
5
0
The BST now contains:1 9
if the user enter these values in to the program
3,7,5,4,2,1,6
The height should be 2.
This discussion leads to (void *)null. Either your balancing your tree while you add the number to it or you don't. The height function is the same for every type of tree, regardless if it's balanced or not. If the tree isn't balanced and you enter "1 2 3 4 5" the height is 4, if the tree is auto-balanced during creation, the height is 2.
And btw, the input "3,7,5,4,2,1,6" results in a height of 3. Even if you don't take into account the root node, then there's still 6 elements left to enter into the tree which need ceil(log(2) 6) to account for. (log(2) 6 = log of 6, base 2)
This is my insert function:
3,7,5,4,2,1,6Code:node_ptr insert(int n, node_ptr tree)
{
if(tree == NULL)
{
tree = (node_ptr) malloc(sizeof(struct node));
tree->data_item = n;
tree->left = tree->right = NULL;
/*
tree->left = NULL;
tree->right= NULL;
*/
}
else if(n < tree->data_item)
{
tree->left = insert(n, tree->left);
}
else if(n > tree->data_item)
{
tree->right = insert(n, tree->right);
}
return tree;
}
-----4 -----> 0
---/---\
--2----6 ------->1
-/-\---/-\
1--3-5--7 -------->2
I was thinking the tree like this, is this wrong?
Yeah, that's wrong. ;) Your code doesn't do an avl tree, it just does a regular bst without any balancing logic, so where a node goes, it stays. The tree looks like this with that sequence of insertions:
Code:3,7,5,4,2,1,6
3
/ \
2 7
/ /
1 5
/ \
4 6
As others are stating, an AVL tree is always supposed to be balanced with the exception of during an insertion or deletion. By the end of the insertion or deletion, however, you should have balanced the tree.
1. insert a node
2. check if balanced
3. if not balanced, balance
Thanks for the replies.
Take the middle element of the sorted array. This will be the root of the tree. Take everything left of this middle element and construct a balanced tree from it, and make this the left subtree. Same for the right. Recursive implementation is just a few lines.Quote:
Originally Posted by BoneXXX
If the data is already sorted, there is no need to make a tree out of it. Just do binary search.
Is this for an assignment? If not, you're making things harder than they need to be. The height of ANY balanced tree of N nodes is simply floor(log2(N))+1.
Thats the way I intend to balance my ternary tree code. Adding the logic to balance the tree during every insertion and deletion is just a pain. Of course if the tree is large and unbalanced, you might run out of stack space. Thus iteration with a stack (LIFO) allocated from the heap for your node traversal is in order, rather than the more elegant recursive solution.Quote:
Originally Posted by brewbuck
My question, however, is this:
Is generating a sorted list from a potentially unbalanced ternary (or even binary) tree of order n, the number of entries? For a binary tree I think the answer is yes, that you only have to visit each node at most three times as you do a depth first traversal. For ternary trees where the sort is in lexigraphical order I think you visit a node at most 4 times.