标准百度网站建设,电子商务网站前台建设常用的技术,网站首页静态化代码,年轻人免费观看视频文章目录 前言AVL树的概念AVL树节点的定义AVL树类框架AVL树的插入AVL树的旋转新节点插入较高子树的左侧 —— 左左: 右单旋新节点插入较高右子树的右侧——右右: 左单旋新节点插入较高左子树的右侧 —— 左右#xff1a; 先左单旋然后再有单旋新节点插入较高右子树的左侧… 文章目录 前言AVL树的概念AVL树节点的定义AVL树类框架AVL树的插入AVL树的旋转新节点插入较高子树的左侧 —— 左左: 右单旋新节点插入较高右子树的右侧——右右: 左单旋新节点插入较高左子树的右侧 —— 左右 先左单旋然后再有单旋新节点插入较高右子树的左侧右左单旋旋转总结 AVL树插入完整代码AVL树的验证验证其为二叉搜索树验证其为平衡树 AVL树的删除AVL树的性能完整实现代码总结 前言 本篇博客将为大家详细讲述AVL树是什么以及其相对于普通的二叉搜索树有什么优点将详细讲述其拥有哪些性质并且通过模拟实现的方式让大家对该数据结构有更深入的理解和认识对于该数据结构的增删查改操作其中的删除操作是在普通搜索二叉树的基础上进行一些改进会简单提及但不会细讲重点将会讲述插入操作查和改操作和二叉搜索树一模一样也不做讲解。 由于AVL树是一棵特殊的二叉搜索树因此想要学习AVL树需要先知道二叉搜索树是什么东西如果有不知道二叉搜索树是什么的小伙半可以先看看博主的另一篇博客: 数据结构—— 二叉搜索树(附c模拟实现) 该篇博客详细介绍了二叉搜索树。 AVL树的概念
我们知道二叉搜索树虽然可以缩短查找的效率但如果数据有序或接近有序那么此时二叉搜索树将会退化成单支树此时的查找效率和在链表中搜索等同效率低下因此两位俄罗斯的数学家(G.M.Adelson-Velskii 和E.M.Landis)在1962年的时候发明了一种解决上述问题的方法 当向二叉搜索树中插入新节点后如果能够保证每个节点的左右子树高度差的绝对值不超过1(在不破坏二叉搜素树性质的情况下对树中节点进行调整)即可降低树的高度从而减少平均搜索长度。 因此AVL树就这样诞生了 一棵AVL树可以是空树或者是具有如下性质的搜索二叉树
它的左右子树都是AVL树左右子树高度之差的绝对值超过1 因此对于一棵AVL树最重要的就是如何控制每棵树左右子树高度之差都不超过1这种控制是通过翻转操作来实现的博主在下文会重点讲解。 另外AVL树的实现方式有两种一种就是在插入的过程中动态的检查左右子树的高度差是否超过1另外一种就是引入一个新的概念——平衡因子对于每个节点都存储一个int值表示该根节点左右子树的高度差负数代表左子树更高正数代表右子树更高然后在插入的过程中不断维护每个节点的平衡因子即可。
这里由于第二种方法实现起来相对逻辑更加清晰所以我们采用第二种方法进行模拟实现并且用key_value的模型进行实现
AVL树节点的定义
和普通二叉搜索树节点定义不同的是AVL树的节点为了方便进行旋转操作需要多加一个指针指向其双亲节点并且还要有一个int值表示平衡因子定义如下
templatetypename K, typename V
struct TreeNode
{pairK, V _kv;TreeNodeK, V* _parent nullptr;TreeNodeK, V* _left nullptr;TreeNodeK, V* _right nullptr;int _bf 0; //balance factorTreeNode(const K key, const V value):_kv({ key, value }){}
};AVL树类框架
templatetypename K, typename V
class AVL_Tree
{typedef TreeNodeK, V node;
private:node* _root nullptr;
public:bool insert(const pairK, V kv) void inorder();void is_AVL();
};
AVL树的插入
AVL树就是在二叉搜索树的基础上引入平衡因子因此插入过程其实可以分成两步
按照二叉搜索树的方式插入新节点调整节点的平衡因子
对于第一步按照二叉搜索树的规则插入新节点的步骤这里不进行详解这里重点讲解如何调整插入节点后各个AVL树节点的平衡因子。 pCur表示新插入的节点pParent表示新插入节点的父节点需要找到父节点是节点定义时需要定义指向双亲的指针的原因之一。 pCur插入后 pParent的平衡因子一定需要调整插入之前pParent的平衡因子分为三种情况(-1/0/1)而根据pCur插入位置的不同可以分为以下两种情况 如果pCur插入到pParent的左侧只需要给pParent的平衡因子减一如果pCur插入到pParent的右侧只需要给pParent的平衡因子加一 pParent的平衡因子经过修改后可能会出现五种情况0±1±2 如果pParent的平衡因子为0说明修改后以pParent为根节点的最高高度并没有发生变化所以无需继续调整插入成功 如下图所示如果插入后pParent的平衡因子为±1说明插入前pParent的平衡因子一定是0插入后被更新成±1说明插入后以pParent为根的子树高度增加了1也就是说我们需要继续向上更新祖先节点的平衡因子 如下图所示: 这个过程将不断循环直到一直更新到pParent的平衡因子为0或者pParent更新到根节点为止。 如果pParent的平衡因子为±2那么此时以pParent为根的树已经不满足AVL树的性质了此时就需要进行旋转操作对于旋转是什么我们在下一个小节进行讲解这里先给出插入代码整体框架 bool insert(const pairK, V kv){//如果头节点为空直接将值赋给头节点即可if (!_root){node* newNode new node(kv.first, kv.second);_root newNode;return true;}//如果不为空寻找插入位置node* parent nullptr, *cur _root;while (cur){auto key cur-_kv.first;parent cur;if (kv.first key)cur cur-_right;else if (kv.first key)cur cur-_left;else return false;}node* newNode new node(kv.first, kv.second);//循环结束找到插入位置if (parent-_kv.first kv.first)parent-_right newNode;elseparent-_left newNode;newNode-_parent parent;cur newNode;//更新平衡因子while (parent){//先修改因子//判断新增节点的方位对parent的平衡因子进行处理if (parent-_right cur)parent-_bf;elseparent-_bf--;if (parent-_bf 0) break;//如果parent的平衡因子为±1继续处理else if (abs(parent-_bf) 1){cur parent;parent parent-_parent;}else if (abs(parent-_bf) 2){//此时以pParent为根的子树已经违反了AVL树的特性需要进行旋转处理//...}//由于平衡因子的情况只有以上五种出现其他种类的平衡因子说明AVL树已经被破坏//通过抛异常来显示else throw the bf out_of_range;}return true;}AVL树的旋转
上一小节说到在一棵本来是平衡的AVL树中插入一个新节点可能导致不平衡必须调整树的结构使之平衡这一步也叫做旋转AVL树的旋转也分为四种 旋转的本质其实是使高度较高的子树高度降低然后将降低的高度给到其另一个较低的子树 新节点插入较高子树的左侧 —— 左左: 右单旋 上图是左单旋的普遍思路但是我们还需要考虑一些特殊场景: 30的右孩子可能存在也可能不存在60可能是根节点也可能是子树 如果60是根节点旋转完成之后需要更新根节点如果60是子树可能是左子树也可能是右子树需要注意更改上面的链接关系 这里大家可以自行画图模拟一下各种特殊场景至于为什么要考虑这些场景是因为虽然整个思路很简单但是由于我们整棵树是以三叉链的形式来存储的所以修改过程中需要维护这一结构。 下面是右旋代码
void reverseR(node* parent)
{node* cur parent-_left, *ppnode parent-_parent;node* curR cur-_right;//连接parent和curRparent-_left curR;if (curR)curR-_parent parent;//连接cur和parentcur-_right parent;parent-_parent cur;//连接ppnode和curcur-_parent ppnode;if (ppnode){if (ppnode-_right parent)ppnode-_right cur;elseppnode-_left cur;}else_root cur;//跟新bfparent-_bf cur-_bf 0;
}新节点插入较高右子树的右侧——右右: 左单旋 由于右单旋和左单旋基本类似这里不进行细致讲解下面是实现代码:
void reverseL(node* parent)
{node* ppnode parent-_parent, *cur parent-_right;node* curL cur-_left;// 连接parent和curLeftparent-_right curL;if (curL) curL-_parent parent;// 连接parent和curcur-_left parent;parent-_parent cur;//跟新parent和cur的平衡因子parent-_bf cur-_bf 0;//更新根节点或者与ppnode的连接关系if (ppnode){if (ppnode-_right parent)ppnode-_right cur;elseppnode-_left cur;cur-_parent ppnode;}else{_root cur;cur-_parent nullptr;}
}新节点插入较高左子树的右侧 —— 左右 先左单旋然后再有单旋 其次对于右左单旋来说还有一个需要考虑的点就是平衡因子的更新对于这个问题我们可以先总结一下上图90作为pParent, 30作为pCur, 60作为curR左右单旋的结果其实使把curR的左子树与pCur链接curR的右子树与pParent链接然后curR作为新树的根那么平衡因子的修改就需要根据60的平衡因子为状况进行修改了,curR的平衡因子一共有三种情况(-1/0/1).我们逐步分析
curR是新插入的节点 —— curR的平衡因子是0相当于上图中h等于0的情况 插入后pParentpCur和curR的平衡因子都变成0 插入在curR的左子树 —— curR的平衡因子是-1 由于插入后curR的左子树交给了pCur也就是上图中的情况此时pCur和curR的平衡因子都变成0pParent的平衡因子变成1 插入在curR的右子树——curR的平衡因子是1 对应的就是上图中c的高度是h, b的高度是h - 1, 此时pParent 和 curR的平衡因子都变成0 pCur的平衡因子变成-1 因此旋转后平衡因子的改变是根据curR的平衡因子的状况就行分类修改的并且由于上文中我们定义了左右旋转的函数直接复用就可以得到左右单选的函数代码如下: void reverseRL(node* parent){node* cur parent-_right, * curL cur-_left;int bf curL-_bf;reverseR(cur);reverseL(parent);if (bf 0)cur-_bf parent-_bf curL-_bf 0;else if (bf -1){cur-_bf 1;parent-_bf curL-_bf 0;}else if (bf 1){parent-_bf -1;cur-_bf curL-_bf 0;}elsethrow balance factor out_of_range;}新节点插入较高右子树的左侧右左单旋 这里的思考方式和右左单选相同留给大家自己思考。
旋转总结
假如以pParent为根的子树不平衡即pParent的平衡因子为±2分以下情况考虑
pParent的平衡因子为2说明pParent的右子树高设pParent的右子树的根为pCur
当pCur的平衡因子为1是执行左单旋如果是-1执行右左单选
pParent的平衡因子为-2说明pParent的左子树高设pParent的左子树的根为pCur
当pCur的平衡因子为-1时执行右单旋当pCur的平衡因子为1时执行左右单旋 另外我们可以发现旋转完成之后当前根的平衡因子都变成了0因此不需要继续向上更新
AVL树插入完整代码
public:bool insert(const pairK, V kv){//如果头节点为空直接将值赋给头节点即可if (!_root){node* newNode new node(kv.first, kv.second);_root newNode;return true;}//如果不为空寻找插入位置node* parent nullptr, *cur _root;while (cur){auto key cur-_kv.first;parent cur;if (kv.first key)cur cur-_right;else if (kv.first key)cur cur-_left;else return false;}node* newNode new node(kv.first, kv.second);//循环结束找到插入位置if (parent-_kv.first kv.first)parent-_right newNode;elseparent-_left newNode;newNode-_parent parent;cur newNode;//更新平衡因子while (parent){//先修改因子//判断新增节点的方位对parent的平衡因子进行处理if (parent-_right cur)parent-_bf;elseparent-_bf--;if (parent-_bf 0) break;//如果parent的平衡因子为±1继续处理else if (abs(parent-_bf) 1){cur parent;parent parent-_parent;}else if (abs(parent-_bf) 2){//进行翻转操作if (parent-_bf 2 cur-_bf 1) reverseL(parent);else if (parent-_bf -2 cur-_bf -1)reverseR(parent);else if (parent-_bf 2 cur-_bf -1) reverseRL(parent);else if (parent-_bf -2 cur-_bf 1) reverseLR(parent);break;}//由于平衡因子的情况只有以上五种出现其他种类的平衡因子说明AVL树已经被破坏//通过抛异常来显示else throw the bf out_of_range;}return true;}
private:void reverseL(node* parent){node* ppnode parent-_parent, *cur parent-_right;node* curL cur-_left;// 连接parent和curLeftparent-_right curL;if (curL) curL-_parent parent;// 连接parent和curcur-_left parent;parent-_parent cur;//跟新parent和cur的平衡因子parent-_bf cur-_bf 0;//更新根节点或者与ppnode的连接关系if (ppnode){if (ppnode-_right parent)ppnode-_right cur;elseppnode-_left cur;cur-_parent ppnode;}else{_root cur;cur-_parent nullptr;}}void reverseR(node* parent){node* cur parent-_left, *ppnode parent-_parent;node* curR cur-_right;//连接parent和curRparent-_left curR;if (curR)curR-_parent parent;//连接cur和parentcur-_right parent;parent-_parent cur;//连接ppnode和curcur-_parent ppnode;if (ppnode){if (ppnode-_right parent)ppnode-_right cur;elseppnode-_left cur;}else_root cur;//跟新bfparent-_bf cur-_bf 0;}void reverseRL(node* parent){node* cur parent-_right, * curL cur-_left;int bf curL-_bf;reverseR(cur);reverseL(parent);if (bf 0)cur-_bf parent-_bf curL-_bf 0;else if (bf -1){cur-_bf 1;parent-_bf curL-_bf 0;}else if (bf 1){parent-_bf -1;cur-_bf curL-_bf 0;}elsethrow balance factor out_of_range;}void reverseLR(node* parent){node* cur parent-_left;node* curR cur-_right;int bf curR-_bf;reverseL(cur);reverseR(parent);if (bf 0)cur-_bf parent-_bf curR-_bf 0;else if (bf -1){parent-_bf -1;cur-_bf curR-_bf 0;}else if (bf 1){cur-_bf 1;curR-_bf parent-_bf 0;}else throwbalance factor out_of_range;}AVL树的验证
可以通过监视窗口进行验证但是这样过于麻烦我们可以设计一个验证函数
验证其为二叉搜索树
如果中序遍历能够得到一个有序序列那就说明是二叉搜索树public:void inorder() {_inorder(_root); cout endl;return;}
private:void _inorder(node* root){if (!root) return;_inorder(root-_left);cout root-_kv.first root-_kv.second endl;_inorder(root-_right);}验证其为平衡树
每个节点子树的高度绝对值不超过1验证节点的平衡因子是否计算正确 博主采用的是回溯的方法来验证先验证左子树和右子树是否为AVL_Tree同时返回该树的高度用于验证上层的树是否为AVL_Tree。 代码如下:
public:void is_AVL() {auto ret _is_AVL(_root); if (ret.second) cout this tree is AVL_tree\n;}
private:pairint, bool _is_AVL(node* root){pairint, bool ret{ 0, true };if (!root) return ret;auto ret_left _is_AVL(root-_left);auto ret_right _is_AVL(root-_right);ret.second ret_left.second ret_right.second;//判断平衡因子是否正确int ans_bf ret_right.first - ret_left.first;if (ans_bf ! root-_bf){printf(平衡因子计算错误正确平衡因子: %d, 当前平衡因子:%d, ans_bf, root-_bf);ret.second false;}if (abs(ans_bf) 2){cout 平衡因子超过最大值\n;ret.second false;}ret.first max(ret_left.first, ret_right.first) 1;return ret;}AVL树的删除
因为AVL树也是搜索二叉树所以可以按照搜索二叉树的方式将节点删除然后只需要加入更新平衡因子的步骤就可以了比较不同的是删除操作下平衡因子的更新是如果删除后节点的平衡因子为0还需要继续更新而如果是±1不需要继续更新±2进行旋转但是旋转完成之后由于根的平衡因子变成了0还有可能需要继续向上更新。
AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这 样可以保证查询时高效的时间复杂度即 l o g 2 ( N ) log_2 (N) log2(N)。但是如果要对AVL树做一些结构修改的操 作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时 有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数 据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
完整实现代码
templatetypename K, typename V
struct TreeNode
{pairK, V _kv;TreeNodeK, V* _parent nullptr;TreeNodeK, V* _left nullptr;TreeNodeK, V* _right nullptr;int _bf 0;TreeNode(const K key, const V value):_kv({ key, value }){}
};templatetypename K, typename V
class AVL_Tree
{typedef TreeNodeK, V node;
private:node* _root nullptr;
public:bool insert(const pairK, V kv){//如果头节点为空直接将值赋给头节点即可if (!_root){node* newNode new node(kv.first, kv.second);_root newNode;return true;}//如果不为空寻找插入位置node* parent nullptr, *cur _root;while (cur){auto key cur-_kv.first;parent cur;if (kv.first key)cur cur-_right;else if (kv.first key)cur cur-_left;else return false;}node* newNode new node(kv.first, kv.second);//循环结束找到插入位置if (parent-_kv.first kv.first)parent-_right newNode;elseparent-_left newNode;newNode-_parent parent;cur newNode;//更新平衡因子while (parent){//先修改因子//判断新增节点的方位对parent的平衡因子进行处理if (parent-_right cur)parent-_bf;elseparent-_bf--;if (parent-_bf 0) break;//如果parent的平衡因子为±1继续处理else if (abs(parent-_bf) 1){cur parent;parent parent-_parent;}else if (abs(parent-_bf) 2){//进行翻转操作if (parent-_bf 2 cur-_bf 1) reverseL(parent);else if (parent-_bf -2 cur-_bf -1)reverseR(parent);else if (parent-_bf 2 cur-_bf -1) reverseRL(parent);else if (parent-_bf -2 cur-_bf 1) reverseLR(parent);break;}//由于平衡因子的情况只有以上五种出现其他种类的平衡因子说明AVL树已经被破坏//通过抛异常来显示else throw the bf out_of_range;}return true;}void inorder() {_inorder(_root); cout endl;return;}void is_AVL() {auto ret _is_AVL(_root); if (ret.second) cout this tree is AVL_tree\n;}
private:void reverseL(node* parent){node* ppnode parent-_parent, *cur parent-_right;node* curL cur-_left;// 连接parent和curLeftparent-_right curL;if (curL) curL-_parent parent;// 连接parent和curcur-_left parent;parent-_parent cur;//跟新parent和cur的平衡因子parent-_bf cur-_bf 0;//更新根节点或者与ppnode的连接关系if (ppnode){if (ppnode-_right parent)ppnode-_right cur;elseppnode-_left cur;cur-_parent ppnode;}else{_root cur;cur-_parent nullptr;}}void reverseR(node* parent){node* cur parent-_left, *ppnode parent-_parent;node* curR cur-_right;//连接parent和curRparent-_left curR;if (curR)curR-_parent parent;//连接cur和parentcur-_right parent;parent-_parent cur;//连接ppnode和curcur-_parent ppnode;if (ppnode){if (ppnode-_right parent)ppnode-_right cur;elseppnode-_left cur;}else_root cur;//跟新bfparent-_bf cur-_bf 0;}void reverseRL(node* parent){node* cur parent-_right, * curL cur-_left;int bf curL-_bf;reverseR(cur);reverseL(parent);if (bf 0)cur-_bf parent-_bf curL-_bf 0;else if (bf -1){cur-_bf 1;parent-_bf curL-_bf 0;}else if (bf 1){parent-_bf -1;cur-_bf curL-_bf 0;}elsethrow balance factor out_of_range;}void reverseLR(node* parent){node* cur parent-_left;node* curR cur-_right;int bf curR-_bf;reverseL(cur);reverseR(parent);if (bf 0)cur-_bf parent-_bf curR-_bf 0;else if (bf -1){parent-_bf -1;cur-_bf curR-_bf 0;}else if (bf 1){cur-_bf 1;curR-_bf parent-_bf 0;}else throwbalance factor out_of_range;}//需要知道两个东西层数高度以及高度差pairint, bool _is_AVL(node* root){pairint, bool ret{ 0, true };if (!root) return ret;auto ret_left _is_AVL(root-_left);auto ret_right _is_AVL(root-_right);ret.second ret_left.second ret_right.second;//判断平衡因子是否正确int ans_bf ret_right.first - ret_left.first;if (ans_bf ! root-_bf){printf(平衡因子计算错误正确平衡因子: %d, 当前平衡因子:%d, ans_bf, root-_bf);ret.second false;}if (abs(ans_bf) 2){cout 平衡因子超过最大值\n;ret.second false;}ret.first max(ret_left.first, ret_right.first) 1;return ret;}void _inorder(node* root){if (!root) return;_inorder(root-_left);cout root-_kv.first root-_kv.second endl;_inorder(root-_right);}};总结 AVL树的出现较为有效的解决了二叉搜索树在极端情况下效率低下的问题但还处理的不够完善因此后面又出现了红黑树对于AVL树在一些地方会更有优势红黑树博主在之后也会讲解关于AVL树的知识就到此结束了如果大家有什么疑惑或者发现博主写的有哪些问题欢迎在评论区指出
