Thread: Balancing 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.

http://en.wikipedia.org/wiki/AVL_Tree

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?

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

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

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.

http://cis.stvincent.edu/html/tutori.../avltrees.html

Code:

int height(node_ptr tree)
{
	if(tree == NULL)
	{
		return -1;
	}
	return max(height(tree->left),height(tree->right)) + 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.

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

Just one thing left that is I need to write a function to find the height of the tree.

if the user enter these values in to the program

3,7,5,4,2,1,6

The height should be 2.

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;
}

3,7,5,4,2,1,6

-----4 -----> 0
---/---\
--2----6 ------->1
-/-\---/-\
1--3-5--7 -------->2

I was thinking the tree like this, is this wrong?