林芝北京网站建设,wordpress搬家出问题,移动端网站如何做导出功能吗,手机网站建设服务商文章目录 前言AVL树节点的定义AVL树的插入AVL树的旋转AVL树的验证AVL树的删除AVL树的性能与源码 前言 二叉搜索树虽可以缩短查找的效率#xff0c;但如果数据有序或接近有序二叉搜索树将退化为单支树#xff0c;查找元素相当于在顺序表中搜索元素#xff0c;效率低下。因此但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson - Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n)搜索时间复杂度O( l o g 2 n log_2 n log2n)。 AVL树节点的定义 templateclass Tstruct TreeNode{public:TreeNode(T data):_data(data), _bf(0), _parent(nullptr), _left(nullptr), _right(nullptr){}public:T _data;// Defining balance factorint _bf; // 该节点的平衡因子// 定义成一个三叉链结构,方便后续操作TreeNode* _parent; // 该节点的双亲TreeNode* _left; // 该节点的左孩子TreeNode* _right; // 该节点的右孩子};AVL树的插入 因为插入逻辑比较复杂我在这里就写一个大致思路具体代码我上传到了git上。
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步
按照二叉搜索树的方式插入新节点调整节点的平衡因子
此处我写一个大致的代码逻辑并结合图片给大家看一下
bool Insert(const T data)
{// 1. 先按照二叉搜索树的规则将节点插入到AVL树中// ...// 2. 新节点插入后AVL树的平衡性可能会遭到破坏此时就需要更新平衡因子// 并检测是否破坏了AVL树的平衡性/*cur插入后parent的平衡因子一定需要调整在插入之前parent的平衡因子分为三种情况-10, 1, 插入时出现以下两种情况1. 如果cur插入到parent的左侧只需给parent的平衡因子-1即可2. 如果cur插入到pParent的右侧只需给parent的平衡因子1即可此时parent的平衡因子可能有三种情况0正负1 正负21. 如果parent的平衡因子为0说明插入之前pParent的平衡因子为正负1插入后被调整成0此时满足AVL树的性质插入成功2. 如果parent的平衡因子为正负1说明插入前parent的平衡因子一定为0插入后被更新成正负1此时以pParent为根的树的高度增加需要继续向上更新3. 如果parent的平衡因子为正负2则parent的平衡因子违反平衡树的性质需要对其进行旋转处理*/while (parent){// 更新双亲的平衡因子if (cur parent-_pLeft)parent-_bf--;elseparent-_bf;// 更新后检测双亲的平衡因子if (0 parent-_bf){break;}else if (1 pParent-_bf || -1 pParent-_bf){// 插入前双亲的平衡因子是0插入后双亲的平衡因为为1 或者 -1 说明以双亲为根的二叉树// 的高度增加了一层因此需要继续向上调整cur pParent;pParent pCur-_pParent;}else{// 双亲的平衡因子为正负2违反了AVL树的平衡性需要对以parent// 为根的树进行旋转处理if (2 pParent-_bf){// ...}else{// ...}}}return true;
}插入节点会影响新增节点的部分祖先 更新规则
c是p的左边p-_bf--c是p的右边p-_bf
是否要继续更新取决于p的高度是否变化是否会影响爷爷节点。
在上面这张图的基础上插入11 我们可以看到
更新后p-_bf 0p所在的高度不会改变不会影响爷爷节点。说明更新前p-_bf是1或者-1p的矮的那一边插入了新节点左右高度均衡了p的高度不变不会影响爷爷更新结束。更新后p-_bf 1 / -1p所在的子树高度变了会影响爷爷。说明更新前p-_bf是0p的有一边插入p变得不均衡但不违反规则p的高度变了会影响爷爷继续往上更新
在上面这张图的基础上再插入1
更新后p-_bf 2 / -2说明p所在的子树违反了平衡规则需要进行旋转处理。 AVL树的旋转 如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种
1. 新节点插入较高左子树的左侧—左左右单旋
/*上图在插入前AVL树是平衡的新节点插入到30的左子树(注意此处不是左孩子)中30左子树增加了一层导致以60为根的二叉树不平衡要让60平衡只能将60左子树的高度减少一层右子树增加一层即将左子树往上提这样60转下来因为60比30大只能将其放在30的右子树而如果30有右子树右子树根的值一定大于30小于60只能将其放在60的左子树旋转完成后更新节点的平衡因子即可。在旋转过程中有以下几种情况需要考虑1. 30节点的右孩子可能存在也可能不存在2. 60可能是根节点也可能是子树如果是根节点旋转完成后要更新根节点如果是子树可能是某个节点的左子树也可能是右子树大家在此处可举一些详细的例子进行画图考虑各种情况加深旋转的理解
*/
void RotateR(Node* parents)
{// SubL: parents的左孩子// SubLR: parents左孩子的右孩子,注意:该节点可能为空Node* SubL parents-_left;Node* SubLR SubL-_right;// 旋转完成之后30的右孩子作为双亲的左孩子parents-_left SubLR;// 如果30的左孩子的右孩子存在更新该节点的双亲if (SubLR ! nullptr)SubLR-_parent parents;// 60 作为 30的右孩子SubL-_right parents;// 因为60可能是棵子树因此在更新其双亲前必须先保存60的双亲Node* ppnode parents-_parent;// 更新60的双亲 parents-_parent SubL;// 更新30的双亲SubL-_parent ppnode;// 如果60是根节点更新指向根节点的指针if (_root parents){_root SubL;SubL-_parent nullptr;}else{ // 如果60是子树可能是其双亲的左子树也可能是右子树if (parents ppnode-_left)ppnode-_left SubL;elseppnode-_right SubL;}// Renewal balance factorparents-_bf 0;SubL-_bf 0;
}2. 新节点插入较高右子树的右侧—右右左单旋 实现及情况考虑可参考右单旋
void RotateL(Node* parents)
{Node* SubR parents-_right;Node* SubRL SubR-_left;parents-_right SubRL;if (SubRL ! nullptr)SubRL-_parent parents;SubR-_left parents;Node* ppnode parents-_parent;parents-_parent SubR;SubR-_parent ppnode;if (_root parents){_root SubR;SubR-_parent nullptr;}else{if (parents ppnode-_left)ppnode-_left SubR;elseppnode-_right SubR;}// Renewal balance factorparents-_bf 0;SubR-_bf 0;
}3. 新节点插入较高左子树的右侧—左右先左单选再右单旋 将双旋变成单旋后再旋转即先对30进行左单旋然后再对90进行右单旋旋转完成后再考虑平衡因子的更新。 旋转之前先看60的平衡因子是多少旋转结束以后根据60的平衡因子更新结果。 这里平衡因子的更新有三种情况 旋转之前60的平衡因子为-1 旋转之前60的平衡因子为1 旋转之前60的平衡因子为0
从这三张图中可以发现不管旋转之前60的平衡因子是多少最后都会变成0在单旋中已经将它置0所以我们只用观察3090 的平衡因子。而不管这棵树怎么变它必定会遵守搜索二叉树的规则所以在这里我只是用了一个示例向大家展示这三种情况。不管这棵树的形状是什么样的只要它满足搜索二叉树的规则那么左右双旋只会有这几种情况。
// 旋转之前60的平衡因子可能是-1/0/1旋转完成之后根据情况对其他节点的平衡因子进行调整
void RotateLR(Node* parents)
{Node* SubL parents-_left;Node* SubLR SubL-_right;// 旋转之前保存pSubLR的平衡因子旋转完成之后需要根据该平衡因子来调整其他节点的平衡因子int bf SubLR-_bf;// 先对30进行左单旋RotateL(SubL);// 再对90进行右单旋RotateR(parents);// Renewal balance factorif (bf 0){parents-_bf 0;SubL-_bf 0;}else if (bf 1){parents-_bf 0;SubL-_bf -1;}else if (bf -1){parents-_bf 1;SubL-_bf 0;}
}4. 新节点插入较高右子树的左侧—右左先右单旋再左单旋 这里与左右双旋相似将双旋变成单旋后再旋转即先对90进行右单旋然后再对30进行左单旋旋转完成后再考虑平衡因子的更新。 旋转之前先看60的平衡因子是多少旋转结束以后根据60的平衡因子更新结果。 这里平衡因子的更新有三种情况 旋转之前60的平衡因子为1 旋转之前60的平衡因子为-1 旋转之前60的平衡因子为0
void RotateRL(Node* parents)
{Node* SubR parents-_right;Node* SubRL SubR-_left;int bf SubRL-_bf;RotateR(SubR);RotateL(parents);// Renewal balance factorif (bf 0){parents-_bf 0;SubR-_bf 0;}else if (bf 1){parents-_bf -1;SubR-_bf 0;}else if (bf -1){parents-_bf 0;SubR-_bf 1;}
}总结 假如以parent为根的子树不平衡即parent的平衡因子为2或者-2分以下情况考虑
parent的平衡因子为2说明parent的右子树高设parent的右子树的根为SubR 当SubR的平衡因子为1时执行左单旋 当SubR的平衡因子为-1时执行右左双旋parent的平衡因子为-2说明parent的左子树高设parent的左子树的根为SubL 当SubL的平衡因子为-1时执行右单旋 当SubL的平衡因子为1时执行左右双旋 旋转完成后原parent为根的子树个高度降低已经平衡不需要再向上更新。
AVL树的旋转只有以上情况不可能会出现其他情况了。 AVL树的验证 AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步
验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确
bool Isbalance()
{int Hight 0;return _Isbalance(_root, Hight);
}
// 为了提高效率,可以走后序来计算每个节点的左子树和右子树的高度差为多少
// 通过Hight来保存每个节点的最高的子树的高度为多少
bool _Isbalance(Node* root, int Hight)
{if (root nullptr)return true;int leftHight 0;int rightHight 0;if (!_Isbalance(root-_left, leftHight) || !_Isbalance(root-_right, rightHight)){// 如果root的左子树或者右子树不平衡,就直接返回falsereturn false;}// 判断每个节点的左右子树高度差的绝对值不超过1if (abs(rightHight - leftHight) 2){std::cout balance factor error, the tree is unbalanced\n;return false;}// 判断每个节点的右子树的最大高度与左子树的最大高度的差值是否等于该节点的平衡因子else if (rightHight - leftHight ! root-_bf){std::cout root-_data the balance factor is wrong\n;return false;}// 保存左子树和右子树较高的高度Hight leftHight rightHight ? leftHight 1 : rightHight 1;return true;
}这段代码是随机生成10000个数插入到我自己写的一棵AVL树中插完这10000个树以后我对这棵树进行了一下判断是否平衡结果是平衡的证明我的插入逻辑是没有问题的我测试了不止这一组数据。 AVL树的删除 因为插入删除比较复杂我在这里就写一个大致思路具体代码我上传到了git上。
因为AVL树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不 过与插入不同的是删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。
这里更新平衡因子的逻辑与插入更新平衡因子的逻辑恰恰是相反的。 删除节点会影响删除节点的部分祖先如果是删除根节点也会找一个可以替代的节点交换值再删除具体可以参考搜索二叉树的删除部分。 更新原则
c是p的左边p-_bfc是p的右边p-_bf--
是否要继续更新取决于p的高度是否变化是否会影响爷爷节点。
在上面这张图的基础上删除7 在上面这张图的基础上再删除3 在上面这张图的基础上再删除14
从上面三个动图可以分析出
更新后p-_bf 1 / -1p所在的子树高度不变不会影响爷爷。说明更新前p-_bf是0p的两边是均衡的p的有一边删除了p变得不均衡但不违反规则p的高度不变不会影响爷爷更新结束。更新后p-_bf 0p所在的子树的高度变了会影响爷爷。说明更新前p-_bf 1 / -1p的有一边删除了p的左右变得均衡p的高度变了会影响爷爷继续往上更新。更新后p-_bf 2 / -2说明p所在的子树违反了平衡规则需要进行旋转处理。 AVL树的性能与源码 AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即 l o g 2 ( N ) log_2(N) log2(N)。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
源码地址https://gitee.com/ASL498/data-structure/tree/master/AVLTree
