【C++高阶(三)】AVL树深度剖析&模拟实现

二叉搜索树如果插入顺序是有序的
那么这棵树的查找效率将会是O(N)
所以说在实际情况下,二叉搜索很少被使用

template<class K, class V>
struct AVLTreeNode   //高度平衡二叉搜索树
{
  AVLTreeNode(const pair<K,V>& kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_kv(kv)
    ,_bf(0)
  {}
  //用三叉链,方便更新祖先的平衡因子
  AVLTreeNode<K, V>* _left;
  AVLTreeNode<K, V>* _right;
  AVLTreeNode<K, V>* _parent;
  pair<K, V> _kv; //存储的数据
  int _bf; //balance factor平衡因子
};

template<class K,class V>
struct AVLTree
{
  typedef AVLTreeNode<K, V> Node;
private:
  Node* _root;//定义一个根节点
};

bool insert(const pair<K, V>& kv)//第一步:按照二叉搜索树的方式插入值,第二步:调整平衡因子后旋转
  {
    if (_root == nullptr)//插入第一个节点时
    {
      _root = new Node(kv);
      return true;
    }
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)//找到要插入节点的位置和它的父亲
    {
      if (cur->_kv.first < kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_kv.first > kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else return false;
    }
    //走到这一步后,已经找到了位置,开空间后插入
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
      parent->_right = cur;
    else
      parent->_left = cur;
    //此时new出来的节点的parent还指向空
    cur->_parent = parent;
    //插入完成后,此时需要查看平衡因子来控制平衡
    //沿着插入的位置往上更新平衡因子 
    while (parent)//由于parent需要不断向上更新,所以要使用循环!
    {
      if (cur == parent->_right)
        parent->_bf++;
      else
        parent->_bf--;
      if (parent->_bf == 0)//不用向上更新了
        break;
      else if (parent->_bf == 1 || parent->_bf == -1)//若高度出现变化,需要往上更新
      {
        parent = parent->_parent;
        cur = cur->_parent;
      }
      else if (abs(parent->_bf) == 2)//说明parent所在的子树不平衡了,需要旋转处理
      {
        //后面再处理这个过程......
      }
    }
}

void RotateL(Node* parent)
{
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
  parent->_right = subRL;
  if (subRL)
    subRL->_parent = parent;
  Node* ppNode = parent->_parent;
  subR->_left = parent;
  parent->_parent = subR;
  if (_root == parent)
  {
    _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;
  parent->_left = subLR;
  if (subLR)
    subLR->_parent = parent;
  Node* ppNode = parent->_parent;
  subL->_right = parent;
  parent->_parent = subL;
  if (_root == parent)
  {
    _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;
  RotateL(parent->_left);
  RotateR(parent);
  subLR->_bf = 0;
  if (bf == 1)
  {
    parent->_bf = 0;
    subL->_bf = -1;
  }
  else if (bf == -1)
  {
    parent->_bf = 1;
    subL->_bf = 0;
  }
  else if (bf == 0)
  {
    parent->_bf = 0;
    subL->_bf = 0;
  }
  else assert(false);
}
void RotateRL(Node* parent)
{
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
  int bf = subRL->_bf;
  RotateR(parent->_right);
  RotateL(parent);
  subRL->_bf = 0;
  if (bf == 1)
  {
    subR->_bf = 0;
    parent->_bf = -1;
  }
  else if (bf == -1)
  {
    subR->_bf = 1;
    parent->_bf = 0;
  }
  else if (bf == 0)
  {
    parent->_bf = 0;
    subR->_bf = 0;
  }
  else assert(false);
}