#include "AVL_tree.h"

/*************************************************************************

** Suggested helper functions

*************************************************************************/

/* Returns the height (number of nodes on the longest root-to-leaf path) of

* the tree rooted at node 'node'. Returns 0 if 'node' is NULL.

*/

int height(AVL_Node* node);

/* Updates the height of the tree rooted at node 'node' based on the heights

* of its children. Note: this should be an O(1) operation.

*/

void update_height(AVL_Node* node);

/* Returns the balance factor (height of left subtree - height of right

* subtree) of node 'node'. Returns 0 of node is NULL.

*/

int balance_factor(AVL_Node* node);

/* Returns the result of performing the corresponding rotation in the AVL

* tree rooted at 'node'.

*/

// single rotations: right/clockwise

AVL_Node* right_rotation(AVL_Node* node);

// single rotations: left/counter-clockwise

AVL_Node* left_rotation(AVL_Node* node);

// double rotation: right/clockwise then left/counter-clockwise

AVL_Node* right_left_rotation(AVL_Node* node);

// double rotation: left/counter-clockwise then right/clockwise

AVL_Node* left_right_rotation(AVL_Node* node);

/* Returns the successor node of 'node'. */

AVL_Node* successor(AVL_Node* node);

/* Creates and returns an AVL tree node with key 'key', value 'value', height

* of 1, and left and right subtrees NULL.

*/

AVL_Node* create_node(int key, void* value);

/*************************************************************************

** Provided functions

*************************************************************************/

void print_tree_inorder_(AVL_Node* node, int offset) {

if (node == NULL) return;

print_tree_inorder_(node->right, offset + 1);

printf("%*s %d [%d] ", offset, "", node->key, node->height);

print_tree_inorder_(node->left, offset + 1);

}

void print_tree_inorder(AVL_Node* node) {

print_tree_inorder_(node, 0);

}

void delete_tree(AVL_Node* node) {

if (node == NULL) return;

delete_tree(node->left);

delete_tree(node->right);

free(node);

}

/*************************************************************************

** Required functions

** Must run in O(log n) where n is the number of nodes in a tree rooted

** at 'node'.

*************************************************************************/

AVL_Node* search(AVL_Node* node, int key) {

return node;

}

AVL_Node* insert(AVL_Node* node, int key, void* value) {

return node;

}

AVL_Node* delete(AVL_Node* node, int key) {

return node;

}

This is AVL_tree.h file below:

#include

#include

#ifndef __AVL_tree_header

#define __AVL_tree_header

typedef struct avl_node {

int key; // key stored in this node

void* value; // value associated with this node's key

int height; // height of tree rooted at this node

struct avl_node* left; // this node's left child

struct avl_node* right; // this node's right child

} AVL_Node;

/* Returns the node, from the tree rooted at 'node', that contains key 'key'.

* Returns NULL if 'key' is not in the tree.

*/

AVL_Node* search(AVL_Node* node, int key);

/* Inserts the key/value pair 'key'/'value' into the AVL tree rooted at

* 'node'. If 'key' is already a key in the tree, updates the value

* associated with 'key' to 'value'. Returns the root of the resulting tree.

*/

AVL_Node* insert(AVL_Node* node, int key, void* value);

/* Deletes the node with key 'key' from the AVL tree rooted at 'node'. If

* 'key' is not a key in the tree, the tree is unchanged. Returns the root of

* the resulting tree.

*/

AVL_Node* delete(AVL_Node* node, int key);

/* Prints the keys of the AVL tree rooted at 'node', in the in-order

* traversal order.

*/

void print_tree_inorder(AVL_Node* node);

/* Frees all memory allocated for an AVL tree rooted at 'node'.

*/

void delete_tree(AVL_Node* node);

#endif

Needs to be implemented in C