Balancing a tree (AVL Tree)

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. ...

  1. #1
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62

    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.
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211

  3. #3
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    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

  4. #4
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    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?

  5. #5
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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?

  6. #6
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    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

  7. #7
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Recursion is probably the easiest way to handle it instead of doing it iteratively with loops.

  8. #8
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    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

  9. #9
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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.

  10. #10
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    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 05:44 AM.
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  11. #11
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    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.

  12. #12
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    Quote Originally Posted by BoneXXX View Post
    Thanks for the quick reply.Shouldn't I need to balance the tree to get the height right?

    Binary search tree height
    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.

  13. #13
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    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.
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  14. #14
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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)

  15. #15
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    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?
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. AVL tree balancing problem
    By sweets in forum C++ Programming
    Replies: 4
    Last Post: 05-06-2004, 12:17 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21