/**
 * @file avltree.cpp
 * Definitions of the binary tree functions you'll be writing for this lab.
 * You'll need to modify this file.
 */

template <class K, class V>
V AVLTree<K, V>::find(const K& key) const
{
    return find(root, key);
}

template <class K, class V>
V AVLTree<K, V>::find(Node* subtree, const K& key) const
{
    if (subtree == NULL)
        return V();
    else if (key == subtree->key)
        return subtree->value;
    else {
        if (key < subtree->key)
            return find(subtree->left, key);
        else
            return find(subtree->right, key);
    }
}

template <class K, class V>
void AVLTree<K, V>::rotateLeft(Node*& t)
{
    functionCalls.push_back("rotateLeft"); // Stores the rotation name (don't remove this)
  Node * temp = t;
  Node * temp2 = t->right;

  temp->right = temp2->left;
  temp2->left = temp;
  t = temp2;
  updateHeight(temp);
  updateHeight(temp);
}

template <class K, class V>
void AVLTree<K, V>::rotateLeftRight(Node*& t)
{
    functionCalls.push_back("rotateLeftRight"); // Stores the rotation name (don't remove this)
    // Implemented for you:
    rotateLeft(t->left);
    rotateRight(t);
}


template <class K, class V>
void AVLTree<K, V>::updateHeight(Node*& node) {
  node->height = 1 + max(heightOrNeg1(node->left), heightOrNeg1(node->right));
}



template <class K, class V>
void AVLTree<K, V>::rotateRight(Node*& t)
{
    functionCalls.push_back("rotateRight"); // Stores the rotation name (don't remove this)
    Node *temp = t;
    Node *temp2 = t->left;

    temp->left = temp2->right;
    temp2->right = temp;
    t = temp2;
  updateHeight(temp);
  updateHeight(temp2);
}

template <class K, class V>
void AVLTree<K, V>::rotateRightLeft(Node*& t)
{
    functionCalls.push_back("rotateRightLeft"); // Stores the rotation name (don't remove this)
    rotateRight(t->right);
    rotateLeft(t);
}

template <class K, class V>
void AVLTree<K, V>::rebalance(Node*& subtree)
{
  if (!subtree) {
    return;
  }
  int balance = heightOrNeg1(subtree->right) - heightOrNeg1(subtree->left);

  if (balance == -2) {
    int leftbalance = heightOrNeg1(subtree->left->right) - heightOrNeg1(subtree->left->left);
    if (leftbalance == -1 ) {
      rotateRight(subtree);
    } else {
      rotateLeftRight(subtree);
    }
  } else if (balance == 2) {
    int rightbalance = heightOrNeg1(subtree->right->right) - heightOrNeg1(subtree->right->left);
    if (rightbalance == 1 ){
      rotateLeft(subtree);
    } else {
      rotateRightLeft(subtree);
    }
  }
  updateHeight(subtree);
}

template <class K, class V>
void AVLTree<K, V>::insert(const K & key, const V & value)
{
    insert(root, key, value);
}

template <class K, class V>
void AVLTree<K, V>::insert(Node*& subtree, const K& key, const V& value)
{
  if (subtree == NULL) {
    subtree = new Node(key, value);
    return;
  } else if (key > subtree->key) {
    insert(subtree->right, key, value);
  } else if (key < subtree->key) {
    insert(subtree->left, key, value);
}
rebalance(subtree);

}

template <class K, class V>
void AVLTree<K, V>::remove(const K& key)
{
    remove(root, key);
}

template <class K, class V>
void AVLTree<K, V>::remove(Node*& subtree, const K& key)
{
    if (subtree == NULL)
        return;

    if (key < subtree->key) {
        // your code here
    } else if (key > subtree->key) {
        // your code here
    } else {
        if (subtree->left == NULL && subtree->right == NULL) {
            /* no-child remove */
            // your code here
        } else if (subtree->left != NULL && subtree->right != NULL) {
            /* two-child remove */
            // your code here
        } else {
            /* one-child remove */
            // your code here
        }
        // your code here
    }
}