PLEASE FILL IN THE FUNCTIONS BELOW WHERE IT SAYS FIX ME COMPLETE THE FUNCTION, FOR C PROGRAMMING .

A function h(Node) will be useful to determine the height of a child node. Since leaf nodes have height zero, a value of -1 is returned for a null value. Using this, a function setHeight can be defined that will set the height value of a node, assuming that the height of the child nodes is known:

int _h(struct AVLnode * current) {if (current == 0) return -1; return current->height;}

void _setHeight (struct AVLnode * current) { int lch = h(current->left); int rch = h(current->right); if (lch < rch) current->height = 1 + rch; else current->height = 1 + lch;

}

Armed with the height information, the AVL tree algorithms are now easy to describe. The addition and removal algorithms for the binary search tree are modified so that their very last step is to invoke a method balance:

struct AVLnode * _AVLnodeAdd (struct AVLnode* current, TYPE newValue) { struct AVLnode * newnode; if (current == 0) {

newnode = (struct AVLnode *) malloc(sizeof(struct AVLnode)); assert(newnode != 0); newnode->value = newValue; newnode->left = newnode->right = 0;

return newnode; //why dont we balance here ?? } else if (LT(newValue, current->value))

current->left = AVLnodeAdd(current->left, newValue); else current->right = AVLnodeAdd(current->right, newValue); return balance(current); /* <- NEW the call on balance */

}

The function balance performs the rotations necessary to restore the balance in the tree. Let the balance factor be the difference in height between the right and left child trees. This is easily computed using a function. If the balance factor is more than 2, that is, if one subtree is more than two levels different in height from the other, then a rebalancing is performed. A check must be performed for double rotations, but again this is easy to determine using the balance factor function. Once the tree has been rebalanced the height is set by calling setHeight:

int _bf (struct AVLnode * current) { return h(current->right) - h(current->left); }

struct AVLnode * _balance (struct AVLnode * current) { int cbf = bf(current); if (cbf < -1) {

if (bf(current->left) > 0) // double rotation current->left = rotateLeft(current->left);

return rotateRight(current); // single rotation } else if (cbf > 1) {

if (bf(current->right) < 0) current->right = rotateRight(current->right);

return rotateLeft(current); }

setHeight(current);

return current; }

Since the balance function looks only at a node and its two children, the time necessary to perform rebalancing is proportional to the length of the path from root to leaf.

Insert the values 1 to 7 into an empty AVL tree and show the resulting tree after each step. Remember that rebalancing is performed bottom up after a new value has been inserted, and only if the difference in heights of the child trees are more than one.

Complete the implementation of the AVLtree abstraction by writing the methods to perform a left and right rotation. Both these methods should call setHeight on both the new interior node that has been changed and the new root. Other methods that are similar to those of the Binary Search Tree have been omitted:

struct AVLnode * _rotateLeft (struct AVLnode * current) {

FIX ME, COMPLETE THIS FUNCTION !!

}

struct AVLnode * _rotateRight (struct AVLnode * current) {

FIX ME , COMPLETE THIS FUNCTION

}

Finally, lets write the remove function for the AVL Tree. It is very similar to the remove() for a BST, however, you must be sure to balance when appropriate. Weve provide the remove function, you must finish the implementation of the removeHelper. Assume you have access to removeLeftMost and LeftMost which we have already written for the BST.

void removeAVLTree(struct AVLTree *tree, TYPE val) { if (containsAVLTree(tree, val)) {

tree->root = _removeNode(tree->root, val);

tree->cnt--; }

}

TYPE _leftMost(struct AVLNode *cur) { while(cur->left != 0) {

cur = cur->left;

} return cur->val;

}

struct AVLNode *_removeLeftmost(struct AVLNode *cur) { struct AVLNode *temp;

if(cur->left != 0) {

cur->left = _removeLeftmost(cur->left);

return _balance(cur); }

temp = cur->rght; free(cur); return temp;

}

struct AVLNode *_removeNode(struct AVLNode *cur, TYPE val) {

FIX ME, COMPLETE THIS FUNCTION

}