Thread: How do you create a balanced binary tree?

  1. #1
    Registered User Mr_Jack's Avatar
    Join Date
    Oct 2003
    Posts
    63

    How do you create a balanced binary tree?

    I can't figure out how to make a binary tree efficiently and all of the the tutorials on the interenet SUCK. Can someone please post some code?

  2. #2
    'AlHamdulillah
    Join Date
    Feb 2003
    Posts
    790
    prelude posted a great tutorial not that long ago, i would look at it if I were you

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Can someone please post some code?
    I am in the process of writing a tutorial on this that covers AVL trees, Red-Black trees, B-trees, randomized trees, and miscellaneous techniques as a companion to the binary search tree tutorial in the FAQ. I am not sure how much longer it will take as I am juggling tutorials on several topics at the moment, so here is some temporary code that you can play with:
    Code:
    int insert ( struct avl **tree, struct avl *new_item )
    {
      if ( *tree == NULL ) {
        *tree = new_item;
        return 1;
      }
      if ( cmp ( (*tree)->data, new_item->data ) > 0 ) {
        if ( (*tree)->left != NULL ) {
          if ( insert ( &(*tree)->left, new_item ) != 0 ) {
            if ( (*tree)->bal++ < 1 )
              return (*tree)->bal;
            else if ( (*tree)->left->bal > 0 ) {
              rrotate ( tree );
              (*tree)->bal = 0;
              (*tree)->right->bal = 0;
            }
            else {
              lrotate ( &(*tree)->left );
              rrotate ( tree );
              switch ( (*tree)->bal ) {
              case 1:
                (*tree)->left->bal = -1;
                (*tree)->right->bal = 0;
                break;
              case 0:
                (*tree)->left->bal = 0;
                (*tree)->right->bal = 0;
                break;
              default:
                (*tree)->left->bal = 0;
                (*tree)->right->bal = 1;
              }
              (*tree)->bal = 0;
            }
          }
          else
            return 0;
        }
        else {
          (*tree)->left = new_item;
          (*tree)->bal++;
          return (*tree)->bal;
        }
      }
      else if ( cmp ( (*tree)->data, new_item->data ) < 0 ) {
        if ( (*tree)->right != NULL ) {
          if ( insert ( &(*tree)->right, new_item ) != 0 ) {
            if ( (*tree)->bal++ < 1 )
              return (*tree)->bal;
            else if ( (*tree)->right->bal > 0 ) {
              lrotate ( tree );
              (*tree)->bal = 0;
              (*tree)->left->bal = 0;
            }
            else {
              rrotate ( &(*tree)->right );
              lrotate ( tree );
              switch ( (*tree)->bal ) {
              case 1:
                (*tree)->left->bal = -1;
                (*tree)->right->bal = 0;
                break;
              case 0:
                (*tree)->left->bal = 0;
                (*tree)->right->bal = 0;
                break;
              default:
                (*tree)->left->bal = 0;
                (*tree)->right->bal = 1;
              }
              (*tree)->bal = 0;
            }
          }
          else
            return 0;
        }
        else {
          (*tree)->right = new_item;
          (*tree)->bal++;
          return (*tree)->bal;
        }
      }
    
      return 0;
    }
    Bugs:

    The code for rrotate, lrotate, and cmp is simple enough for you to write on your own. If you have trouble with the rotations, see my binary search tree tutorial in the FAQ. It covers rotation while discussing root insertion.

    The solution is recursive. This isn't really a bug, but I prefer to write non-recursive code for trees whenever I can. However, the code for a non-recursive insertion is considerably more complicated and I'm not sure I can give you working code from memory.

    The code is uncompiled and untested. I wrote it directly from brain to forum, so there may be typos and real errors.

    Code for deletion is not included for the same reason I did not use a non-recursive approach.

    None of the types are included (ie. struct avl), but you can easily determine what is needed for it from the code given.

    Disclaimer:

    This code is given as-is. I make no claims on it being correct or even compilable, so don't come complaining to me if it doesn't work. If it does work, all the better for my reputation.

    p.s. I really hope this works.
    My best code is written with the delete key.

  4. #4
    'AlHamdulillah
    Join Date
    Feb 2003
    Posts
    790
    This code is given as-is. I make no claims on it being correct or even compilable, so don't come complaining to me if it doesn't work. If it does work, all the better for my reputation.
    you forgot the part about "in case of destruction of property by using my code..."

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Inserting value to a sorted binary tree?
    By HappySmileMan in forum C Programming
    Replies: 3
    Last Post: 02-15-2009, 09:34 AM
  2. problem in creating a tree
    By Lorin_sz in forum C++ Programming
    Replies: 2
    Last Post: 09-26-2005, 01:28 PM
  3. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM
  4. Code to test if a tree is balanced
    By rahuls in forum C Programming
    Replies: 1
    Last Post: 03-20-2003, 02:41 PM
  5. read records fron file into a binary tree
    By Kirsten in forum C Programming
    Replies: 1
    Last Post: 04-23-2002, 02:48 PM