#include
#include
#include
#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**);