Thread: still cany suss out this balancing problem

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    54

    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

  2. #2
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help understanding a problem
    By dnguyen1022 in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2009, 04:21 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM