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.
This is a discussion on Balancing a tree (AVL Tree) within the C Programming forums, part of the General Programming Boards category; I am having a difficulty to convert my knowledge that is about balancing a tree on paper into C codes. ...
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.
“Example isn't another way to teach, it is the only way to teach” Albert Einstein
Thanks for the reply, I know how it works on paper, just having a difficulty to code.
“Example isn't another way to teach, it is the only way to teach” Albert Einstein
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.
“Example isn't another way to teach, it is the only way to teach” Albert Einstein
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
“Example isn't another way to teach, it is the only way to teach” Albert Einstein
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?
Binary search tree height
Last edited by BoneXXX; 04-12-2007 at 06:44 AM.
“Example isn't another way to teach, it is the only way to teach” Albert Einstein
http://cis.stvincent.edu/html/tutori.../avltrees.htmlThe 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.
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.
“Example isn't another way to teach, it is the only way to teach” Albert Einstein
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?
“Example isn't another way to teach, it is the only way to teach” Albert Einstein