Binary Tree

[1v5E3TCk]

I am trying to learn about binay trees And I want to make the program able to balance the tee when user wants. For doing that it counts the number of nodes and creates an array to save current tree. And sort it then starts creating a new tree from middle of the array. But it doesnt save nodes into array just the first node.

If you want I can send the full code.

  int func_count_node( node* p_tree)
{
    int sum = 0;

    if( p_tree->p_left != NULL)
    {
        sum += func_count_node( p_tree->p_left );
    }
    else if( p_tree->p_right != NULL)
    {
        sum += func_count_node( p_tree->p_right );
    }

    ++sum;
    return sum;
}

node* func_balance_tree( node* p_tree, node* p_array[], int num)
{

    if( p_tree->p_left != NULL)
    {
        func_balance_tree( p_tree->p_left, p_array, ++num );
    }
    if( p_tree->p_left != NULL)
    {
        func_balance_tree( p_tree->p_right, p_array, ++num );
    }
        p_array[num] = p_tree;
}

void sort (node* array[], int size)
{
	for ( int i = 0; i < size; i++ )
	{
		int index = findSmallestRemainingElement( array, size, i );
		swap( array, i, index );
	}
}

int findSmallestRemainingElement (node* array[], int size, int index)
{
	int index_of_smallest_value = index;
	for (int i = index + 1; i < size; i++)
	{
		if ( array[ i ]->number < array[ index_of_smallest_value ]->number  )
		{
			index_of_smallest_value = i;
		}
	}
	return index_of_smallest_value;
}

void swap (node* array[], int first_index, int second_index)
{
	node* temp = array[ first_index ];
	array[ first_index ] = array[ second_index ];
	array[ second_index ] = temp;
}

        if( x == 5)
        {
            sum = func_count_node(p_tree);
            if(sum>0)
            {
                node* p_array[sum];
                p_array[sum] = new node;
                p_tree = func_balance_tree(p_tree, p_array, 0);
                sort( p_array, sum);
                delete p_tree;
                p_tree = new node;

                    mid1 = (sum%2)-1;
                    mid2 = mid1+1;

                while(mid1>=0)
                {
                    p_tree = func_add_node( p_tree, p_array[mid1]->number, p_array[mid1]->name);
                    --mid1;
                }
                while(mid2<sum)
                {
                    p_tree = func_add_node( p_tree, p_array[mid2]->number, p_array[mid2]->name);
                    ++mid2;
                }
            }


        }

[Smac89]

Having to count the nodes of the tree to determine if it needs balancing is not a very efficient method because this will take time as the trees grows ( ~O(n) time ) to find all lengths. But with a well implemented binary search tree, you are able to know the height of the tree at any point by keeping track of a single variable. Balancing is then achieved by something known as rotation (avl tree) or zig, zig-zig, zig-zag(splay tree), etc for different balance trees

Wikipedia gives some information on self-balancing trees:
http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree#Implementations

I have recently completed an implementation of an avl search tree. If you are interested in taking a look at that: http://www.cplusplus.com/forum/beginner/108093/#msg588108

Other helpful links:
http://pages.cs.wisc.edu/~paton/readings/liblitVersion/AVL-Tree-Rotations.pdf
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

[Catfish4]

It's just as hard for us to find logical errors in your code as it is for you.

People here are most helpful when you don't know/understand something about C++, and they can give a simple answer.

Posting your code saying "it doesn't work, I don't know why" is unlikely to be fruitful unless the code is very simple, and yours isn't.

Tree balancing is a bit complicated. Do you already have an algorithm for balancing that you can translate to C++? If not, maybe read these:

http://www.mec.ac.in/resources/notes/notes/ds/bal.htm
http://courses.cs.vt.edu/~cs2604/fall05/mcpherson/note/BalancingTrees.ppt
http://www.stoimen.com/blog/2012/07/03/computer-algorithms-balancing-a-binary-search-tree/

Good luck.

[1v5E3TCk]

Thakns for helps. I will read about them.

[ResidentBiscuit]

Red-Black trees are super neat and auto-balance themselves. They are pretty complicated, though. Would be a good project if you understand various types of trees already.

[Catfish4]

I am trying to learn about binay trees And I want to make the program able to balance the tee when user wants.

Leaving it to the user to decide when to balance the tree is a bit weird.
How can the user know when balancing is required and when it's just a waste of time? And if you provide a check_if_well_balanced() function, you might as well be handling the tree balance yourself, no?

So like the others already hinted, you should look at self-balancing binary trees.

[1v5E3TCk]

thanks for replies I will look at them at choose a good one :D