Question 4: AVL trees [10]

Suppose we decided to use an array to store an AVL tree, i.e. storing the root in position 0, children of node i in positions 2i+1 and 2i+2, etc.

The elements of the array (i.e. nodes of the avl tree) will be structs which contain the data value (a string) and the height of the subtree, e.g.:

struct node {
   int height;
   string key;
};
node Array[SIZE];

Write the body of the avl tree insert method below. (You can assume the existence of a CheckForRotation routine, which updates a node's height and checks for/applies any necessary rotations.)

// s is the new string to be inserted,
// pos is the position of the current node
// this allows a recursive insert, where
//    the initial call would be insert(s, 0);
bool avltree::insert(string s, int pos)