北京学生做兼职的网站,婚纱手机网站制作,周口建设企业网站公司,门户网站建设关键点AVL树
一、AVL树的概念 二叉搜索树虽可以缩短查找的效率#xff0c;但如果数据有序或接近有序二叉搜索树将退化为单支树#xff0c;查找元素相当于在顺序表中搜索元素#xff0c;效率低下。因此#xff0c;两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明…AVL树
一、AVL树的概念 二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法 AVL树又被称为高度平衡搜索二叉树当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)它的左右子树都是AVL树 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在log_2 n搜索时间复杂度O(log_2 n)。 二、AVL树节点的定义
template class K, class V
struct AVLTreeNode{ AVLTreeNodeK,V *_left; //指向左节点的指针 AVLTreeNodeK,V *_right; //指向右节点的指针 AVLTreeNodeK,V *_parent; //指向父节点的指针 pairK,V _kv; //存储元素键值对 int _bf; //平衡因子balance factor AVLTreeNode(const pairK,V kv) :_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0) {}
}; 三、AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为三步
按照二叉搜索树的方式插入新节点调整节点的平衡因子如果节点所在的二叉树不再平衡通过旋转恢复平衡。 template class K, class V
bool AVLTreeK,V::Insert(const pairK,V kv)
{//1.按照二叉搜索树的方式插入新节点if(_root nullptr){_root new Node(kv);return true;}Node *cur _root;Node *parent nullptr; //cur要向下一直遍历到null所以要记录父节点的指针while(cur ! nullptr){if(kv.first cur-_kv.first) {parent cur;cur cur-_right;}else if(kv.first cur-_kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if(kv.first parent-_kv.first){ parent-_right cur;}else{parent-_left cur;}cur-_parent parent; //不要忘了修改父节点指针//2.调整节点的平衡因子while(parent!nullptr) //只影响插入节点的所有祖先节点的平衡因子,parent不断向上一直遍历到根节点{//更新父节点的平衡因子//平衡因子右树的高度-左树的高度if(cur parent-_right){parent-_bf; //插入右节点bf }else{--parent-_bf; //插入左节点bf--}//更新后检测双亲的平衡因子if(parent-_bf 0){//由1/-1更新为0说明以父节点为根的二叉树高度不变无需继续向上调整。 break; }else if(abs(parent-_bf) 1){//由0更新为1/-1说明以父节点为根的二叉树高度增加了一层需要继续向上调整。 parent parent-_parent;cur cur-_parent;}else if(abs(parent-_bf) 2){//3.更新后为2/-2说明parent所在的子树已经不平衡了需要通过旋转恢复平衡。//......//下面的内容会有讲解↓↓↓}else{//除非代码有错否则不可能有其他情况。assert(false);}}return true;
}四、AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种
4.1 左单旋
新节点插入较高右子树的右侧—右右左单旋 解释
上图在插入前AVL树是平衡的。a,b,c是高度为h的AVL子树(h0)。新节点插入到60的右子树c使c树增加了一层最终导致以30为根的二叉树不平衡。要让30平衡就需要将30向左旋转将60提上去。让30的左子树增加一层右子树减少一层。也就是让30做60的左子树。如果60有左子树bb树的根一定大于30小于60刚好做30的右子树。旋转完成后更新节点的平衡因子即可。在旋转过程中有以下几种情况需要考虑 60节点的左子树b可能存在也可能为空。30可能是根节点也可能是子树 如果是根节点旋转完成后要更新根节点指针_root。如果是子树可能是某个节点的左子树也可能是右子树。要更新父节点的指针。
template class K, class V
void AVLTreeK,V::RotateL(Node *parent){ //parent对应30Node *subR parent-_right; //subR对应60Node *subRL subR-_left; //subRL对应b树的根Node *ppNode parent-_parent; //记录30的父节点便于旋转后进行连接。//30和b树进行连接parent-_right subRL; if(subRL ! nullptr) //b树可能为空{subRL-_parent parent;}//30和60重新连接subR-_left parent;parent-_parent subR;//60和30的父节点进行连接//如果30是根节点更新根节点指针_root指向60//if(_root parent)if(ppNode nullptr){_root subR;}else{//60和30的父节点进行连接先要确定30是父节点的左子树还是右子树if(ppNode-_left parent){ppNode-_left subR;}else{ ppNode-_right subR;}}subR-_parent ppNode;//更新平衡因子进过旋转60和30的平衡因子变为0subR-_bf parent-_bf 0;
}4.2 右单旋
新节点插入较高左子树的左侧—左左右单旋 详细解释参考左单旋。
template class K, class V
void AVLTreeK,V::RotateR(Node *parent){Node *subL parent-_left;Node *subLR subL-_right;Node *ppNode parent-_parent;parent-_parent subL;subL-_right parent; parent-_left subLR;if(subLR ! nullptr)subLR-_parent parent;//if(_root parent)if(ppNode nullptr){_root subL;}else{if(ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}}subL-_parent ppNode;subL-_bf parent-_bf 0;
}旋转的作用1. 平衡二叉树 2. 降低二叉树高度恢复到插入之前的高度h2 4.3 左右双旋
新节点插入较高左子树的右侧—左右先左单旋再右单旋 将双旋变成单旋后再旋转即先对30进行左单旋然后再对90进行右单旋旋转完成后再考虑平衡因子的更新。
左右双旋又能细分为3种情况
a,b,c,d是空树60是新增引发双旋。在b树插入新增引发双旋。在c树插入新增引发双旋。
三种情况的双旋过程不变只是平衡因子的更新需要分别处理 双旋的关键在于更新平衡因子30,60,90三个节点的平衡因子都在两次单旋过程中被错误的置为0因为并没要满足单旋的条件。要根据以上三种不同的情况重新调整三个节点的平衡因子。如何区分三种不同的情况根据旋转之前60的平衡因子确认。
template class K, class V
void AVLTreeK,V::RotateLR(Node *parent){ //parent对应90Node *subL parent-_left; //subL对应30Node *subLR subL-_right; //subLR对应60int bf subLR-_bf; //记录旋转之前60的平衡因子RotateL(subL); //30左单旋RotateR(parent); //90右单旋//更新平衡因子subLR-_bf 0; //60的平衡因子一定为0 switch(bf) //根据旋转之前60的平衡因子确认属于那种情况{case 1:subL-_bf -1;parent-_bf 0;break;case -1:subL-_bf 0;parent-_bf 1;break;case 0:subL-_bf 0;parent-_bf 0;break;default://除非代码有错否则不可能有其他情况。assert(false);break;}
}双旋最终的结果是将60作为二叉树的根60的左右子树分别作了30和90的右左子树。30和90作了60的左右子树。 4.4 右左双旋
新节点插入较高右子树的左侧—右左先右单旋再左单旋 详细解释参考左右双旋。
template class K, class V
void AVLTreeK,V::RotateRL(Node *parent){Node *subR parent-_right;Node *subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent); //更新平衡因子 subRL-_bf 0;switch(bf){case 1:subR-_bf 0;parent-_bf -1;break;case -1:subR-_bf 1;parent-_bf 0;break;case 0:subR-_bf 0;parent-_bf 0;break;default://除非代码有错否则不可能有其他情况。assert(false);break;}
}双旋最终的结果是将60作为二叉树的根60的左右子树分别作了30和90的右左子树。30和90作了60的左右子树。 4.5 分情况旋转 else if(abs(parent-_bf) 2){ //3.更新后为2/-2说明parent所在的子树已经不平衡了需要通过旋转恢复平衡。if(parent-_bf 2 cur-_bf 1) //右右左单旋{RotateL(parent);}else if(parent-_bf 2 cur-_bf -1) //右左右左双旋{RotateRL(parent);}else if(parent-_bf -2 cur-_bf -1) //左左右单旋{RotateR(parent); }else if(parent-_bf -2 cur-_bf 1) //左右左右双旋{RotateLR(parent);}else{//除非代码有错否则不可能有其他情况。assert(false);}break; //注意旋转完成后原parent为根的子树个高度降低已经平衡不需要再向上更新。}总结 假如以parent为根的子树不平衡即parent的平衡因子为2或者-2分以下情况考虑 parent的平衡因子为2说明parent的右子树高设parent的右子树的根为subR 当subR的平衡因子为1时(右右)执行左单旋 当subR的平衡因子为-1时(右左)执行右左双旋 parent的平衡因子为-2说明parent的左子树高设parent的左子树的根为subL 当subL的平衡因子为-1是(左左)执行右单旋 当subL的平衡因子为1时(左右)执行左右双旋
经过旋转后可以直接break因为经过旋转插入元素前后子树的高度未发生变化都是h2不需要再调整上层节点的平衡因子。一次插入最多一次旋转。
所以AVL树插入元素的时间复杂度找插入位置O(log_2N) 更新平衡因子O(log_2N) 旋转O(1) O(log_2N)。 五、AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树 验证其为平衡树 每个节点子树高度差的绝对值不超过1 节点的平衡因子是否计算正确 template class K, class V
bool AVLTreeK,V::_Isbalance(Node *root){if(root nullptr) return true; //注意空树也是AVL树int lh _Height(root-_left); //_Height返回二叉树的高度int rh _Height(root-_right);int diff rh-lh; //计算得到平衡因子 if(diff ! root-_bf){cout Key: root-_kv.first bf: root-_bf 平衡因子异常 endl;return false;}return abs(diff) 2 _Isbalance(root-_left) _Isbalance(root-_right);
}测试用例 //插入一两组序列测试
void Test1(){//int arr[] {16, 3, 7, 11, 9, 26, 18, 14, 15};int arr[] {1,2,3,4,5,6,7,8,9,10};AVLTreeint, int avl;for(auto e : arr){avl.Insert(make_pair(e, e)); }avl.Inorder();cout Isbalance: avl.Isbalance() endl;
}//插入10000个随机值测试
void Test2(){srand(time(NULL));AVLTreeint, int avl;const int N 10000;for(int i 0; iN; i){int x rand();avl.Insert(make_pair(x, i));}cout Isbalance: avl.Isbalance() endl;
}六、AVL树的删除(了解)
AVL树节点的删除步骤如下
在AVL树中找到要删除的节点。如果要删除的节点是叶子节点直接删除即可。如果要删除的节点只有一个子节点先使前驱节点指向该节点的子节点然后删除该节点。如果要删除的节点有两个子节点需要找到该节点的替换节点即该节点右子树中最小的节点或左子树中最大的节点然后交换与替换节点的值最后删除替换节点。在删除节点后需要更新从该节点到根节点路径上所有节点的平衡因子并进行平衡调整使得整棵树重新满足AVL树的性质。
删除操作的平衡调整方法和AVL树的插入操作相似但在实现时需要注意一些细节上的差异。需要注意的是删除操作可能会导致多个节点的平衡因子发生变化因此需要一直向上循环更新和平衡调整直到根节点。具体实现大家可以参考《算法导论》或《数据结构-用面向对象方法与C描述》殷人昆版。 七、AVL树的性能 AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即log_2 (N)。 但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。 因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树。但一个结构经常修改就不太适合。
