template<class T>
class AVLNode {
public:
    AVLNode() { 
        left = right = 0; 
    }
    AVLNode(const T& el, AVLNode *l = 0, AVLNode *r = 0) {
        key = el; left = l; right = r; 
    }
    T key;
    AVLNode *left, *right, *parent;
  int balance;
};

template<class T>
class AVLTree {
private:
  AVLNode<T>* root;

  void rightRotation(AVLNode<T>* node) {
    AVLNode<T>* left = node->left;
    AVLNode<T>* parent = node->parent;

    left->parent = parent;
    node->left = left->right;
    node->left->parent = node;
    left->right = node;
    node->parent = left;
    if(parent->left == node)
      parent->left = left;
    else
      parent->right = left;
  }
};