【C++】手撕AVL树（上）

// 创建AVL树的结点
template<class K,class V>
struct AVLTreeNode
{
  AVLTreeNode<K, V>* _left;  // 左子树
  AVLTreeNode<K, V>* _right; // 右子树
  AVLTreeNode<K, V>* _parent;// 父亲结点
 
  pair<K, V> _kv; // 存储的键值对
  int _bf;       // 平衡因子（右子树高度 - 左子树高度）
 
  // 构造函数
  AVLTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
    , _bf(0)
  {}
};

public:
  // 插入函数
  bool Insert(const pair<K, V>& kv)
  {
    // 如果AVL树是空树，把插入节点直接作为根节点
    if (_root == nullptr)
    {
      _root = new Node(kv);
      _root->_bf = 0;
      return true;
    }
 
    // 1.按照二叉搜索树的规则插入
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
      if (cur->_kv.first < kv.first) // 待插入节点的key值大于当前节点的key值
      {
        // 往右子树走
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_kv.first > kv.first) // 待插入节点的key值小于当前节点的key值
      {
        // 往左子树走
        parent = cur; 
        cur = cur->_left;
      }
      else // 待插入节点的key值等于当前节点的key值
      {
        return false; // 插入失败，返回false
      }
    }
 
    // 2.当循环结束，说明cur找到了空的位置，那么就插入
    cur = new Node(kv); // 构造一个新节点
    if (parent->_kv.first < kv.first) // 如果新节点的key值大于当前parent节点的key值
    {
      // 就把新节点链接到parent的右边
      parent->_right = cur;
    }
    else // 如果新节点的key值小于当前parent节点的key值
    {
      // 就把新节点链接到parent的左边
      parent->_left = cur;
    }
    cur->_parent = parent; // 别忘了把新节点里面的_parent指向parent(因为我们定义的是一个三叉链)
 
    // 3.更新平衡因子,如果出现不平衡,则需要进行旋转
    while (parent) // 最远要更新到根节点去
    {
      if (cur == parent->_right) // 如果cur插在parent的右边，说明parent的右子树增高
      {
        parent->_bf++; // 那么parent的平衡因子要++
      }
      else // 如果cur插在parent的左边，说明parent的左子树增高
      {
        parent->_bf--; // 那么parent的平衡因子要--
      }
 
      // 判断是否更新结束，或者是否需要进行旋转
      if (parent->_bf == 0) // 如果parent的bf等于0，说明左右子树高度一致，就更新结束(原因是新插入的节点把parent左右子树中矮的那一边给填补了）
      {
        // 高度不变,更新结束
        break;
      }
      else if (parent->_bf == 1 || parent->_bf == -1) // 继续往上更新平衡因子(插入节点导致某一边变高了，说明parent所在的子树高度改变了)
      {
        // 子树的高度变了，就要继续往上更新祖先
        cur = cur->_parent;
        parent = parent->_parent;
      }
      else if (parent->_bf == 2 || parent->_bf == -2) // 说明插入节点导致本来高的一边又变高了，子树不平衡了，那么此时需要做旋转处理
      {
        // 旋转的四种处理方式
        // 1.左单旋
        // 2.右单旋
        // 3.左右双旋
        // 4.右左双旋
        
        // 旋转完成，跳出
        break;
      }
      else
      {
        // 如果程序走到了这里，说明在插入节点之前AVL树就存在不平衡的子树，也就是存在平衡因子 >= 2的节点
        // 所以这里加一个断言进行处理
        assert(false);
      }
    }
    // 插入成功，返回true
    return true;
  }