插入操作
// 插入操作
bool insert(const pair<K, V>& kv)
{// 若树为空，直接构造，new一个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->_kv.first;}// 插入值小于当前节点值，向左移动else if (cur->_kv.first > kv.first) {parent = cur;cur = cur->_left;}// 插入值等于当前节点值，去重else {return false;}}// 跳出循环后，cur指向空，创建新节点cur = new Node(kv);// 根据父节点的值决定新节点是父节点的左子节点还是右子节点if (parent->_kv.first < kv.first) {parent->_right = cur;}else {parent->_left = cur;}// 设置新节点的父节点cur->_parent = parent;// 控制平衡while (parent) {// 右加左减 if (cur == parent->_left) {parent->_bf--;}else {parent->_bf++;}// 平衡因子为0，说明子树平衡，跳出循环if (parent->_bf == 0) {break;}// 平衡因子为1或-1，说明子树仍平衡，继续向上更新else if (parent->_bf == 1 || parent->_bf == -1) {// 继续更新cur = parent;parent = parent->_parent;}// 平衡因子为2或-2，说明子树不平衡，需要旋转else if (parent->_bf == 2 || parent->_bf == -2) {// 根据节点的平衡因子决定旋转类型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){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}}else {assert(false);}}return true;
}
1. 函数功能概述：这个函数的主要功能是向树中插入一个新的键值对 kv ，并且在插入后通过旋转操作来维护树的平衡。
2. 树为空的情况：
- if (_root == nullptr) ：检查树是否为空。如果为空，创建一个新的节点并将其设置为根节点，然后返回 true ，表示插入成功。
3. 查找插入位置：
- 使用 while (cur) 循环来遍历树，根据当前节点的值与插入值的大小关系，决定是向左还是向右移动。
- 如果插入值等于当前节点的值，返回 false ，表示插入失败（去重操作）。
4. 插入新节点：
- 循环结束后， cur 指向空，创建一个新的节点并将其插入到合适的位置（作为父节点的左子节点或右子节点），并设置新节点的父节点。
5. 维护树的平衡：
- 使用 while (parent) 循环向上更新节点的平衡因子。
- 根据新节点是父节点的左子节点还是右子节点，更新父节点的平衡因子。
- 如果平衡因子为0，说明子树平衡，跳出循环。
- 如果平衡因子为1或-1，继续向上更新。
- 如果平衡因子为2或-2，根据节点的平衡因子决定进行哪种旋转操作（左旋 RotateL 、右旋 RotateR 、先左后右双旋 RotateRL 、先右后左双旋 RotateLR ）。
6. 返回值：最后返回 true ，表示插入操作成功。
这段代码主要实现了在平衡二叉树（如AVL树）中插入节点并维护树的平衡的功能。不过，代码中存在一些小错误，例如 cur = cur->_kv.first 这一行应该是 cur = cur->_right ，可能是笔误。同时，代码中使用的 RotateL 、 RotateR 、 RotateRL 和 RotateLR 函数的具体实现也需要根据实际情况进行补充。
//左转void RotateL(Node* parent) {Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root) {_root = cur;cur->_parent = nullptr;}else {if (ppnode->_left == parent) {ppnode->_left = cur;}else {ppnode->_parent= cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}以下是对这段代码 RotateL （左旋操作）的详细解析：
1. 函数声明：
void RotateL(Node* parent)
这是一个名为 RotateL 的函数，它接受一个指向 Node 类型的指针 parent 作为参数，函数的返回值类型为 void ，即不返回任何值。 parent 表示要进行左旋操作的节点。
1. 变量定义：
Node* cur = parent->_right; Node* curleft = cur->_left;
定义了两个指针变量 cur 和 curleft 。 cur 指向 parent 的右子节点， curleft 指向 cur 的左子节点。这里的操作是为左旋操作做准备，获取相关节点的指针以便后续调整指针指向。
1. 调整 parent 的右子节点：
parent->_right = curleft; if (curleft) {curleft->_parent = parent; }
将 parent 的右子节点设置为 curleft 。如果 curleft 不为空（即 cur 原本有左子节点），则将 curleft 的父节点设置为 parent 。这一步是为了重新连接 parent 和 curleft 之间的父子关系。
1. 调整 cur 的左子节点：
cur->_left = parent;
将 cur 的左子节点设置为 parent ，这是左旋操作中改变指针指向的关键步骤之一，使得 parent 成为 cur 的左子节点。
1. 处理 parent 的父节点：
Node* ppnode = parent->_parent; parent->_parent = cur;
定义了一个指针 ppnode 指向 parent 的父节点。然后将 parent 的父节点设置为 cur ，这一步是为了更新 parent 的父节点信息，使其指向 cur 。
1. 处理根节点情况：
if (parent == _root) {_root = cur;cur->_parent = nullptr; }
如果 parent 是根节点（即 parent 是整个树的根），则将根节点 _root 指向 cur ，并将 cur 的父节点设置为 nullptr ，这是因为 cur 成为了新的根节点，它没有父节点。
1. 处理非根节点情况：
else {if (ppnode->_left == parent) {ppnode->_left = cur;}else {ppnode->_parent= cur;}cur->_parent = ppnode; }
如果 parent 不是根节点，则根据 parent 是 ppnode 的左子节点还是右子节点，相应地将 ppnode 的左子节点或右子节点设置为 cur 。最后将 cur 的父节点设置为 ppnode ，确保 cur 与 ppnode 之间的父子关系正确。
1. 设置平衡因子：
parent->_bf = cur->_bf = 0;
将 parent 和 cur 的平衡因子 _bf 都设置为 0，这是在左旋操作完成后对平衡因子的更新，因为左旋操作可能会影响节点的平衡状态，这里简单地将它们的平衡因子设为 0，具体的平衡因子计算可能需要根据树的其他信息进一步处理。
//右转void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left= curright;if (curright){curright->_parent = parent;}cur->_right= parent;Node* ppnode = parent->_parent;cur->_right = parent;if (ppnode==nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right= cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}以下是对这段 RotateR （右转操作）代码的详细解析：
1. 函数声明：
void RotateR(Node* parent)
这是一个名为 RotateR 的函数，接收一个指向 Node 类型的指针 parent 作为参数，函数返回值类型为 void ，即不返回任何值。 parent 表示要进行右转操作的节点。
1. 变量定义：
Node* cur = parent->_left; Node* curright = cur->_right;
定义了两个指针变量 cur 和 curright 。 cur 指向 parent 的左子节点， curright 指向 cur 的右子节点。这是为右转操作做准备，获取相关节点的指针以便后续调整指针指向。
1. 调整 parent 的左子节点：
parent->_left = curright; if (curright) {curright->_parent = parent; }
将 parent 的左子节点设置为 curright 。如果 curright 不为空（即 cur 原本有右子节点），则将 curright 的父节点设置为 parent 。这一步是为了重新连接 parent 和 curright 之间的父子关系。
1. 调整 cur 的右子节点：
cur->_right = parent;
将 cur 的右子节点设置为 parent ，这是右转操作中改变指针指向的关键步骤之一，使得 parent 成为 cur 的右子节点。
1. 处理 parent 的父节点：
Node* ppnode = parent->_parent;
定义了一个指针 ppnode 指向 parent 的父节点。
1. 处理根节点情况：
if (ppnode == nullptr) {_root = cur;cur->_parent = nullptr; }
如果 ppnode 为空（即 parent 原本是根节点），则将根节点 _root 指向 cur ，并将 cur 的父节点设置为 nullptr ，因为 cur 成为了新的根节点，它没有父节点。
1. 处理非根节点情况：
else {if (ppnode->_left == parent) {ppnode->_left = cur;}else {ppnode->_right = cur;}cur->_parent = ppnode; }
如果 ppnode 不为空（即 parent 不是根节点），根据 parent 是 ppnode 的左子节点还是右子节点，相应地将 ppnode 的左子节点或右子节点设置为 cur 。最后将 cur 的父节点设置为 ppnode ，确保 cur 与 ppnode 之间的父子关系正确。
1. 设置平衡因子：
parent->_bf = cur->_bf = 0;
将 parent 和 cur 的平衡因子 _bf 都设置为 0，这是在右转操作完成后对平衡因子的更新，因为右转操作可能会影响节点的平衡状态，这里简单地将它们的平衡因子设为 0，具体的平衡因子计算可能需要根据树的其他信息进一步处理。
//右左双旋void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1){cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1;}else if (bf == -1){cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}else{assert(false);}}以下是对 RotateRL 函数（右左双旋操作）的详细解析：
1. 函数声明：
void RotateRL(Node* parent)
这是一个名为 RotateRL 的函数，接受一个指向 Node 类型的指针 parent 作为参数，函数的返回值类型为 void ，即不返回任何值。 parent 表示要进行右左双旋操作的节点。
1. 变量定义：
Node* cur = parent->_right;
Node* curleft = cur->_left;
int bf = curleft->_bf;
定义了三个变量。 cur 指向 parent 的右子节点， curleft 指向 cur 的左子节点， bf 用于存储 curleft 的平衡因子 _bf 。这些操作是为后续的双旋操作获取相关节点的信息和平衡因子。
1. 第一次旋转（右旋）：
RotateR(parent->_right);
调用 RotateR 函数（右旋函数），对 parent 的右子节点进行右旋操作。右旋操作会调整树的结构，改变节点之间的指针指向。
1. 第二次旋转（左旋）：
RotateL(parent);
调用 RotateL 函数（左旋函数），对 parent 进行左旋操作。左旋操作同样会调整树的结构，改变节点之间的指针指向。经过先右旋再左旋的操作，实现了右左双旋，对树的整体结构进行了调整。
1. 更新平衡因子：
if (bf == 0) {cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0; } else if (bf == 1) {cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1; } else if (bf == -1) {cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0; } else {assert(false); }
根据之前保存的 curleft 的平衡因子 bf 的值，来更新 cur 、 curleft 和 parent 的平衡因子。
- 当 bf 为 0 时，将 cur 、 curleft 和 parent 的平衡因子都设为 0 ，表示这些节点在双旋操作后达到了平衡状态。
- 当 bf 为 1 时，将 cur 和 curleft 的平衡因子设为 0 ，将 parent 的平衡因子设为 -1 ，更新它们的平衡因子以反映双旋后的状态。
- 当 bf 为 -1 时，将 cur 的平衡因子设为 1 ， curleft 的平衡因子设为 0 ， parent 的平衡因子设为 0 ，调整它们的平衡因子。
- 如果 bf 不是上述的 0 、 1 、 -1 这几种情况，通过 assert(false) 来触发断言，通常意味着出现了异常情况，因为正常情况下平衡因子应该是这几个值之一。
//左右双旋void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1){cur->_bf = -1;curleft->_bf = 0;parent->_bf = 0;}else if (bf == -1){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 1;}else{assert(false);}}以下是对 RotateLR 函数（左右双旋操作）的详细解析：
1. 函数声明：
void RotateLR(Node* parent)
该函数名为 RotateLR ，接受一个指向 Node 类型的指针 parent 作为参数，返回值类型为 void ，即不返回任何值。 parent 是要进行左右双旋操作的节点。
1. 变量定义：
Node* cur = parent->_left; Node* curright = cur->_right; int bf = curright->_bf;
定义了三个变量。 cur 指向 parent 的左子节点； curright 指向 cur 的右子节点； bf 用于存储 curright 的平衡因子 _bf 。这些操作是为后续的双旋操作获取相关节点的信息和平衡因子。
1. 第一次旋转（左旋）：
RotateL(parent->_left);
调用 RotateL 函数（左旋函数），对 parent 的左子节点进行左旋操作。左旋操作会改变树的结构，调整节点之间的指针指向。
1. 第二次旋转（右旋）：
RotateR(parent);
调用 RotateR 函数（右旋函数），对 parent 进行右旋操作。右旋操作同样会调整树的结构，改变节点之间的指针指向。先左旋再右旋的操作，实现了左右双旋，对树的整体结构进行调整。
1. 更新平衡因子：
if (bf == 0) {cur->_bf = 0;// 这里原代码应该是curright->_bf = 0，可能是笔误，按逻辑应该是这个节点的平衡因子设为0curright->_bf = 0; parent->_bf = 0; } else if (bf == 1) {cur->_bf = -1;curright->_bf = 0;parent->_bf = 0; } else if (bf == -1) {cur->_bf = 0;curright->_bf = 0;parent->_bf = 1; } else {assert(false); }
根据之前保存的 curright 的平衡因子 bf 的值，来更新 cur 、 curright 和 parent 的平衡因子：
- 当 bf 为 0 时，将 cur 、 curright 和 parent 的平衡因子都设为 0 ，表示这些节点在双旋操作后达到了平衡状态。
- 当 bf 为 1 时，将 cur 的平衡因子设为 -1 ， curright 的平衡因子设为 0 ， parent 的平衡因子设为 0 ，更新它们的平衡因子以反映双旋后的状态。
- 当 bf 为 -1 时，将 cur 的平衡因子设为 0 ， curright 的平衡因子设为 0 ， parent 的平衡因子设为 1 ，调整它们的平衡因子。
- 如果 bf 不是上述的 0 、 1 、 -1 这几种情况，通过 assert(false) 来触发断言，意味着出现了异常情况，因为正常情况下平衡因子应该是这几个值之一。
完整代码
#include<iostream>
#include<assert.h>
using namespace std;
template<class K,class V>
struct AVLTreeNode
{pair<K, V>_kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V>Node;
public://插入操作bool insert(const pair<K, V>& kv){if (_root == nullptr) //若树为空，直接构造，new一个{_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;while (cur) {if (cur->_kv .first< kv.first)//插入值大于root右移{parent = cur;cur = cur->_right;}else if (cur->_kv.first> kv.first)//插入值小于root左移{parent = cur;cur = cur->_left;}else //相等去重{return false;}}//跳空判断cur的位置cur = new Node(kv);if (parent->_kv.first < kv.first) {parent->_right = cur;}else {parent->_left = cur;}cur->_parent = parent;//...控制平衡//更新平衡while (parent) {//右加左减 if (cur = parent->_left) {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) {//子树不平衡，需要旋转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){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}}else {assert(false);}}return true;}//左转void RotateL(Node* parent) {Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root) {_root = cur;cur->_parent = nullptr;}else {if (ppnode->_left == parent) {ppnode->_left = cur;}else {ppnode->_parent= cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}//右转void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left= curright;if (curright){curright->_parent = parent;}cur->_right= parent;Node* ppnode = parent->_parent;cur->_right = parent;if (ppnode==nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right= cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}//右左双旋void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1){cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1;}else if (bf == -1){cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}else{assert(false);}}//左右双旋void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1){cur->_bf = -1;curleft->_bf = 0;parent->_bf = 0;}else if (bf == -1){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 1;}else{assert(false);}}private:Node* _root=nullptr;
};
)