trouble balancing an unbalanced binary tree

does anyone have now any good websites that have a page devoted to balancing an unbalanced tree, i found one myself but its in c++ only and i cant find any others.

also if anyone has any advice, (dont want the code), that would be just as good


heres what i think i should do

1) put the node pointers into an array
2) sort the array
3) destroy the root of the tree
4) find the middle of the array
5) do some recursion and keep finding the middle until all the remaining pointers are added to the new tree

when i tried to read the addresses in they sorted themselves, but not the information contained within the addresses, i used an in order traversal

my information is all characters so i want the lowest letters at the start of the array

heres what i got so far (not much i'm afraid)


void balanceTree(PTRnode* &root, datatype &data, int &numberCDS)
{
PTRnode *tempnode[300]; //temporary storage for node addresses
static int index = 0;

tempnode[index]=inOrderTraversal(root, data); //call to function that sorts in Order
index++; //increment index by 1


}


PTRnode* inOrderTraversal(PTRnode* &root, datatype &data)
{
if(root->left!=NULL) //check if root->left is not equal to NULL
{
inOrderTraversal(root->left, data); //call function and go left
}
else
{
return root; //return the roots contents
}
if(root->right!=NULL) //check if root->right is not equal to NULL
{
inOrderTraversal(root->right, data); //call function and go right
}
}



i hope you can make sense out of all that

Well, first off you need to fix up your inOrderTraversal() to actually write the array. There's a couple ways to do this, but here's a prototype that I think works well...

Code:

---

int inOrderTraversal (PTRnode * root, PTRnode * array);
// Copies the elements of root's tree into array.
// Returns the number of elements copied.

---

However, the code you have here appears to have a lot of incorrect syntax, and I fail to understand what the data parameter is for.

Here is some info on a balanced binary tree aka AVL tree.

http://purists.org/avltree/

More sites can be found at http://www.google.com/search?sourcei...tree+algorithm

What you have is a good algo for balancing an unbalanced tree, it would be inefficent to call that everytime the tree is changed. It would be better to keep the tree balanced at all times by taking care of it during the inserts and deletes

There are many kinds of balanced trees. For example AVL trees, Splay trees, etc. Google gives many results when searching for these things.

In database code, in order to balance a tree (shorter sort times) you essentially "roll" your tree left or right until it is once again balanced.

This works with any tree, b, b+, b*, n-way, k-way, etc.

I would recommend you find a book on database file structures-- usually in your college bookstore. It will explain all of this. Don't be mislead by the title referring to 'file structures'. Back when most of this stuff was figured out, the program usually had to work off disk because there wasn't enough RAM to hold everything.

Principles are the same.

enjoy.