template<class K, class V>
struct AVLTreeNode
{
  // 三叉连
  AVLTreeNode<K, V>* _left;
  AVLTreeNode<K, V>* _right;
  AVLTreeNode<K, V>* _parent;
  // 平衡因子
  int _bf;
  // 储存的键值对
  pair<K, V> _kv;
  // 构造函数
  AVLTreeNode(const pair<K , V>& kv)
  :_left(nullptr)
  ,_right(nullptr)
  ,_parent(nullptr)
  ,_kv(kv)
  ,_bf(0) //因为构造出来之后没有左右子树 所以说平衡因子为0
  {}
};

cur = parent;
parent = parent->_parent;

bool insert(const pair <K,V>& kv)
  {
  if (_root == nullptr) // 如果AVL树为空 则直接为其根节点
  {
    _root = new Node(kv);
    return true;
  }
  // 如果不为空 则按照二叉树的插入方式 通过key值 即first来比较
  Node* cur = _root; // cur确定当前位置
  Node* parent = nullptr; // parent最后连接用 
  while (cur) // 当cur不为空的时候一直走
  {
    if (kv.first > cur->_kv.first) // 如果插入值大于当前节点 向右移
    {
    cur = cur->_right;
    parent = cur;
    }
    else if (kv.first < cur->_kv.first) // 如果插入值小于当前节点 向右移
    {
    cur = cur->_left;
    parent = cur;
    }
    else // 到这里这种情况说明等于 则插入失败 返回false
    {
    return false;
    }
  }
  // 将待插入节点插入到树中
  cur = new Node(kv);
  // 根据kv的key值来分辨插入的是左子树还是右子树
  if (kv.first > parent->_kv.first)
  {
    parent->_right = cur;
    cur->_parent = parent; // 因为是三叉链 所以要更新父节点
  }
  else // 因为走到这里了kv的key值不可能相等 所以说else就表示小于
  {
    parent->_left = cur;
    cur->_parent = parent; // 因为是三叉链 所以要更新父节点
  }
  // 更新平衡因子
  while (cur != _root) // 最坏的情况 一直更新到根节点 但是cur不可能到根节点
  {
    // 如果是右则平衡因子++ 反之则--
    if (cur = parent->_left)
    {
    parent->_bf--;
    }
    else if (cur = parent->_right)
    {
    parent->_bf++;
    }
    // 平衡因子更新完毕 此时开始查看父亲节点的平衡因子是多少 是否结束 是否需要旋转
    if (parent->_bf == 0) // 如果父亲的平衡因子是0 则停止更新 直接返回
    {
    return true;
    }
    else if (parent->_bf == 1 || parent->_bf == -1) // 如果父亲的平衡因子是1或-1 则继续往上更新
    {
    cur = parent;
    parent = parent->_parent;
    }
    else if (parent->_bf == 2 || parent->_bf == -2) // 如果父亲的平衡因子是2或-2 则进行旋转操作
    {
    // 旋转
    }
  }
  }

void RotateL(Node* parent)
  {
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
  Node* grandparent = parent->_parent;
  // 建立subR和parent的联系
  subR->_left = parent;
  parent->_parent = subR;
  // 建立parent和subRL的联系
  parent->_right = subRL;
  if (subRL) // 有可能subRL为空
  {
    subRL->_parent = parent;
  }
  // 建立grandparent和sunR的联系
  // 这里要分grandparent是否存在以及parent是grandparent的左还是右
  if (grandparent) // 如果进去了 则说明grandparent存在 
  {
    // 如果存在 要分清楚parent在左边还是右边
    if (grandparent->_left == parent)
    {
    grandparent->_left = subR;
    }
    else
    {
    grandparent->_right = subR;
    }
    subR->_parent = grandparent;
  }
  // 否则就是不存在 我们更新_root 并且将subR的父节点置空
  else
  {
    _root = subR;
    subR->_parent = nullptr;
  }
  // 更新平衡因子
  subR->_bf = 0;
  parent->_bf = 0;
  }

void RotateR(Node* parent)
  {
  Node* subL = parent->_left;
  Node* subLR = subL->_right;
  Node* grandparent = parent->_parent;
  // 建立subL和parent之间的联系
  subL->_right = parent;
  parent->_parent = subL;
  // 建立parent和subLR之间的联系 
  parent->_left = subLR;
  if (subLR) // subLR可能不存在 
  {
    subLR->_parent = parent;
  }
  // 建立grandparent和subl之间的联系
  // 这里要分grandparent是否存在以及parent是grandparent的左还是右
  if (grandparent)
  {
    // 如果存在 要分清楚parent在左边还是右边
    if (grandparent->_left == parent)
    {
    grandparent->_left = subL;
    }
    else
    {
    grandparent->_right = subL;
    }
    subL->_parent = grandparent;
  }
  else // 这里就是表示parent就是根节点
  {
    _root = subL;
    subL->_parent = nullptr;
  }
  // 更新平衡因子
  subL->_bf = 0;
  parent->_bf = 0;
  }

void RotateLR(Node* parent)
  {
  Node* subL = parent->_left;
  Node* subLR = parent->_left->_right;
  int bf = subLR->_bf;
  // 以subL作为旋转点左单旋
  RotateL(subL);
  // 以parent作为旋转点右单旋
  RotateR(parent);
  // 平衡因子
  if (bf == 1)
  {
    subLR->_bf = 0;
    subL->_bf = -1;
    parent->_bf = 0;
  }
  else if (bf == -1)
  {
    subLR->_bf = 0;
    subL->_bf = 0;
    parent->_bf = 1;
  }
  else if (bf == 0)
  {
    subLR->_bf = 0;
    subL->_bf = 0;
    parent->_bf = 0;
  }
  else
  {
    assert(false); 
  }
  }

void RotateRL(Node* parent)
  {
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
  int bf = subRL->_bf;
  //  以subR为轴进行右单旋
  RotateR(subR);
  //  以parent为轴进行左单旋
  RotateL(parent);
  //  更新平衡因子
  if (bf == 1)
  {
    subRL->_bf = 0;
    parent->_bf = -1;
    subR->_bf = 0;
  }
  else if (bf == -1)
  {
    subRL->_bf = 0;
    parent->_bf = 0;
    subR->_bf = 1;
  }
  else if (bf == 0)
  {
    subRL->_bf = 0;
    parent->_bf = 0;
    subR->_bf = 0;
  }
  else
  {
    assert(false); 
  }
  }

void _Inorder(Node* root)
  {
  if (root == nullptr)
  {
    return;
  }
  _Inorder(root->_left);
  cout << root->_kv.first << " ";
  _Inorder(root->_right);
  }
  void Inorder()
  {
  _Inorder(_root);
  }

//判断是否为AVL树
bool IsAVLTree()
{
  int hight = 0; //输出型参数
  return _IsBalanced(_root, hight);
}
//检测二叉树是否平衡
bool _IsBalanced(Node* root, int& hight)
{
  if (root == nullptr) //空树是平衡二叉树
  {
  hight = 0; //空树的高度为0
  return true;
  }
  //先判断左子树
  int leftHight = 0;
  if (_IsBalanced(root->_left, leftHight) == false)
  return false;
  //再判断右子树
  int rightHight = 0;
  if (_IsBalanced(root->_right, rightHight) == false)
  return false;
  //检查该结点的平衡因子
  if (rightHight - leftHight != root->_bf)
  {
  cout << "平衡因子设置异常：" << root->_kv.first << endl;
  }
  //把左右子树的高度中的较大值+1作为当前树的高度返回给上一层
  hight = max(leftHight, rightHight) + 1;
  return abs(rightHight - leftHight) < 2; //平衡二叉树的条件
}

Node* find(const K& key)
  {
  Node* cur = _root;
  while (cur) // 一直查找到空为止
  {
    if (key < cur->_kv.first) // 小于
    {
    cur = cur->_left;
    }
    else if (key < cur->_kv.first) // 大于
    {
    cur = cur->_right;
    }
    else // 等于
    {
    return cur
    }
  }
  // 走到这里就是没找到
  return nullptr;
  }

bool Modify(const K& key, const V& value)
  {
  Node* ret = find(key);
  // 有可能不存在
  if (ret == nullptr)
  {
    return false;
  }
  ret->_kv.second = value;
  return true;
  }