当前位置：首页 > news >正文

探索数据结构：AVL树的分析与实现

news 文章来源：https://blog.csdn.net/Bettysweetyaaa/article/details/141195956 2025/1/16 18:01:20

✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. AVL树的介绍

在前面我们学习二叉搜索树时知道，在数据有序或接近有序时二叉搜索树会退化为单边树，查找时相当于在单链表中查找，效率低下。

为了解决这个问题，1962 年，两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis提出了一种新方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。而这颗新的树我们平衡二叉搜索（排序）树，简称AVL树。其具有以下特点：

AVL树本质就是一颗二叉搜索树。
AVL树左右两棵子树的高度差的绝对值(平衡因子)不超过1。
AVL树的左右两棵子树也是一颗AVL树。

其中特别注意：空树也是一颗AVL树，并且由于AVL树也是二叉搜索树，所以AVL树的中序遍历是有序的。

AVL树通过特殊的构造有效的避免了二叉搜索树在数据有序或接近有序时退化为单边树的情况。这使得AVL树在查找、插入和删除操作上，能够保持较为稳定的时间复杂度，而不会因为数据的特殊分布导致性能急剧下降。

2. AVL树的功能

以下是常见的AVL树的功能：

AVL树的插入。
AVL树的查找。
AVL树的删除。

3. AVL树的结构

3.1. AVL树的节点

AVL树的节点本质与二叉搜索树的节点差不多，所以肯定有三个成员变量：左子树_left，右子树_right，键值_val，并且键值我们采用KV模型的形式。而为了后续调整我们还需一个平衡因子_bf(默认为右子树的高度-左子树的高度)以及一个父节点_parent。当然为了适配不同的类型，我们可以定义一个模版.。

template<class K,class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K, V>& val = pair<K, V>()):_kv(val),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}pair<K, V> _kv;//kv模型int _bf;//平衡因子AVLTreeNode* _left;//左子树AVLTreeNode* _right;//右子树AVLTreeNode* _parent;//指向父节点
};

3.2. AVL树

然后我们就可以通过节点来定义AVL树，并将根节点初始化为空。

template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public://...具体功能
private:Node* _root = nullptr;//根节点
};

4. AVL树的初始化与销毁

4.1. 构造函数/拷贝构造/赋值重载

首先我们直接定义一个无参的构造函数，因为我们在定义拷贝构造之后编译器就不会在生成默认的构造函数了。

AVLTree()
{}

之后我们可以利用递归来实现一个拷贝构造函数。

AVLTree(const AVLTree& t)
{_root = copy(t._root);
}
Node* copy(Node* root)
{// 如果传入的根节点为空，直接返回空指针，表示拷贝结束if (root == nullptr)return nullptr;// 为新树创建一个与原始根节点值相同的新节点Node* newnode = new Node(root->_kv);// 递归地拷贝原始根节点的左子树，并将结果赋给新节点的左指针newnode->_left = copy(root->_left);// 递归地拷贝原始根节点的右子树，并将结果赋给新节点的右指针newnode->_right = copy(root->_right);// 新节点的父节点默认为空newnode->_parent = nullptr;// 如果新节点的左子节点存在，设置其父节点为新节点if (newnode->_left){newnode->_left->_parent = newnode;}// 如果新节点的右子节点存在，设置其父节点为新节点if (newnode->_right){newnode->_right->_parent = newnode;}// 返回新树的根节点指针return newnode;
}

最后我们通过一个简单的方式实现赋值重载——通过形参调用拷贝构造出一个临时变量，然后交换this所指向的变量，这样原本this所指向的对象出了作用域就会销毁，间接实现了实现赋值重载。

AVLTree<K,V>& operator=(const AVLTree <K,V> t)
{//赋值重载this->swap(_root, t._root);return *this;
}

4.2. 析构函数

析构函数需要借助递归释放所有节点，而为了方便我们传参我们可以定义子函数来帮助我们解决。

~AVLTree()
{Destroy(_root);
}
void Destroy(Node*& root)
{if (root == nullptr){return;}//递归销毁左子树Destroy(root->_left);//递归销毁右子树Destroy(root->_right);//销毁根节点delete root;root = nullptr;
}

5. AVL树的功能实现

5.1. AVL树的旋转

我们知道AVL树左右子树的高度差绝对值要保证不超过1，也就是说AVL树的平衡因子_bf只能取-1，0，1三个值。而无论插入还是删除都可能破坏原有的结构，导致AVL树失衡。为了重新平衡AVL树，我们需要重新对其调整。

首先我们可以将AVL树被破坏的情形可以抽象成以下四种场景，其中红色字体代表该节点的平衡因子，蓝色节点代表破坏AVL树平衡的节点。

5.1.1. 右单旋

首先第一种情况就是破坏AVL树平衡的节点位于较高左子树的左侧。

对于这种情况我们需要右单旋的方式，设失衡节点为_parent，其左子树节点为subL，而左子树的右子树为subLR。其调整规则如下：

将subLR链接到parent的左边。
将parent链接到subL的右边。
将parent与subL的平衡因子置为0。

void RotateR(Node*&parent)
{// 获取父节点的左子节点Node* subL = parent->_left;// 获取父节点左子节点的右子节点Node* subLR = subL->_right;// 1.将subLR链接到parent的左边。parent->_left = subLR;// 如果父节点左子节点的右子节点存在，设置其父节点为当前父节点if (subLR){subLR->_parent = parent;}// 获取父节点的父节点Node* ppNode = parent->_parent;// 2.将parent链接到subL的右边。subL->_right = parent;//parent的父节点指向subLparent->_parent = subL;// 如果父节点存在父节点if (ppNode){// 如果父节点是其父亲节点的左子节点if (ppNode->_left == parent){// 将父节点的父亲节点的左子节点设置为当前父节点的左子节点ppNode->_left = subL;}// 如果父节点是其父亲节点的右子节点else{// 将父节点的父亲节点的右子节点设置为当前父节点的左子节点ppNode->_right = subL;}// 设置父节点左子节点的父节点为父节点的父节点subL->_parent = ppNode;}// 如果父节点为根节点else{// 将根节点设置为父节点的左子节点_root = subL;// 将父节点左子节点的父节点设置为空subL->_parent = nullptr;}//3.将parent与subL的平衡因子置为0。subL->_bf = parent->_bf = 0;//改变parent节点的指向，方便erase中的node返回parent = subL;
}

其中需要特别注意的就是：判断父节点**_parent**到底是根节点，还是某个节点的子节点。

5.1.2. 左单旋

第二种情况就是破坏AVL树平衡的节点位于较高右子树的右侧。

对于这种情况我们需要左单旋的方式，设失衡节点为_parent，其右子树节点为subR，而有右子树的左子树为subRL。其调整规则如下：

将subRL链接到parent的右边。
将parent链接到subR的左边。
将parent与subR的平衡因子置为0。

void RotateL(Node* &parent)
{// 获取父节点的右子节点Node* subR = parent->_right;// 获取父节点右子节点的左子节点Node* subRL = subR->_left;//1.将subRL链接到parent的右边。parent->_right = subRL;// 如果父节点右子节点的左子节点存在，设置其父节点为当前父节点if (subRL){subRL->_parent = parent;}// 获取父节点的父节点Node* ppNode = parent->_parent;//2.将parent链接到subR的左边。subR->_left = parent;// 设置父节点的父节点为右子节点parent->_parent = subR;// 如果父节点存在父节点if (ppNode){// 如果父节点是其父亲节点的左子节点if (ppNode->_left == parent){// 将父节点的父亲节点的左子节点设置为当前父节点的右子节点ppNode->_left = subR;}// 如果父节点是其父亲节点的右子节点else{// 将父节点的父亲节点的右子节点设置为当前父节点的右子节点ppNode->_right = subR;}// 设置父节点右子节点的父节点为父节点的父节点subR->_parent = ppNode;}// 如果父节点为根节点else{// 将根节点设置为父节点的右子节点_root = subR;// 将父节点右子节点的父节点设置为空subR->_parent = nullptr;}// 3.将parent与subR的平衡因子置为0。subR->_bf = parent->_bf = 0;//改变parent节点的指向，方便erase中的node返回parent = subR;
}

其中需要特别注意的就是：判断父节点**_parent**到底是根节点，还是某个节点的子节点。

5.1.3. 先左单旋，再右单旋

第三种情况就是破坏AVL树平衡的节点位于较高左子树的右侧。

对于这种情况我们需要先左单旋，再右单旋的方式，设失衡节点为_parent，其左子树节点为subL，而有左子树的右子树为subLR。其调整规则如下：

先对subL进行左单旋。
在对parent进行右单旋。
调整平衡因子。

但是平衡因子的调整又可以分别三种情况：

当subLR = -1时，如上图所示，调整后subL = 0，subLR = 0，parent = 1。
当subLR = 0，即h = 0时：

比如依次插入三个节点，10，5，6，如下图所示：

调整后subL = 0，subLR = 0，parent = 0。

当subLR = 1时，具体情况如下图：

调整后subL = -1，subLR = 0，parent = 0。

最后我们可以总结一下：

当subLR = 0时：调整为subLR = 0，subL = 0，parent = 0。
当subLR = -1时：调整为subLR = 0，subL = 0，parent = 1。
当subLR = 1时：调整为subLR = 0，subL = -1，parent = 0。

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//先左旋RotateL(parent->_left);//再右旋RotateR(parent);//1.情况1if (bf == 0){parent->_bf = subL->_bf = subLR->_bf = 0;}//2.情况2else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}//3.情况3else if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else{//走到这里说明AVL树有问题assert(false);}
}

5.1.4. 先右单旋，再左单旋

最后一种情况就是破坏AVL树平衡的节点位于较高右子树的左侧。

对于这种情况我们需要先右单旋，再左单旋的方式，设失衡节点为_parent，其右子树节点为subR，而有右子树的左子树为subRL。其调整规则如下：

先对subR进行右单旋。
在对parent进行左单旋。
调整平衡因子。

同理，平衡因子的调整又可以分别三种情况：

当subRL = -1时，如上图所示，调整后subR = 1，subRL = 0，parent = 0。
当subRL = 0，即h = 0时：

比如依次插入三个节点，5，10，6，如下图所示：

调整后subR = 0，subRL = 0，parent = 0。

3.当subRL = 1时，具体情况如下图：

调整后subR = 0，subRL = 0，parent = -1。

最后我们可以总结一下：

当subRL = 0时：调整为subRL = 0，subR = 0，parent = 0。
当subRL = -1时：调整为subRL = 0，subR = 1，parent = 0。
当subRL = 1时：调整为subRL = 0，subL = 0，parent = -1。

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;//先右单旋Rotate(parent->_right);Rotate(parent);//1.情况一if (bf == 0){parent->_bf = subRL->_bf = subR->_bf = 0;}//2.情况二else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}//3.情况三else if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else{//走到这里说明AVL树出错assert(false);}
}

5.2. AVL树的插入

向AVL树进行插入，首先是先找到需要插入的位置，这个逻辑与二叉搜索树类似，这里就不在赘述。找到之后对父节点的平衡因子进行更新，更新平衡因子就可以分为以下三种大的情况：

父节点平衡因子为 0，整体高度不变，不需要再向上调整平衡因子。

父节点平衡因子为1或-1，整体高度改变，需要再向上调整平衡因子。

父节点平衡因子为2或-2，平衡被破坏，需要进行旋转。

平衡被破坏同样可以分为四种情况，与旋转的方式想对应，其中蓝色为插入节点。首先第一种往较高左子树的左侧插入，此时parent = -2，subL = -1，进行右单旋。

第二种往较高右子树的右侧插入，此时parent = 2，subL = 1，进行左单旋。

第三种往较高左子树的右侧插入，此时parent = -2，subL = 1，先左旋再右旋。

第四种往较高右子树的右侧插入，先右旋再左旋，此时parent = 2，subR = -1，先右旋再左旋。

最后我们可以归纳总结出：

父节点平衡因子为 0，整体高度不变，不需要再向上调整平衡因子。
父节点平衡因子为1或-1，整体高度改变，需要再向上调整平衡因子。
父节点平衡因子为2或-2，平衡被破坏，需要进行旋转。设父节点为parent，插入方向子节点为cur。

parent = -2且cur = -1进行右单旋。
parent = 2且cur = 1进行左单旋。
parent = -2且cur = 1进行先进行左单旋，再进行右单旋。
parent = 2且cur = -1进行先进行右单旋，再进行左单旋。

	bool insert(const pair<K, V>& kv){// 如果根节点为空，创建新节点作为根节点并设置平衡因子为 0，然后返回插入成功if (_root == nullptr){_root = new Node(kv);_root->_bf = 0;return true;}// 初始化父节点为空，当前节点为根节点Node* parent = nullptr;Node* cur = _root;// 查找插入位置while (cur){// 小于当前节点，往左子树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 false;}}// 找到插入位置，创建新节点cur = new Node(kv);// 根据键值大小确定新节点在父节点的位置if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更新平衡因子while (parent){// 如果插入在左边，父节点的平衡因子减 1if (cur == parent->_left){parent->_bf--;}// 如果插入在右边，父节点的平衡因子加 1else{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){RotateR(parent);}// 左单旋else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}// 左右双旋else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}// 右左双旋else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}break;}// 插入之前 AVL 树就已经不平衡了，断言else{assert(false);}}return true;}

5.3. AVL树的查找

AVL树的查找逻辑就与二叉搜索树一样了，这里就不在赘述。

Node* Find(const K& val)
{Node* cur = _root;while (cur){if (cur->_kv.first > val){//左子树中查找cur = cur->_left;}else if (cur->_kv.first < val){//右子树中查找cur = cur->_right;}else{//找到了return cur;}}return nullptr;
}

5.4. AVL树的删除

AVL树的删除逻辑其实整体与二叉搜索树的删除逻辑类似，可以分为三种情况讨论：删除节点的左子树节点为空

，删除节点的右子树节点为空，删除节点的左右子树都不为空。其中删除节点的左右子树都不为空可以经过伪删除法，即寻找到左子树的最右节点即左子树的最大值，或者是右子树的最左节点即右子树的最小值。然后赋值，转换为在其左子树或者右子树删除节点。而我们的AVL树本质是为了保持平衡，所以尽量选择删除子树较高的一方。

因为删除节点的左右子树都不为空的情况一定会被转换另外两种情况，所以我们只需要讨论删除节点的左子树节点为空，删除节点的右子树节点为空这两种情况。

当然这里在上面基础上再重新分类可分为：

删除节点在父节点的左侧：

当节点数少于三个时，删除后父节点平衡因子为1或0时，正常删除。

当父节点parent的右子树的左右子树高度相等，且删除后父节点平衡因子为2时，进行左单旋。

当父节点parent的右子树的右子树高度大于其左子树高度，且删除后父节点平衡因子为2时，进行左单旋。

当父节点parent的右子树的右子树高度小于其左子树高度，且删除后父节点平衡因子为2时，先进行右单旋，再进行左单旋。

删除节点在父节点右侧：

当节点数少于三个时，删除后父节点平衡因子为-1或0时，正常删除。

当父节点parent的左子树的左右子树高度相等，且删除后父节点平衡因子为-2时，进行右单旋。

当父节点parent的左子树的左子树高度大于其右子树高度，且删除后父节点平衡因子为-2时，进行右单旋。

当父节点parent的左子树的左子树高度小于其右子树高度，且删除后父节点平衡因子为-2时，先进行左单旋，再进行右单旋。

最后我们可以总结出以下结论：

当删除节点在父节点的左侧时

父节点的平衡因子为2时，如果根节点的右子树的右子树高度大于等于其左子树高度，进行左单旋，否则进行先右旋再左旋。
父节点的平衡因子不为2时，正常删除。

当删除节点在父节点的右侧时

父节点的平衡因子为-2时，如果根节点的左子树的左子树高度大于等于其右子树高度，进行右单旋，否则进行先左旋再右旋。
父节点的平衡因子不为-2时，正常删除。

//求高度
int Hegiht(Node* root)
{if (root == nullptr)return 0;int leftHegiht = Hegiht(root->_left);//先计算左子树高度int rightHegiht = Hegiht(root->_right);//再计算右子树高度return leftHegiht > rightHegiht ? leftHegiht + 1 : rightHegiht + 1;
}
void erase(const K& val)
{//递归删除_root = _erase(_root, val);
}
Node* _erase(Node* node, const K& val)
{// 如果当前节点为空，直接返回空指针if (node == nullptr){return nullptr;}// 如果当前节点的键值大于要删除的键值，在左子树中删除if (node->_kv.first > val){node->_left = _erase(node->_left, val);//更新节点的父节点if (node->_left)node->_left->_parent = node;// 调整节点的平衡因子node->_bf = Hegiht(node->_right) - Hegiht(node->_left);int bf = node->_bf;//情况一删除节点都在左边if (bf == 2){int rightHegiht = Hegiht(node->_right->_right);int leftHegiht = Hegiht(node->_right->_left);if (rightHegiht >= leftHegiht){RotateL(node);}else{RotateRL(node);}}}// 如果当前节点的键值小于要删除的键值，在右子树中删除else if (node->_kv.first < val){node->_right = _erase(node->_right, val);//更新节点的父节点if(node->_right)node->_right->_parent = node;// 调整节点平衡因子node->_bf = Hegiht(node->_right) - Hegiht(node->_left);int bf = node->_bf;//情况二删除节点都在右边if (bf == -2){int rightHegiht = Hegiht(node->_left->_right);int leftHegiht = Hegiht(node->_left->_left);if (leftHegiht >= rightHegiht){RotateR(node);}else{RotateLR(node);}}}// 找到要删除的节点else{// 如果节点有两个孩子if (node->_left != nullptr && node->_right != nullptr){// 如果左子树高度大于等于右子树高度if (Hegiht(node->_left) >= Hegiht(node->_right)){// 找到左子树中的最大节点Node* prev = node->_left;while (prev->_right)prev = prev->_right;int target = prev->_kv.first;// 将当前节点的值替换为左子树中的最大节点的值node->_kv = prev->_kv;// 在左子树中删除该最大节点node->_left = _erase(node->_left,target);}else{// 找到右子树中的最小节点Node* post = node->_right;while (post->_left)post = post->_left;// 将当前节点的值替换为右子树中的最小节点的值int target = post->_kv.first;node ->_kv = post->_kv ;// 在右子树中删除该最小节点node->_right = _erase(node->_right, target);}}// 如果节点最多有一个孩子else{// 如果有左孩子if (node->_left != nullptr){// 保存左孩子指针Node* left = node->_left;// 删除当前节点delete node;// 返回左孩子指针return left;}// 如果有右孩子else if (node->_right != nullptr){// 保存右孩子指针Node* right = node->_right;// 删除当前节点delete node;// 返回右孩子指针return right;}// 如果没有孩子else{// 返回空指针delete node;return nullptr;}}}// 返回调整后的节点指针return node;
}

6. 判断是否为AVL树

在判断一棵树是否为 AVL 树时，其核心在于检查每一个节点的左右子树高度差的绝对值是否小于 1 。由于需要对整棵树的所有子树进行这样的判断，所以采用递归的方法比较合适的。

具体实现时，定义一个函数来进行判断。然后，分别递归地获取左子树和右子树的高度。接着，进行条件判断。如果左子树或右子树中存在高度标记为 -1 的情况（意味着该子树不平衡），或者当前节点左右子树高度差的绝对值大于 1 ，那么就将当前子树的高度标记为 -1 并返回。如果当前节点的子树都是平衡的，那么就返回最高的高度。

最后，通过一个总函数来调用这个递归函数，并根据返回结果是否大于 0 来确定整棵树是否为 AVL 树。如果大于 0 ，则表示整棵树是AVL 树；否则，表示不是AVL树。

//判断是否平衡
bool isBalanced()
{return _isBalanced(_root) >= 0;
}
int _isBalanced(Node* root)
{if (root == nullptr){return 0;}//左平衡高度int left_isBalanced = _isBalanced(root->_left);//右平衡高度int right_isBalanced = _isBalanced(root->_right);//如果右平衡-左平衡则返回-1，并且防止两边同时返回-1相减等于0的情况，需要单独判断if (left_isBalanced == -1 || right_isBalanced == -1 || abs(right_isBalanced - left_isBalanced) > 1){return -1;}//返回最高高度return max(left_isBalanced, right_isBalanced) + 1;
}

7. 复杂度分析

下是对上述AVL 树代码中主要操作的时间复杂度和空间复杂度分析：

时间复杂度：

insert 操作：平均和最坏情况下的时间复杂度均为 $O(\log n)$ 。在插入过程中，通过不断调整平衡因子和进行旋转操作来保持树的平衡，每次调整和旋转的操作时间都是常数级，而查找插入位置的过程类似于二叉搜索树，时间复杂度为
$O(\log n)$ 。
Find 操作：平均和最坏情况下的时间复杂度均为 $O(\log n)$ 。与二叉搜索树的查找过程类似，每次比较都将搜索范围缩小一半。
erase 操作：平均和最坏情况下的时间复杂度均为 $O(\log n)$ 。删除节点时需要查找节点位置，然后进行调整和可能的旋转操作，时间复杂度类似于插入操作。

空间复杂度：

insert 操作：空间复杂度为 $O (1)$ 。在插入过程中，主要的额外空间消耗在于创建新节点以及一些临时变量来存储指针和平衡因子等信息，这些都是常数级的空间消耗。
Find 操作：空间复杂度为 $O (1)$ 。在查找过程中，仅使用了一些固定数量的指针和临时变量，没有额外的大规模空间分配。
erase 操作：空间复杂度为 $O (1)$ 。删除操作中，主要的空间消耗在于临时变量和指针的存储，没有动态分配大规模的额外空间。

总的来说，上述各个操作的主要空间复杂度都为 $O (1)$ ，整个 AVL 树的空间复杂度主要取决于树中节点的数量，即 $O (n)$ ，其中 $n$ 是节点的数量。

8. 源码

#pragma once
#include<utility>
#include<assert.h>
template<class K,class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K, V>& val = pair<K, V>()):_kv(val),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}pair<K, V> _kv;//kv模型int _bf;//平衡因子AVLTreeNode* _left;//左子树AVLTreeNode* _right;//右子树AVLTreeNode* _parent;//指向父节点
};
template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public://...具体功能AVLTree(){}AVLTree(const AVLTree& t){_root = copy(t._root);}AVLTree<K,V>& operator=(const AVLTree <K,V> t){//赋值重载this->swap(_root, t._root);return *this;}void RotateR(Node*&parent){// 获取父节点的左子节点Node* subL = parent->_left;// 获取父节点左子节点的右子节点Node* subLR = subL->_right;// 1.将subLR链接到parent的左边。parent->_left = subLR;// 如果父节点左子节点的右子节点存在，设置其父节点为当前父节点if (subLR){subLR->_parent = parent;}// 获取父节点的父节点Node* ppNode = parent->_parent;// 2.将parent链接到subL的右边。subL->_right = parent;//parent的父节点指向subLparent->_parent = subL;// 如果父节点存在父节点if (ppNode){// 如果父节点是其父亲节点的左子节点if (ppNode->_left == parent){// 将父节点的父亲节点的左子节点设置为当前父节点的左子节点ppNode->_left = subL;}// 如果父节点是其父亲节点的右子节点else{// 将父节点的父亲节点的右子节点设置为当前父节点的左子节点ppNode->_right = subL;}// 设置父节点左子节点的父节点为父节点的父节点subL->_parent = ppNode;}// 如果父节点为根节点else{// 将根节点设置为父节点的左子节点_root = subL;// 将父节点左子节点的父节点设置为空subL->_parent = nullptr;}//3.将parent与subL的平衡因子置为0。subL->_bf = parent->_bf = 0;//改变parent节点的指向，方便erase中的node返回parent = subL;}void RotateL(Node* &parent){// 获取父节点的右子节点Node* subR = parent->_right;// 获取父节点右子节点的左子节点Node* subRL = subR->_left;//1.将subRL链接到parent的右边。parent->_right = subRL;// 如果父节点右子节点的左子节点存在，设置其父节点为当前父节点if (subRL){subRL->_parent = parent;}// 获取父节点的父节点Node* ppNode = parent->_parent;//2.将parent链接到subR的左边。subR->_left = parent;// 设置父节点的父节点为右子节点parent->_parent = subR;// 如果父节点存在父节点if (ppNode){// 如果父节点是其父亲节点的左子节点if (ppNode->_left == parent){// 将父节点的父亲节点的左子节点设置为当前父节点的右子节点ppNode->_left = subR;}// 如果父节点是其父亲节点的右子节点else{// 将父节点的父亲节点的右子节点设置为当前父节点的右子节点ppNode->_right = subR;}// 设置父节点右子节点的父节点为父节点的父节点subR->_parent = ppNode;}// 如果父节点为根节点else{// 将根节点设置为父节点的右子节点_root = subR;// 将父节点右子节点的父节点设置为空subR->_parent = nullptr;}// 3.将parent与subR的平衡因子置为0。subR->_bf = parent->_bf = 0;//改变parent节点的指向，方便erase中的node返回parent = subR;}void RotateLR(Node*&parent){Node* subL = parent->_left;Node* subLR = subL->_right;//先左旋RotateL(parent->_left);//再右旋RotateR(parent);int bf = subLR->_bf;//1.情况1if (bf == 0){parent->_bf = subL->_bf = subLR->_bf = 0;}//2.情况2else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}//3.情况3else if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else{//走到这里说明AVL树有问题assert(false);}}void RotateRL(Node*&parent){Node* subR = parent->_right;Node* subRL = subR->_left;//先右单旋RotateR(parent->_right);//再左单旋RotateL(parent);int bf = subRL->_bf;//1.情况一if (bf == 0){parent->_bf = subRL->_bf = subR->_bf = 0;}//2.情况二else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}//3.情况三else if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else{//走到这里说明AVL树出错assert(false);}}bool insert(const pair<K, V>& kv){// 如果根节点为空，创建新节点作为根节点并设置平衡因子为 0，然后返回插入成功if (_root == nullptr){_root = new Node(kv);_root->_bf = 0;return true;}// 初始化父节点为空，当前节点为根节点Node* parent = nullptr;Node* cur = _root;// 查找插入位置while (cur){// 小于当前节点，往左子树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 false;}}// 找到插入位置，创建新节点cur = new Node(kv);// 根据键值大小确定新节点在父节点的位置if (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更新平衡因子while (parent){// 如果插入在左边，父节点的平衡因子减 1if (cur == parent->_left){parent->_bf--;}// 如果插入在右边，父节点的平衡因子加 1else{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){RotateR(parent);}// 左单旋else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}// 左右双旋else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}// 右左双旋else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}break;}// 插入之前 AVL 树就已经不平衡了，断言else{assert(false);}}return true;}Node* Find(const K& val){Node* cur = _root;while (cur){if (cur->_kv.first > val){//左子树中查找cur = cur->_left;}else if (cur->_kv.first < val){//右子树中查找cur = cur->_right;}else{//找到了return cur;}}return nullptr;}//求高度int Hegiht(Node* root){if (root == nullptr)return 0;int leftHegiht = Hegiht(root->_left);//先计算左子树高度int rightHegiht = Hegiht(root->_right);//再计算右子树高度return leftHegiht > rightHegiht ? leftHegiht + 1 : rightHegiht + 1;}void erase(const K& val){//递归删除_root = _erase(_root, val);}//判断是否平衡bool isBalanced(){return _isBalanced(_root) >= 0;}~AVLTree(){Destroy(_root);}private:void Destroy(Node* root){if (root == nullptr){return;}//cout << root->_kv.first << " ";//递归销毁左子树Destroy(root->_left);//递归销毁右子树Destroy(root->_right);//销毁根节点delete root;//root = nullptr;}Node* _erase(Node* node, const K& val){// 如果当前节点为空，直接返回空指针if (node == nullptr){return nullptr;}// 如果当前节点的键值大于要删除的键值，在左子树中删除if (node->_kv.first > val){node->_left = _erase(node->_left, val);//更新节点的父节点if (node->_left)node->_left->_parent = node;// 调整节点的平衡因子node->_bf = Hegiht(node->_right) - Hegiht(node->_left);int bf = node->_bf;//情况一删除节点都在左边if (bf == 2){int rightHegiht = Hegiht(node->_right->_right);int leftHegiht = Hegiht(node->_right->_left);if (rightHegiht >= leftHegiht){RotateL(node);}else{RotateRL(node);}}}// 如果当前节点的键值小于要删除的键值，在右子树中删除else if (node->_kv.first < val){node->_right = _erase(node->_right, val);//更新节点的父节点if(node->_right)node->_right->_parent = node;// 调整节点平衡因子node->_bf = Hegiht(node->_right) - Hegiht(node->_left);int bf = node->_bf;//情况二删除节点都在右边if (bf == -2){int rightHegiht = Hegiht(node->_left->_right);int leftHegiht = Hegiht(node->_left->_left);if (leftHegiht >= rightHegiht){RotateR(node);}else{RotateLR(node);}}}// 找到要删除的节点else{// 如果节点有两个孩子if (node->_left != nullptr && node->_right != nullptr){// 如果左子树高度大于等于右子树高度if (Hegiht(node->_left) >= Hegiht(node->_right)){// 找到左子树中的最大节点Node* prev = node->_left;while (prev->_right)prev = prev->_right;int target = prev->_kv.first;// 将当前节点的值替换为左子树中的最大节点的值node->_kv = prev->_kv;// 在左子树中删除该最大节点node->_left = _erase(node->_left,target);}else{// 找到右子树中的最小节点Node* post = node->_right;while (post->_left)post = post->_left;// 将当前节点的值替换为右子树中的最小节点的值int target = post->_kv.first;node ->_kv = post->_kv ;// 在右子树中删除该最小节点node->_right = _erase(node->_right, target);}}// 如果节点最多有一个孩子else{// 如果有左孩子if (node->_left != nullptr){// 保存左孩子指针Node* left = node->_left;// 删除当前节点delete node;// 返回左孩子指针return left;}// 如果有右孩子else if (node->_right != nullptr){// 保存右孩子指针Node* right = node->_right;// 删除当前节点delete node;// 返回右孩子指针return right;}// 如果没有孩子else{// 返回空指针delete node;return nullptr;}}}// 返回调整后的节点指针return node;}int _isBalanced(Node* root){if (root == nullptr){return 0;}//左平衡高度int left_isBalanced = _isBalanced(root->_left);//右平衡高度int right_isBalanced = _isBalanced(root->_right);//如果右平衡-左平衡则返回-1，并且防止两边同时返回-1相减等于0的情况，需要单独判断if (left_isBalanced == -1 || right_isBalanced == -1 || abs(right_isBalanced - left_isBalanced) > 1){return -1;}//返回最高高度return max(left_isBalanced, right_isBalanced) + 1;}Node* copy(Node* root){// 如果传入的根节点为空，直接返回空指针，表示拷贝结束if (root == nullptr)return nullptr;// 为新树创建一个与原始根节点值相同的新节点Node* newnode = new Node(root->_kv);// 递归地拷贝原始根节点的左子树，并将结果赋给新节点的左指针newnode->_left = copy(root->_left);// 递归地拷贝原始根节点的右子树，并将结果赋给新节点的右指针newnode->_right = copy(root->_right);// 新节点的父节点默认为空newnode->_parent = nullptr;// 如果新节点的左子节点存在，设置其父节点为新节点if (newnode->_left){newnode->_left->_parent = newnode;}// 如果新节点的右子节点存在，设置其父节点为新节点if (newnode->_right){newnode->_right->_parent = newnode;}// 返回新树的根节点指针return newnode;}Node* _root = nullptr;//根节点
};}// 如果有右孩子else if (node->_right != nullptr){// 保存右孩子指针Node* right = node->_right;// 删除当前节点delete node;// 返回右孩子指针return right;}// 如果没有孩子else{// 返回空指针delete node;return nullptr;}}}// 返回调整后的节点指针return node;}int _isBalanced(Node* root){if (root == nullptr){return 0;}//左平衡高度int left_isBalanced = _isBalanced(root->_left);//右平衡高度int right_isBalanced = _isBalanced(root->_right);//如果右平衡-左平衡则返回-1，并且防止两边同时返回-1相减等于0的情况，需要单独判断if (left_isBalanced == -1 || right_isBalanced == -1 || abs(right_isBalanced - left_isBalanced) > 1){return -1;}//返回最高高度return max(left_isBalanced, right_isBalanced) + 1;}Node* copy(Node* root){// 如果传入的根节点为空，直接返回空指针，表示拷贝结束if (root == nullptr)return nullptr;// 为新树创建一个与原始根节点值相同的新节点Node* newnode = new Node(root->_kv);// 递归地拷贝原始根节点的左子树，并将结果赋给新节点的左指针newnode->_left = copy(root->_left);// 递归地拷贝原始根节点的右子树，并将结果赋给新节点的右指针newnode->_right = copy(root->_right);// 新节点的父节点默认为空newnode->_parent = nullptr;// 如果新节点的左子节点存在，设置其父节点为新节点if (newnode->_left){newnode->_left->_parent = newnode;}// 如果新节点的右子节点存在，设置其父节点为新节点if (newnode->_right){newnode->_right->_parent = newnode;}// 返回新树的根节点指针return newnode;}Node* _root = nullptr;//根节点
};