#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef DEBUG
#define DPRINTF(x) fprintf x
#else
#define DPRINTF(x)
#endif

typedef struct avl_node { 
  const char *data; 
  int height;
  struct avl_node *left;
  struct avl_node *right;
} avl_node;

/*
 * Adds the character array into the AVL tree.  You will NOT malloc out 
 * data for the character array.  Simply store a reference to it.  Returns
 * the root of the tree after the add.  
 *
 * To create a new avl_tree you will simply add to a null tree.
 * Example:
 *  avl_tree *root = avl_add(NULL,"hello");
 */
avl_node *avl_add(avl_node *,const char *);

/*
 * Determines whether or not the avl tree contains the specified char*.  If
 * it does not it will return 0.  If it does it will return 1.
 */
int avl_has(avl_node *,const char *);
/* 
 * Delete a string from the avl tree.  The tree will remain balanced after 
 * this operation.  If the char* is not in the tree the structure should 
 * remain unchanged
 *
 * *** NOTE *** 
 * This function is optional.  No credit will be gained or lost as a 
 * result of coding this function.  It is fairly difficult when you can 
 * only consider the balance factor stored in the nodes.  However we 
 * encourage you to try it.  If you do not wish to code this function, 
 * just have it return the value passed in. 
 * ************
 */
avl_node *avl_delete(avl_node *,const char *);

/*
 * Performs a left rotation on the root node that is passed in and returns 
 * the new root node for the subtree.
 */
avl_node *avl_left_rotate(avl_node *);

/*
 * Performs a right rotation on the root node that is passed in and returns
 * the new root node for the subtree.  This function must update the 
 * balance factors for the nodes involved.  
 */
avl_node *avl_right_rotate(avl_node *);

/*
 * Performs a left right rotation on the root node that is passed in and 
 * returns the new root node for the subtree.  This function must update
 * the balance factor of the nodes involved.  
 */
avl_node *avl_left_right_rotate(avl_node *);

/*
 * Performs a right left rotation on the root node that is passed in and 
 * returns the new root node for the subtree.  This function must update
 * the balance factor of the nodes involved. 
 */
avl_node *avl_right_left_rotate(avl_node *);

/*
 * Frees all nodes in the avl tree and sets the node passed in to NULL
 */
void avl_free(avl_node**);