still cany suss out this balancing problem

i've tried numerous code attempts(all seem to crash the machine),
can anyone explain in easy to understand terms how to balance a binary search tree

the basic explanation of my program is that i've got a load of CDS and would like to store them to a file and load them up again when needed, the CDS are placed within a binary tree and gets sorted according to the artist name, the rest of the details are CD title, number of tracks, and tracklist

heres my structure for the tree

struct tracks
{
char SongTitle[40];
};

struct datatype
{
char artist[40]; //key field
char title[40];
int numberTracks;
tracks SongList[24];

};

struct PTRnode
{

datatype data;
PTRnode *left;
PTRnode *right;
};

any help whatsoever will be much appreciated, please be as basic as possible as we haven't covered this topic in class yet and i dont want to wait until then


thanx korbitz

There are many ways to balance a binary search tree. Here's an example.

Definition: An AVL tree is a binary search tree which heights of the left and right subtrees of the root differ at most 1 and in which the left and right subtrees are again AVL trees.

A basic action in balancing trees is rotating. Take a paper and pencil and keep the definition in mind while I explain how this is being done.

Assume we have the keys K and M. Now K is the root and M is the right child. This tree is a AVL tree since the heights of the left ( = 0) differs at most 1 of the right ( = 1). According to the definition also the right subtree must be an AVL tree, as you can see, this is true.

Now we add the key U. U is larger than K and M and so it is the right child of M. Note that the tree now isn't an AVL tree anymore. The left subtree of K has height 0 and the right subtree of K has height 2.

Now we must rotate. Since the right tree is unbalanced, we must rotate to left. When doing this, M becomes root and K and U become the left and right subtrees of M. As you see, the tree is now an AVL tree again.

We add key T. This is the left child of U. When looking from M, the tree is an AVL tree. Check that also the right and left subtrees are AVL trees. And note that the left and right subtrees of U are also subtrees.

Now we add key P. As you see, P is the left child of T. Check that the tree is not an AVL tree anymore. The right subtree is higher than the left, so will need to rotate to the left. But there is a complication since the left subtree of U is higher than the right subtree of U. We do now need a double rotation. First we will rotate the subtrees of U to the right. And then rotate the the subtrees of M to the left.

Finally we have the following AVL tree. T is root. Left child is M and right child is U. Left child of M is K and right child of M is P. And right child of U is V.

Hope this will explain the algorithm a little bit. There's a lot of information on balancing trees on the Internet.