【高阶数据结构】AVL树（动图详解）

template<class K, class V>
struct AVLTreeNode
{
  //定义三叉链
  AVLTreeNode<K, V>* _left;
  AVLTreeNode<K, V>* _right;
  AVLTreeNode<K, V>* _parent;
  //存储的键值对
  pair<K, V> _kv;
  //平衡因子(balance factor)
  int _bf;
  //构造函数
  AVLTreeNode(const pair<K, V>& kv)
  :_left(nullptr)
  ,_right(nullptr)
  ,_parent(nullptr)
  ,_kv(kv)
  ,_bf(0)
  {}
};

//插入
  bool Insert(const pair<K, V>& kv)
  {
  //若为空树，直接插入作为根节点
  if (_root == nullptr)
  {
    _root = new Node(kv);
    return true;
  }
  //和二叉搜索树类似，找到该插入的节点位置
  Node* parent = nullptr;
  Node* cur = _root;
  while (cur)
  {
    if (cur->_kv.first < kv.first)//插入节点值大于当前节点的key
    {
    parent = cur;
    cur = cur->_right;//往右走
    }
    else if (cur->_kv.first > kv.first)//插入节点值小于当前节点的key
    {
    parent = cur;
    cur = cur->_left;//往左走
    }
    else
    {
    //插入的节点key值等于当前位置的key值，插入失败
    return false;
    }
  }
  //开始插入
  cur = new Node(kv);
  if (parent->_kv.first < kv.first)
  {
    parent->_right = cur;
  }
  else if (parent->_kv.first < kv.first)
  {
    parent->_left = cur;
  }
  //连接parent
  cur->_parent = parent;
  //控制平衡
  //1、更新平衡因子
  while (parent)
  {
    if (cur == parent->right)
    {
    parent->_bf++;
    }
    else
    {
    parent->_bf--;
    }
    if (parent->_bf == -1 || parent->_bf == 1)//也可以用abs
    {
    cur = parent;
    parent = parent->_parent;
    }
    else if (parent->_bf == 0)
    {
    break;
    }
    else if (parent->_bf == -2 || parent->_bf == 2)
    {
    //说明parent所在的子树已经不平衡了，需要旋转
    if (parent->_bf == 2 && cur->_bf == 1)
    {
      RotateL(parent);//左单旋
    }
    else if (parent->_bf == -2 && cur->_bf == -1)
    {
      RotateR(parent);//右单旋
    }
    else if (parent->_bf == -2 && cur->_bf == 1)
    {
      RotateLR(parent);//左右双旋
    }
    break;
    }
    else
    {
    assert(false);//在插入前树的平衡因子就有问题
    }
  }
  return true;
  }

void RotateL(Node* parent)
  {
     //三叉链
  Node* subR = parent->_right;
  Node* subLR = subR->_left;
  Node* ppNode = parent->_parent;
  //subR 和 parent之间的关系
  subR->_left = parent;
  parent->_parent = subR;
  //subRL 和 parent之间的关系
  subRL = parent->_right;
  if (subRL)
    subRL->parent = parent;
  //ppNode 和 subR的关系
  if (ppNode == nullptr)
  {
    _root = subR;
    subR->_parent = nullptr;//没有父节点，所以为空
  }
  else
  {
    if (ppNode->_left == parent)
    {
    ppNode->_left = subR;
    }
    else
    {
    ppNode->_right = subR;
    }
    subR->_parent = ppNode;
  }
  //更新平衡因子
  subR->_bf = parent->_bf = 0;
  }

//右单旋
void RotateR(Node* parent)
{
  Node* subL = parent->_left;
  Node* subLR = subL->_right;
  Node* ppNode = parent->_parent;
  //subL 和 parent的关系
  subL->_right = parent;
  parent->_parent = subL;
  //subLR 和 parent之间的关系
  parent->_left = subLR;
  if (subLR)
  subLR->_parent = parent;
  //ppNode 和 subL的关系
  if (ppNode == nullptr)
  {
  _root = subL;
  subL->_parent = nullptr;
  }
  else
  {
  if (ppNode->_left == parent)
  {
    ppNode->_left == subL;
  }
  else
  {
    ppNode->_right == subL;
  }
  subL->_parent = ppNode;
  }
  //更新平衡因子
  subL->_bf = parent->_bf = 0;
}

void RotateLR(Node* parent)
  {
  Node* subL = parent->_left;
  Node* subLR = subL->_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;
    subR->_bf = 0;
    parent->_bf = -1;
  }
  else if (bf == -1)
  {
    subRL->_bf = 0;
    subR->_bf = 1;
    parent->_bf = 0;
  }
  else if (bf == 0)
  {
    subRL->_bf = 0;
    subR->_bf = 0;
    parent->_bf = 0;
  }
  else
  {
    assert(false);
  }
  }

void _InOrder(Node* root)
  {
  if (root == nullptr)
  {
    return;
  _InOrder(root->_left);
  cout << root->_kv.first << ":" << root->_kv.second << endl;
  _InOrder(root->_right);
  }

//是否平衡
  bool IsBalance(Node* root)
  {
  if (root == nullptr)
  {
    return true;
  }
  int leftHT = Height(root->_left);
  int rightHT = Height(root->_right);
  int diff = rightHT - leftHT;
  if (diff ！ = root->_bf)
  {
    cout << root->_kv.first << "平衡因子异常" << endl;
    return false;
  }
  //小于2就为真 并且递归调用子树判断是否平衡
  return abs(diff) < 2
    && _IsBalance(root->_left)
    && _IsBalance(root->_right);
  }
  //后序查找
  int Height(Node* root)
  {
  if (root == nullptr)
    return 0;
  int leftHT = Height(root->_left);
  int rightHT = Height(root->_right);
  return max(leftHT, rightHT) + 1;
  }