上海网站制作是什么,营销推广48个方法,注册网站,无锡易时代网站建设有限公司怎么样✨✨ 欢迎大家来到贝蒂大讲堂✨✨ #x1f388;#x1f388;养成好习惯#xff0c;先赞后看哦~#x1f388;#x1f388; 所属专栏#xff1a;数据结构与算法 贝蒂的主页#xff1a;Betty’s blog 1. AVL树的介绍
在前面我们学习二叉搜索树时知道#xff0c;在数据有序… ✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 养成好习惯先赞后看哦~ 所属专栏数据结构与算法 贝蒂的主页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。当然为了适配不同的类型我们可以定义一个模版.。
templateclass K,class V
struct AVLTreeNode
{AVLTreeNode(const pairK, V val pairK, V()):_kv(val),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}pairK, V _kv;//kv模型int _bf;//平衡因子AVLTreeNode* _left;//左子树AVLTreeNode* _right;//右子树AVLTreeNode* _parent;//指向父节点
};3.2. AVL树
然后我们就可以通过节点来定义AVL树并将根节点初始化为空。
templateclass K,class V
class AVLTree
{typedef AVLTreeNodeK, 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所指向的对象出了作用域就会销毁间接实现了实现赋值重载。
AVLTreeK,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只能取-101三个值。而无论插入还是删除都可能破坏原有的结构导致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 0subLR 0parent 1。当subLR 0即h 0时
比如依次插入三个节点1056如下图所示 调整后subL 0subLR 0parent 0。
当subLR 1时具体情况如下图 调整后subL -1subLR 0parent 0。
最后我们可以总结一下 当subLR 0时调整为subLR 0subL 0parent 0。当subLR -1时调整为subLR 0subL 0parent 1。当subLR 1时调整为subLR 0subL -1parent 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 1subRL 0parent 0。当subRL 0即h 0时
比如依次插入三个节点5106如下图所示 调整后subR 0subRL 0parent 0。
3.当subRL 1时具体情况如下图 调整后subR 0subRL 0parent -1。
最后我们可以总结一下 当subRL 0时调整为subRL 0subR 0parent 0。当subRL -1时调整为subRL 0subR 1parent 0。当subRL 1时调整为subRL 0subL 0parent -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 -2subL -1进行右单旋。 第二种往较高右子树的右侧插入此时parent 2subL 1进行左单旋。 第三种往较高左子树的右侧插入此时parent -2subL 1先左旋再右旋。 第四种往较高右子树的右侧插入先右旋再左旋此时parent 2subR -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 pairK, 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) O(logn)。在插入过程中通过不断调整平衡因子和进行旋转操作来保持树的平衡每次调整和旋转的操作时间都是常数级而查找插入位置的过程类似于二叉搜索树时间复杂度为 O ( log n ) O(\log n) O(logn)。Find 操作平均和最坏情况下的时间复杂度均为 O ( log n ) O(\log n) O(logn)。与二叉搜索树的查找过程类似每次比较都将搜索范围缩小一半。erase 操作平均和最坏情况下的时间复杂度均为 O ( log n ) O(\log n) O(logn)。删除节点时需要查找节点位置然后进行调整和可能的旋转操作时间复杂度类似于插入操作。 空间复杂度 insert 操作空间复杂度为 O ( 1 ) O(1) O(1)。在插入过程中主要的额外空间消耗在于创建新节点以及一些临时变量来存储指针和平衡因子等信息这些都是常数级的空间消耗。Find 操作空间复杂度为 O ( 1 ) O(1) O(1)。在查找过程中仅使用了一些固定数量的指针和临时变量没有额外的大规模空间分配。erase 操作空间复杂度为 O ( 1 ) O(1) O(1)。删除操作中主要的空间消耗在于临时变量和指针的存储没有动态分配大规模的额外空间。 总的来说上述各个操作的主要空间复杂度都为 O ( 1 ) O(1) O(1)整个 AVL 树的空间复杂度主要取决于树中节点的数量即 O ( n ) O(n) O(n)其中 n n n 是节点的数量。 8. 源码
#pragma once
#includeutility
#includeassert.h
templateclass K,class V
struct AVLTreeNode
{AVLTreeNode(const pairK, V val pairK, V()):_kv(val),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}pairK, V _kv;//kv模型int _bf;//平衡因子AVLTreeNode* _left;//左子树AVLTreeNode* _right;//右子树AVLTreeNode* _parent;//指向父节点
};
templateclass K,class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public://...具体功能AVLTree(){}AVLTree(const AVLTree t){_root copy(t._root);}AVLTreeK,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 pairK, 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;//根节点
};
