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

C++进阶--AVL树的实现续

ai 2025/5/11 6:47:51

文章目录

C++进阶--AVL树的实现
- 双旋
- AVL树的查找
- AVL树的检验
- 结语

很高兴和搭大家见面，给生活加点impetus，开启今天的比编程之路！！

今天我们来完善AVL树的操作，为后续红黑树奠定基础！！
作者：٩( ‘ω’ )و260
我的专栏：C++进阶，C++初阶，数据结构初阶，题海探骊，c语言
欢迎点赞，关注！！

C++进阶–AVL树的实现

在前面一个文章中，我们学习了AVL树插入情况的单旋，今天我们来学习双旋操作。

双旋

话不多说，我们直接来看具体的案例，左右双旋，请看下图：

来看这一种情况，此时如果我们是在5的左边进行插入操作的话，此时需要进行右单旋，以10为旋转中心，但是如果此时我们是在5的右边进行插入操作的话，如果我们继续进行单旋操作，就会发现这AVL树从左边高变成了右边高。
这种情况的时候，我们就应该进行双旋。

总结：什么时候使用单旋，什么时候使用双旋呢？
如果AVL树此时是一边高，即左边高的左边高或者是右边高的右边高，此时应使用单旋，但是如果是左边高的右边高或者是右边高的左边高，此时应该使用双旋。

具体步骤：
需要用两次旋转才能解决，以5为旋转点进行⼀个左单旋，以10为旋转点进行一个右单旋，这棵树就平衡了。

我们再来看一个示例：
此时单旋是根本解决不了问题的。
在这里插入图片描述
注意观察：此时是左边高的右边高（相较于10来说，是左边高，相较于5来说，是右边高），应该使用双旋，我们来看一下具体过程。

过程：先以5为旋转点进行右单旋，随后再以10为旋转点进行右单旋。
具体图像在上方已经呈现，其实，当我们对5进行右单旋的时候，我们其实能够发现，这个时候已经是左单旋的模型了。
在这里插入图片描述

在这里插入图片描述

总结：为了方便记忆，我们来说明双旋之后造成的效果是什么？
我们发现8作为了新的根，5和10分别作为了8的左右子树，即旋转点作为了根的左右子树，以5左旋，5作为左子树，以10右旋，10作为了根的右子树。

接下来我们来看代码实现：

void RotateLR(Node* parent)//此时是左子树高，左子树的右子树高，因为LR，L在前
{//思路:先对subL进行左旋，再对parent进行右旋Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//int bf = subLR->_bf;//现在都已经修改了，还写在这里干嘛？//修改平衡因子if (bf == -1)//此时在subLR的左子树插入{subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else if (bf == 1)//此时在subLR的右子树插入{subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else if (bf == 0)//此时新插入的结点就是subLR，此时全部都为0{subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}else {assert(false);}
}

当然，左右双旋是如此，右左双选也是如此。
接下来我们来看一下左右双旋的简图：
在这里插入图片描述

AVL树的查找

AVL树的查找，其实就是在寻找key需要放置的合适位置，其实本质上就是二叉搜索树搜索的过程。直接来看代码：

Node* Find(const K& key)//查找结点
{Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;
}

AVL树的检验

我们来看如果检验AVL树，检查AVL树需要检查平衡因子是否正常，其次就是高度差是否正常。检查平衡因子的话其实本质上就是检查高度差的问题。
直接设立两个变量，表示这个结点的左子树的高度和这个结点的右子树的高度。最后算一下高度差即可，随后再来算一下平衡因为是否能够对应上这个高度差即可
接下来我们直接来看代码实现：

bool _IsBalanceTree(Node* root)//检测这个二叉树是不是AVL树
{// 空树也是AVL树if (nullptr == root) return true;// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者// pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "⾼度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因⼦异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}