Implement the following member functions:

AVL(bool isAVL) Simple default constructor to initialize the isAVL flag. If the isAVL flag is set, insertions and deletions will follow AVL property. Otherwise, it will be a simple BST.

void insertNode(shared_ptr> N) Inserts the given node into the tree such that the AVL (or BST) property holds.

void deleteNode(T k) Deletes the node with the given key such that the AVL (or BST) property holds. As convention, while deleting a node with 2 children, the new root should be selected from the right subtree.

shared_ptr> searchNode(T k) Returns the pointer to the node with the given key. NULL is returned if the key doesnt exist.

shared_ptr> getRoot() Returns the pointer to the root node of the tree.

int height(shared_ptr> p) Returns the height of the tree. the height of a tree is the number of nodes in the path from the root to its deepest descendant. For example, a tree with only two nodes (a root and a child) will have height 2 and so on.

Starter code:

template

struct node {

S fullName;

T workExperience;

string gender;

shared_ptr left;

shared_ptr right;

int height;

node(T w, S n, C g) {

this->fullName = n;

this->workExperience = w;

this->gender = g;

left = NULL;

right = NULL;

height = 1;

}

};

// AVL Class (This will be used for both BST and AVL Tree implementation)

template

class AVL {

shared_ptr> root;

bool isAVL;

public:

AVL(bool);

void insertNode(shared_ptr>);

void deleteNode(T k);

shared_ptr>getRoot();

shared_ptr>searchNode(T k);

int height (shared_ptr > p);

};

Code this all in c++