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

- 04-10-2007BoneXXXBalancing a tree (AVL Tree)
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.

- 04-10-2007MacGyver
- 04-10-2007BoneXXX
Thanks for the reply, I know how it works on paper, just having a difficulty to code.

- 04-10-2007MacGyver
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?

- 04-10-2007KONI
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? - 04-10-2007BoneXXX
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. - 04-10-2007MacGyver
Recursion is probably the easiest way to handle it instead of doing it iteratively with loops.

- 04-12-2007BoneXXX
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 - 04-12-2007KONI
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. - 04-12-2007BoneXXX
Thanks for the quick reply.Shouldn't I need to balance the tree to get the height right?

http://cboard.cprogramming.com/c-programming/88462-binary-search-tree-height.html - 04-12-2007MacGyverQuote:

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.

Code:`int height(node_ptr tree)`

{

if(tree == NULL)

{

return -1;

}

return max(height(tree->left),height(tree->right)) + 1;

}

- 04-12-2007KONI
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. - 04-12-2007BoneXXX
In my program I get random inputs from a user

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. - 04-12-2007KONI
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) - 04-12-2007BoneXXX
This is my insert function:

Code:`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?