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?

prelude posted a great tutorial not that long ago, i would look at it if I were you

>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. :D

Quote:

---

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..."