【数据结构与算法】AVL树的插入与删除实现详解

前言

​ 之前对 map / multimap / set / multiset 进行了简单的介绍，在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成 O(N)，因此 map、set 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

​ 注意：因为 map 和 set 主要是用红黑树进行封装，所以这里的 AVL 树我们主要是实现它的 插入 和 删除 和 operator[] （因为 insert 就是为了 operator[] 而存在的，还记得我们在二叉树进阶讲的吗？），所以我们这里不会去是实现 AVL 树的拷贝构造和赋值重载，这方面涉及到深拷贝，我们一并到红黑树才讲！

Ⅰ. AVL树的定义

​ 二叉搜索树虽可以缩短查找的效率，但 如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过 1( 需要对树中的结点进行调整 )，即可降低树的高度，从而减少平均搜索长度。

​ 一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：

• 左右子树都是 AVL 树

• 左右子树高度之差 ( 简称 平衡因子) 的绝对值不超过 1

​ 如果一棵二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 $lo{g}_{2}n$，搜索时间复杂度 O($lo{g}_{2}n$)。

Ⅱ. AVL树节点的定义

​ 对于 AVL 树节点的定义，其实有很多个版本，各有优势，这里用的是三叉链的结构，这是为了方便后面的一些操作，但是也是有弊端的比如说在链接的时候要把三条链都考虑进去，但是三叉链的优势是利大于弊，所以这里采用三叉链！

​ 而至于 AVL 树的一些特点，比如说调整树的高度，那么我们就得知道该节点的 平衡因子(balance factor)，所以这里我们给节点里面增加一个 bf，用于存放该节点的平衡因子。

​ 注意：这里 平衡因子bf的值 等于：右子树高度 - 左子树高度

​ 根据AVL树的定义，每个节点的bf值理论上只可能有三种情况：1，0，-1。所以当bf出现其他值的时候就代表树不平衡了，需要调整了。

template <class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv; // _kv是一个键值对int _bf; // 该点的平衡因子 --> balance factorAVLTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};

Ⅲ. AVL树的插入Insert

一、节点的插入

​ AVL 树的插入和之前搜索树的插入是一样的，只不过在插入之后，我们需要做出调整，因为有可能我们插入节点后会导致二叉树的不平衡，所以我们得重新调整高度！这里就涉及到 左单旋、右单旋、左右双旋和右左双旋 四个操作。

​ AVL 树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点

2. 调整节点的平衡因子

   • 新增的节点如果在 parent 的左边，则 parent->bf--
   • 新增的节点如果在 parent 的右边，则 parent->bf++
     • 如果 parent 的平衡因子为 0，说明高度是平衡的，停止更新
     • 如果 parent 的平衡因子为 1 或者 -1，说明 parent 所在子树的高度变了，继续往上更新
     • 如果 parent 的平衡因子为 2 或者 -2，说明已经出现不平衡了，需要进行旋转调整（后面会讲如何旋转）

pair<Node*, bool> Insert(const pair<K, V>& kv)
{// 若树为空则直接开辟新节点if (_root == nullptr){_root = new Node(kv);return make_pair(_root, true);}// 先找到要插入的位置，用cur标记，而parent标记cur的上一个位置Node* cur = _root;Node* parent = _root;while (cur != nullptr){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return make_pair(cur, false);}}// 接着插入节点cur = new Node(kv);Node* newnode = cur; // 这一步是为了后面返回值返回的if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}// 调整高度while (parent != nullptr) // 这里也可写出while(cur != _root){// 1、先调节平衡因子if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}// 2、判断是否需要旋转if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){// 插入前双亲的平衡因子是0，插入后双亲的平衡因为为1 或者 -1 ，说明以双亲为根的二叉树的高度增加了一层，因此需要继续向上调整cur = parent;parent = parent->_parent;}else if(parent->_bf == 2 || parent->_bf == -2){// 需要调整高度if (parent->_bf == -2){if (cur->_bf == -1){RotateR(parent); //右单旋}else if(cur->_bf == 1){RotateLR(parent); //左右双旋}}else if (parent->_bf == 2){if (cur->_bf == 1){RotateL(parent); //左单旋}else if (cur->_bf == -1){RotateRL(parent); //右左双旋 }}// 注意这里的break很关键，因为我们调整了子树的平衡因子后，它的父亲以上的树其实就已经不会受影响了break;}else{// 插入节点之前，树已经不平衡了，或者bf出错。需要检查其他逻辑assert(false);}}return make_pair(newnode, true);
}

​ 问题：这里要注意的是 Insert 的返回值为什么是 pair？

​ 还记得我们在实现二叉搜索树的时候说到，Insert 的实现其实是为了 operator[] 而产生的，而 operator[] 需要接收到是一个键值对里面的 value，所以我们的 Insert 需要返回一个 pair，且 pair 里面第一个键值放的是迭代器，第二个值放的是 bool 值，这是为了和 STL 里面的实现保持一致！详情可查看官方文档。

二、插入的旋转

​ 如果在一棵原本是平衡的 AVL 树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL 树的旋转分为四种：

① 新节点插入较高左子树的左侧（左左）：右单旋

​ 如下图，我们在 a 树下插入新节点，此时 30 节点和 60 节点的平衡因子就变了，则需要调整。

​ 上图在插入前，AVL 树是平衡的，新节点插入到 30 的左子树（注意：此处不是左孩子）中，30 的左子树增加了一层，导致以 60 为根的二叉树不平衡，要让 60 平衡，只能将 60 左子树的高度减少一层，右子树增加一层，即将 60 的左子树往上提，这样 60 转下来，因为 60 比 30 大，只能将其放在 30 的右子树，而如果 30 有右子树，右子树根的值一定大于 30，小于 60，只能将其放在 60 的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：

1. 30 节点的右孩子可能存在，也可能不存在

2. 60 节点可能是根节点，也可能是子树

   • 如果是根节点，旋转完成后，要更新根节点

   • 如果是子树，可能是某个节点的左子树，也可能是右子树

3. 最后记得将 30 和 60 节点的平衡因子调为 0

void RotateR(Node* parent)
{// SubL: Parent的左孩子// SubLR: Parent左孩子的右孩子Node* subL = parent->_left;Node* subLR = subL->_right;// 先将parent的左子树连上subLR，注意要双向链接parent->_left = subLR;if (subLR != nullptr) // 注意要判断subLR是否为空，为空则不需要链接subLR->_parent = parent;// 让parent作为subL的右子树subL->_right = parent;Node* parent_parent = parent->_parent; // 先将parent的parent记录下来，后面链接要用到parent->_parent = subL;// 判断一下parent是否为二叉树的根节点if (parent == _root){_root = subL;_root->_parent = nullptr;}else{// 如果60是子树，可能是parent_parent的左子树，也可能是右子树if (parent_parent->_left == parent){parent_parent->_left = subL;}else{parent_parent->_right = subL;}subL->_parent = parent_parent;}// 最后记得要将平衡因子置零subL->_bf = parent->_bf = 0;
}

② 新节点插入较高右子树的右侧（右右）：左单旋

​ 实现及情况考虑可参考右单旋，与右单旋基本一致，只不过要旋转的节点不同而已！

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;// 先将parent的左子树连上subRL，注意要双向链接parent->_right = subRL;if (subRL != nullptr)subRL->_parent = parent;// 让parent作为subR的右子树subR->_left = parent;Node* parent_parent = parent->_parent;parent->_parent = subR;// 判断一下parent是否为二叉树的根节点if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (parent_parent->_left == parent){parent_parent->_left = subR;}else{parent_parent->_right = subR;}subR->_parent = parent_parent;}// 最后记得要将平衡因子置零subR->_bf = parent->_bf = 0;
}

③ 新节点插入较高左子树的右侧（左右）：先左单旋再右单旋

​ 将双旋变成单旋后再旋转，即：先对 30 进行左单旋，然后再对 90 进行右单旋，旋转完成后再考虑平衡因子的更新。

​ 而这里双旋后平衡因子更新的情况比较多，我们一一列举出来：

可以看出来，三种情况可以根据 60 这个节点来进行区分：

• 当 60 这个节点的 bf 为 0：旋转后该子树的节点的平衡因子都为 0
• 当 60 这个节点的 bf 为 1：也就是在右子树插入了新节点，则最后 subL->bf = -1，其他都为 0
• 当 60 这个节点的 bf 为 -1：也就是在左子树插入了新节点，则最后 parent->bf = 1，其他都为 0

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;// 旋转之前，保存subLR的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节点的平衡因子int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else{assert(false);}
}

④ 新节点插入较高右子树的左侧（右左）：先右单旋再左单旋

​ 大体与左右双旋一致，具体参考左右双旋。这里只画出其中一种情况，剩下的两种自主分析。

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;// 旋转之前，保存subRL的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节点的平衡因子int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);// 平衡因子的调节与左右双旋不太一样，具体自己分析if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else{assert(false);}
}

插入后旋转的总结：

假如以 parent 为根的子树不平衡，即 parent 的平衡因子为 2 或者 -2，分以下情况考虑：

1. parent 的平衡因子为 2，说明 parent 的右子树高，设 parent 的右子树的根为 subR

   • 当 subR 的平衡因子为 1 时，执行左单旋

   • 当 subR 的平衡因子为 -1 时，执行右左双旋

2. parent 的平衡因子为 -2，说明 parent 的左子树高，设 parent 的左子树的根为 subL

   • 当 subL 的平衡因子为 -1 是，执行右单旋

   • 当 subL 的平衡因子为 1 时，执行左右双旋

旋转完成后，原 parent 为根的子树个高度降低，已经平衡，不需要再向上更新。

Ⅳ. AVL树的验证

AVL 树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证 AVL 树，可以分两步：

1. 验证其为二叉搜索树

   • 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

2. 验证其为平衡树

   • 每个节点子树高度差的绝对值不超过 1（注意节点中如果没有平衡因子）
   • 节点的平衡因子是否计算正确

int Height(Node* root)
{if (root == nullptr)return 0;int leftH = Height(root->_left);int rightH = Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;
}bool IsBalanceTree(Node* root)
{if (root == nullptr)return true;int leftH = Height(root->_left);int rightH = Height(root->_right);// 检查一下平衡因子是否正确 (右平衡因子 - 左平衡因子)if (rightH - leftH != root->_bf){cout << "平衡因子异常:" << root->_kv.first << endl;return false;}if (abs(rightH - leftH) > 2)return false;return IsBalanceTree(root->_left) && IsBalanceTree(root->_right);
}// 这个是调用验证AVL树的主函数
bool IsAVLTree()
{return IsBalanceTree(_root);
}

验证用例

结合上述代码按照以下的数据次序，自己动手画 AVL 树的创建过程，验证代码是否有漏洞。

​ 常规场景1：{16, 3, 7, 11, 9, 26, 18, 14, 15}

​ 特殊场景2：{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}

Ⅴ. AVL树的删除Erase

一、节点的删除

​ 因为 AVL 树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与插入不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

​ AVL 树删除节点的过程是，先找到该节点，然后进行删除。由于删除节点的位置不同，导致删除后节点进行移动的方式不同。删除节点的位置分为以下 4 类：

1. 删除叶子结点。操作：直接删除，然后依次向上调整为 AVL 树。

   

   这里叶子节点还有两种比较特殊的情况：

   

2. 删除非叶子节点，该节点只有左孩子。操作：该节点的值替换为左孩子节点的值，然后删除左孩子节点。

   • 为什么左孩子节点为叶子节点，因为删除节点前，该树是 AVL 树，由 AVL 树的定义知，每个节点的左右子树的高度差的绝对值 <=1，由于该节点只有左孩子，没有右孩子，如果左孩子还有子节点，那么将不满足每个节点的左右子树的高度差的绝对值 <=1，所以左孩子节点为叶子结点。

     

     

3. 删除非叶子节点，该节点只有右孩子。操作：该节点的值替换为右孩子节点的值，然后删除右孩子节点。

   • 【右孩子节点为叶子结点，所以删除右孩子节点的情况为第1种情况。】

   • 【为什么右孩子节点为叶子节点？答案和第二种情况一样】
     

     

4. 删除非叶子节点，该节点既有左孩子，又有右孩子。操作：该节点的值替换为该节点的前驱节点（或者后继节点），然后删除前驱节点（或者后继节点）。

   • 前驱结点：在中序遍历中，一个节点的前驱结点，先找到该节点的左孩子节点，再找左孩子节点的最后一个右孩子节点。向左走一步，然后向右走到头。最后一个右孩子节点即为前驱节点

   • 后继节点： 在中序遍历中，一个节点的后继结点，先找到该节点的右孩子节点，再找右孩子节点的最后一个左孩子节点。向右走一步，然后向左走到头。最后一个左孩子节点即为前驱节点

这里我们选择的是后继节点！说的简单一点就是右子树的最小节点！

总结：对于非叶子节点的删除，最终都将转化为对叶子节点的删除。

// 删除的情况：
// 1.删除的节点为叶子节点，直接删除，修改父节点的bf并从该节点的父节点向上调整
//  下面两种情况由于删除之前就是AVL树，又因为有一个子树为空，所以另一个子树（非空）一定只包含一个节点！，搞清楚这点很重要，这种节点一定是叶子节点的上一层！！！！这里虽然是删除该节点实际上删除的是他的唯一一个非空节点
// 2.删除的节点左子树为空，右子树非空： 相当于删除左子树，修改该节点的bf并向上调整
// 3.删除的节点右子树为空，左子树非空： 相当于删除右子树，修改该节点的bf并向上调整
// 4.左右子树都不为空，用替换删除法，找右子树的最小节点（最左边节点，这个节点左子树一定为空）实际上就转化成了上面三种情况// bf调整原则：
// 1. 删左节点，父节点的bf++
// 2. 删右节点，父节点的bf--
// 3. bf为0继续向上调整，bf为1或-1停止向上调整
// 4. cur->bf为2的时候情况就与插入不同了，插入的时候调整的是插入的节点所在cur的半边子树，而删除要调整的是删除节点对面那一半进行旋转（这点很重要！！！，我在这上面卡了半天），旋转的操作与插入相同
bool Erase(const K& key)
{// 开头检查一下是否是空树if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur != nullptr){if (cur->_kv.first > key){parent = cur;cur = cur->_left;}else if (cur->_kv.first < key){parent = cur;cur = cur->_right;}else{// 找到了该节点，准备删除// 1、左右都为空或者其中一个为空if (cur->_left == nullptr || cur->_right == nullptr){// 删除的节点就是根节点话，则先判断是否有左右子树然后在deleteif (_root == cur){if (cur->_left == nullptr)_root = _root->_right;else_root = _root->_left;delete cur;// 平衡因子调节，注意要加这个判断，否则当左右子树不存在的时候，_root是nullptr，修改bf会报错if(_root != nullptr)_root->_bf = 0;}else if (cur->_left == nullptr && cur->_right == nullptr) // 左右子树均为空{if (parent->_left == cur){parent->_left = nullptr;parent->_bf++;}else{parent->_right = nullptr;parent->_bf--;}delete cur;// 调节高度Erase_rotate(parent);}else if (cur->_left == nullptr && cur->_right != nullptr) // 左为空右不为空{// 用右节点来代替作为删除的节点cur->_kv = cur->_right->_kv;delete cur->_right;cur->_right = nullptr;// 调节高度cur->_bf--;Erase_rotate(cur);}else if (cur->_left != nullptr && cur->_right == nullptr) // 右为空左为空{// 用左节点来代替作为删除的节点cur->_kv = cur->_left->_kv;delete cur->_left;cur->_left = nullptr;// 调节高度cur->_bf++;Erase_rotate(cur);}}else // 2、左右都不为空{// 找到右子树中的最小值与cur节点的值进行替换// 找右子树最小节点,也就是右子树的最左边的节点，这个节点：左子树一定为nullptr，右子树未知Node* minRight = cur->_right;Node* minParent = cur;while (minRight->_left != nullptr){minParent = minRight;minRight = minRight->_left;}cur->_kv = minRight->_kv;// 现在要搞清楚等效删除的是哪个节点，以及从哪个节点开始向上检查！// 将删除节点转化为上面左右都为空或者其中一个为空的情况解决if (cur == minParent){// 相当于删除的是minRight->_right，改变minRight的bf，并从minRight节点向上检查if (minRight->_right != nullptr) {minRight->_kv = minRight->_right->_kv;delete minRight->_right;minRight->_right = nullptr;minRight->_bf++;Erase_rotate(minRight);}// 相当于删除的是minRight节点，改变minParent的bf，并从minParent向上检查else{minParent->_right = nullptr;delete minRight;minParent->_bf--;Erase_rotate(minParent);}}else{// 相当于删除的是minRight->_right，改变minRight的bf，并从minRight节点向上检查if (minRight->_right != nullptr){// 左子树为空右子树不为空minRight->_kv = minRight->_right->_kv;delete minRight->_right;minRight->_right = nullptr;minRight->_bf++;Erase_rotate(minRight);}//相当于删除的是minRight，改变minParent的bf，并从minParent向上检查else{// 左右子树 均为空的删除情况minParent->_left= nullptr;delete minRight;minParent->_bf++;Erase_rotate(minParent);}}}return true;}}return false;
}

二、删除的旋转

bf 调整原则：

1. 删左节点，父节点的 bf++
2. 删右节点，父节点的 bf--
3. bf 为 0 继续向上调整，bf 为 1 或 -1 停止向上调整（与插入正好反过来）
4. cur->bf 为 2 的时候情况就与插入不同了，插入的时候调整的是插入的节点所在的半边子树，而删除要调整的是删除节点对面那一半进行旋转（这点很重要！！！），也就是如果 cur 节点的 bf 为 2，意味着右边高删除的节点一定在 cur 的左子树，接下来要调整右子树

🏗 与插入不同的是：删除左右单旋各自会出现一种新的情况，这种情况是插入中不可能发生的（也就是上面删除叶子节点的两种特殊情况）：

​ 由于插入的时候一定是插入的那半边子树高，所以插入的时候只能在 B 的左右一个子树插入，所以 B 树的平衡因子不可能为 0，而删除就不同了删除节点影响的是另一半边子树，旋转的也是另一半边子树（上面删除的地方一定是是高度为h的那颗子树），所以这种情况就出现了，这种情况依然是按照左单旋和右单旋处理。旋转完成之后记得要调整整个树的 bf 值。

// bf调整原则：
// 1. 删左节点，父节点的bf++
// 2. 删右节点，父节点的bf--
// 3. bf为0继续向上调整，bf为1或-1停止向上调整
// 4. cur->bf为2的时候情况就与插入不同了，插入的时候调整的是插入的节点所在cur的半边子树，而删除要调整的是删除节点对面那一	   半进行旋转（这点很重要！！！）
//   旋转的操作与插入相同
void Erase_rotate(Node* cur) // 删除节点的操作函数 传入的是已经修改过bf的删除节点的父节点
{Node* prev = nullptr;while (cur != nullptr){if (cur->_bf == 1 || cur->_bf == -1){break;}else if (cur->_bf == 0){prev = cur;cur = cur->_parent;}else if (cur->_bf == 2 || cur->_bf == -2){if (cur->_bf == 2){if (cur->_right->_bf == 0) // 这种情况是插入没有的，这里要特殊处理一下{RotateL(cur);cur->_parent->_bf = -1;cur->_bf = 1;break;		// 由于旋转完的树的bf的值为-1，所以不用继续循环}else if (cur->_right->_bf == 1) //左单旋{RotateL(cur);// 下面这两步置零其实可以不用写，因为在左旋的实现里面已经置零了// cur->_parent->_bf = 0;// cur->_bf = 0;prev = cur->_parent;cur = prev->_parent;continue;}else if (cur->_right->_bf == -1) //先来一个右单旋 再来一个左单旋{RotateRL(cur);prev = cur->_parent;cur = prev->_parent;continue;}}else if(cur->_bf == -2){if (cur->_left->_bf == 0) // 这种情况是插入没有的，这里要特殊处理一下{RotateR(cur);cur->_bf = -1;cur->_parent->_bf = 1;break;}else if (cur->_left->_bf == -1) //右单旋{RotateR(cur);prev = cur->_parent;cur = prev->_parent;continue;}else if (cur->_left->_bf == 1) // 先来一个左单旋 再来一个右单旋{RotateRL(cur);prev = cur->_parent;cur = prev->_parent;continue;}}}else{assert(false);}// 更新平衡因子if (cur && cur->_left == prev)cur->_bf++;else if (cur && cur->_right == prev)cur->_bf--;}
}

Ⅵ. AVL树的性能

​ AVL 树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过 1，这样可以保证查询时高效的 时间复杂度，即 O($lo{g}_{2}n$)。但是如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。

​ 因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑 AVL 树，但一个结构经常修改，就不太适合。

Ⅶ. AVL树的整体框架

​ 前言中说到，我们这里不实现 AVL 树的拷贝构造以及赋值重载，但是我们这里会实现一下 operator[]，毕竟 insert 函数的出现就是为了它的！

​ 🏗 operator[] 的实现代码：

V& operator[](const K& key)
{pair<Node*, bool> res = Insert(make_pair(key, V()));return res.first->_kv.second;
}

​ 测试代码：

#include "AVLTree.h"void TestTree1()
{AVLTree<int, int> t;int arr[] = { 3,10,1,2,9,4,5,6,7 };//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : arr){t.Insert(make_pair(e, 1));}t.Inorder();cout << t.IsAVLTree() << endl;t[3] *= 102;t[1] *= 10;t[2] *= 10;t.Inorder();t.Erase(3);t.Inorder();cout << t.IsAVLTree() << endl;t.Erase(1);t.Inorder();cout << t.IsAVLTree() << endl;t.Erase(1);t.Inorder();cout << t.IsAVLTree() << endl;t.Erase(2);t.Inorder();cout << t.IsAVLTree() << endl;t.Erase(4);t.Inorder();cout << t.IsAVLTree() << endl;t.Erase(5);t.Inorder();cout << t.IsAVLTree() << endl;t.Erase(6);t.Inorder();cout << t.IsAVLTree() << endl;t.Erase(7);t.Inorder();cout << t.IsAVLTree() << endl;t.Erase(8);t.Inorder();cout << t.IsAVLTree() << endl;t.Erase(9);t.Inorder();cout << t.IsAVLTree() << endl;t.Erase(10);t.Inorder();cout << t.IsAVLTree() << endl;t.Erase(10);t.Inorder();cout << t.IsAVLTree() << endl;
}int main()
{TestTree1();return 0;
}

AVLTree.h

#pragma once
#include <iostream>
#include <string>
#include <cassert>
using namespace std;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; //该点的平衡因子 --> balance factorAVLTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};template <class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:AVLTree():_root(nullptr){}V& operator[](const K& key){pair<Node*, bool> res = Insert(make_pair(key, V()));return res.first->_kv.second;}~AVLTree(){Destory(_root);_root = nullptr;}pair<Node*, bool> Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return make_pair(_root, true);}// 先找到该节点Node* cur = _root;Node* parent = _root;while (cur != nullptr){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return make_pair(cur, false);}}// 接着插入节点cur = new Node(kv);Node* newnode = cur; // 这一步是为了后面返回值返回的if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}// 1、更新平衡因子while (parent != nullptr) // 或者while(cur != _root){if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if(parent->_bf == 2 || parent->_bf == -2){// 2、调整高度if (parent->_bf == -2){if (cur->_bf == -1){RotateR(parent); //右单旋}else if(cur->_bf == 1){RotateLR(parent); //左右双旋}}else if (parent->_bf == 2){if (cur->_bf == 1){RotateL(parent); //左单旋}else if (cur->_bf == -1){RotateRL(parent); //右左双旋 }}// 注意这里的break很关键，因为我们调整了子树的平衡因子后，它的父亲其实就已经不会有影响了break;}else{// 插入节点之前，树已经不平衡了，或者bf出错。需要检查其他逻辑assert(false);}}return make_pair(newnode, true);}void RotateR(Node* parent){// SubL: Parent的左孩子// SubLR: Parent左孩子的右孩子Node* subL = parent->_left;Node* subLR = subL->_right;// 先将parent的左子树连上subLR，注意要双向链接parent->_left = subLR;if (subLR != nullptr)subLR->_parent = parent;// 让parent作为subL的右子树subL->_right = parent;Node* parent_parent = parent->_parent; // 先将parent的parent记录下来，后面链接要用到parent->_parent = subL;// 判断一下parent是否为二叉树的根节点if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (parent_parent->_left == parent){parent_parent->_left = subL;}else{parent_parent->_right = subL;}subL->_parent = parent_parent;}// 最后记得要将平衡因子置零subL->_bf = parent->_bf = 0;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL != nullptr)subRL->_parent = parent;subR->_left = parent;Node* parent_parent = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (parent_parent->_left == parent){parent_parent->_left = subR;}else{parent_parent->_right = subR;}subR->_parent = parent_parent;}// 最后记得要将平衡因子置零subR->_bf = parent->_bf = 0;}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;// 旋转之前，保存subLR的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节点的平衡因子int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_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);if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else{assert(false);}}Node* Find(const K& key){Node* cur = _root;while (cur != nullptr){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool Erase(const K& key){if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur != nullptr){if (cur->_kv.first > key){parent = cur;cur = cur->_left;}else if (cur->_kv.first < key){parent = cur;cur = cur->_right;}else{// 找到了该节点，准备删除// 1、左右都为空或者其中一个为空if (cur->_left == nullptr || cur->_right == nullptr){if (_root == cur){if (cur->_left == nullptr)_root = _root->_right;else_root = _root->_left;delete cur;// 平衡因子调节if(_root != nullptr)_root->_bf = 0;}else if (cur->_left == nullptr && cur->_right == nullptr){if (parent->_left == cur){parent->_left = nullptr;parent->_bf++;}else{parent->_right = nullptr;parent->_bf--;}delete cur;// 调节高度Erase_rotate(parent);}else if (cur->_left == nullptr && cur->_right != nullptr){cur->_kv = cur->_right->_kv;delete cur->_right;cur->_right = nullptr;// 调节高度cur->_bf--;Erase_rotate(cur);}else if (cur->_left != nullptr && cur->_right == nullptr){cur->_kv = cur->_left->_kv;delete cur->_left;cur->_left = nullptr;// 调节高度cur->_bf++;Erase_rotate(cur);}}else // 2、左右都不为空{Node* minRight = cur->_right;Node* minParent = cur;while (minRight->_left != nullptr){minParent = minRight;minRight = minRight->_left;}cur->_kv = minRight->_kv;// 将删除节点转化为上面左右都为空或者其中一个为空的情况解决if (cur == minParent){if (minRight->_right != nullptr){minRight->_kv = minRight->_right->_kv;delete minRight->_right;minRight->_right = nullptr;minRight->_bf++;Erase_rotate(minRight);}else{minParent->_right = nullptr;delete minRight;minParent->_bf--;Erase_rotate(minParent);}}else{if (minRight->_right != nullptr){minRight->_kv = minRight->_right->_kv;delete minRight->_right;minRight->_right = nullptr;minRight->_bf++;Erase_rotate(minRight);}else{minParent->_left= nullptr;delete minRight;minParent->_bf++;Erase_rotate(minParent);}}}return true;}}return false;}void Erase_rotate(Node* cur){Node* prev = nullptr;while (cur != nullptr){if (cur->_bf == 1 || cur->_bf == -1){break;}else if (cur->_bf == 0){prev = cur;cur = cur->_parent;}else if (cur->_bf == 2 || cur->_bf == -2){if (cur->_bf == 2){if (cur->_right->_bf == 0) // 这种情况是插入没有的，这里要特殊处理一下{RotateL(cur);cur->_parent->_bf = -1;cur->_bf = 1;break;		// 由于旋转完的树的bf的值为-1，所以不用继续循环}else if (cur->_right->_bf == 1){RotateL(cur);// 下面这两步置零其实可以不用写，因为在左旋的实现里面已经置零了// cur->_parent->_bf = 0;// cur->_bf = 0;prev = cur->_parent;cur = prev->_parent;continue;}else if (cur->_right->_bf == -1){RotateRL(cur);prev = cur->_parent;cur = prev->_parent;continue;}}else if(cur->_bf == -2){if (cur->_left->_bf == 0) // 这种情况是插入没有的，这里要特殊处理一下{RotateR(cur);cur->_bf = -1;cur->_parent->_bf = 1;break;}else if (cur->_left->_bf == -1){RotateR(cur);prev = cur->_parent;cur = prev->_parent;continue;}else if (cur->_left->_bf == 1){RotateRL(cur);prev = cur->_parent;cur = prev->_parent;continue;}}}else{assert(false);}// 更新平衡因子if (cur && cur->_left == prev)cur->_bf++;else if (cur && cur->_right == prev)cur->_bf--;}}bool IsAVLTree(){return IsBalanceTree(_root);}void Inorder(){_Inorder(_root);cout << endl;}
private:void Destory(Node* root){if (root == nullptr)return;Destory(root->_left);Destory(root->_right);delete root;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_Inorder(root->_right);}int Height(Node* root){if (root == nullptr)return 0;int leftH = Height(root->_left);int rightH = Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;}bool IsBalanceTree(Node* root){if (root == nullptr)return true;int leftH = Height(root->_left);int rightH = Height(root->_right);// 检查一下平衡因子是否正确 (右平衡因子 - 左平衡因子)if (rightH - leftH != root->_bf){cout << "平衡因子异常:" << root->_kv.first << endl;return false;}if (abs(rightH - leftH) > 2)return false;return IsBalanceTree(root->_left) && IsBalanceTree(root->_right);}Node* _root;
};