In tree_find and tree_find_min you're not really gaining anything from using recursion. For example, I think tree_find_min would probably be clearer something like:

tree_position tree_find_min( search_tree tree )
{
   if ( tree == NULL )
      return NULL;
   while (tree->left != NULL)
       tree = tree->left;
   return tree;
}

As a side-benefit, this may also be faster with some compilers. In code like:

 HATE_DATA *hatedata;

 /* ... */

 hatedata = (HATE_DATA * ) malloc( sizeof( HATE_DATA ) );

I'd change it to look more like:

 hatedata = malloc(sizeof(*hatedata));

The cast accomplishes nothing useful in C, and can cover up the bug of forgetting to #include <stdlib.h> to get the proper prototype for malloc. Using sizeof(*hatedata) instead of sizeof(HATE_DATA) means that changing the type only requires changing it in one place (where you've defined the variable), instead of everywhere you've done an allocation.

In tree_find and tree_find_min [edit: and even in tree_insert] you're not really gaining anything from using recursion. For example, I think tree_find_min would probably be clearer something like:

tree_position tree_find_min( search_tree tree )
{
   if ( tree == NULL )
      return NULL;
   while (tree->left != NULL)
       tree = tree->left;
   return tree;
}

As a side-benefit, this may also be faster with some compilers. In code like:

 HATE_DATA *hatedata;

 /* ... */

 hatedata = (HATE_DATA * ) malloc( sizeof( HATE_DATA ) );

I'd change it to look more like:

 hatedata = malloc(sizeof(*hatedata));

The cast accomplishes nothing useful in C, and can cover up the bug of forgetting to #include <stdlib.h> to get the proper prototype for malloc. Using sizeof(*hatedata) instead of sizeof(HATE_DATA) means that changing the type only requires changing it in one place (where you've defined the variable), instead of everywhere you've done an allocation.