Write a c++ function restructure to perform a rotation operation on an unbalanced binary tree

#ifndef AVLTREE_H
#define AVLTREE_H
#include "AVLEntry. h"
#include "BoundaryViolation. h"
#include "NonexistentElement. h"
#include "SearchTree. h"
#include "PrintExpressionTour. h"

template // an AVL tree
class AVLTree : public SearchTree< AVLEntry > {
public: // public types
typedef AVLEntry AVLEntry; // an entry
typedef typename SearchTree::Iterator Iterator; // an iterator
protected: // local types
typedef typename AVLEntry::Key K; // a key
typedef typename AVLEntry::Value V; // a value
typedef SearchTree ST; // a search tree
typedef typename ST::TPos TPos; // a tree position
public: // public functions
AVLTree(); // constructor
Iterator insert(const K& k, const V& x); // insert (k, x)
void erase(const K& k) throw(NonexistentElement); // remove key k entry
void erase(const Iterator& p); // remove entry at p
protected: // utility functions
int height(const TPos& v) const; // node height utility
void setHeight(TPos v); // set height utility
bool isBalanced(const TPos& v) const; // is v balanced?
TPos tallGrandchild(const TPos& v) const; // get tallest grandchild
void rebalance(const TPos& v); // rebalance utility
void restructure(const TPos& v);
};

template // constructor
AVLTree::AVLTree() : ST() { }

template // node height utility
int AVLTree::height(const TPos& v) const
{
return (v. isExternal() ? 0 : v->height());
}

template // set height utility
void AVLTree::setHeight(TPos v) {
int hl = height(v. left());
int hr = height(v. right());
v->setHeight(1 + std::max(hl, hr)); // max of left & right
}

template // is v balanced?
bool AVLTree::isBalanced(const TPos& v) const {
int bal = height(v. left()) - height(v. right());
return ((-1 <= bal) && (bal <= 1));
}

template // get tallest grandchild
typename AVLTree::TPos AVLTree::tallGrandchild(const TPos& z) const {
TPos zl = z. left();
TPos zr = z. right();
if (height(zl) >= height(zr)) // left child taller
if (height(zl. left()) >= height(zl. right()))
return zl. left();
else
return zl. right();
else // right child taller
if (height(zr. right()) >= height(zr. left()))
return zr. right();
else
return zr. left();
}

template // insert (k, x)
typename AVLTree::Iterator AVLTree::insert(const K& k, const V& x) {
TPos v = inserter(k, x); // insert in base tree
setHeight(v); // compute its height
rebalance(v); // rebalance if needed
return Iterator(v);
}

template // remove key k entry
void AVLTree::erase(const K& k) throw(NonexistentElement) {
TPos v = finder(k, ST::root()); // find in base tree
if (Iterator(v) == ST::end()) // not found?
throw NonexistentElement("Erase of nonexistent");
TPos w = eraser(v); // remove it
rebalance(w); // rebalance if needed
}

template
void AVLTree::restructure(const TPos& x)
{

}

template // rebalancing utility
void AVLTree::rebalance(const TPos& v) {
TPos z = v;
while (!(z == ST::root())) { // rebalance up to root
z = z. parent();
setHeight(z); // compute new height
if (!isBalanced(z)) { // restructuring needed
TPos x = tallGrandchild(z);
z = restructure(x); // trinode restructure
setHeight(z. left()); // update heights
setHeight(z. right());
setHeight(z);
}
}
}
#endif