wordpress能做几个域名的301,网站优化北京多少钱,广告策划宣传公司,河北建设集团在哪个网站采购前言
学习了普通二叉树#xff0c;发现普通二叉树作用不大#xff0c;于是我们学习了搜索二叉树#xff0c;给二叉树新增了搜索、排序、去重等特性#xff0c; 但是#xff0c;在极端情况下搜索二叉树会退化成单边树#xff0c;搜索的时间复杂度达到了O(N)#xff0c;这…前言
学习了普通二叉树发现普通二叉树作用不大于是我们学习了搜索二叉树给二叉树新增了搜索、排序、去重等特性 但是在极端情况下搜索二叉树会退化成单边树搜索的时间复杂度达到了O(N)这是十分不利的 所以牛人们又提出了新的数据结构AVL树平衡搜索二叉树给搜索二叉树新增了平衡的特性控制左右子树的高度是搜索二叉树处于平衡的状态避免出现极端情况。 AVL树的发明者是两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis为了几年他们在1962年提出该数据结构就命名为AVL树。 AVL树的特性
AVL树要求任意节点的左右子树的高度差的绝对值不超过1. 为什么拥有该特性AVL树就可以保持平衡呢这里需要数学证明就不解释了理解原理后就很容易理解。 一棵AVL树是具有以下性质的二叉搜索树 它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 注意在这里我们引入一个变量平衡因子balance factor用来记录左右子树的高度差 这里我们记录右子树的高度减左子树的高度。 当然也可以有其他的思路来替代平衡因子。 AVL树节点的定义以KV型为例
templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK,V* _left nullptr;//左子节点AVLTreeNodeK, V* _right nullptr;//右子节点AVLTreeNodeK, V* _parent nullptr;//父亲节点pairK, V _kv;//数据int _bf 0;//平衡因子AVLTreeNode(const pairK, V kv):_kv(kv){}
};注意AVL树使用三叉链实现多了一个parent指针用来记录父亲节点方便使用。 AVL树的插入核心
AVL树是在搜索二叉树上面进行升级所以查找的方法和搜索二叉树类似大了就向右子树走小了就往左子树走。
因为这里多了parent指针和bf在插入之后都需要进行维护。天下没有白吃的午餐使用的时候方便维护起来就麻烦了QAQ
parent指针处理起来很简单我们这里主要讲bf如何控制。
bf有三种取值 0 - 1 1 当我们在节点的右侧插入的时候节点的bf在节点的左侧插入的时候节点的bf–。 在右边插入右子树的高度增加bf在左边插入的时候左子树的高度增加bf– 这是毫无疑问的以下都基于此。
OK更新完当前节点之后bf就维护好了吗 哪有这么简单QAQ 在插入后cur的bf更新为1仅仅如此吗 看这张图parent的bf也要从1变成2了。 所以在更新完cur节点的bf后还需要根据情况确定是否要继续向上更新 具体是否要更新主要是看子树的高度有没有发生变化
有哪些情况呢 cur插入后更新为0 说明原来是1 或者 -1在较短的那一条边上新增了新节点将cur节点变平衡了 这样的话那高度就没有增加不会影响到子树的高度就不需要向上更新bf了。cur插入后更新为 1-1 说明原来是0原来是平衡的插入新节点后破坏了平衡子树高度发生了变化 所以需要向上更新bf。cur插入后更新为 2-2 当更新为2-2后发现违反了AVL树的规则不再是一颗AVL树我们就需要进 行特殊操作来维护AVL树的性质了。这里我们采用旋转 AVL树的旋转最难的部分
AVL树的旋转是AVL树这个数据结构的亮点掌握了这一点之后才会理解这种数据结构有多么精妙。
从深层上看AVL树的旋转分为四种情况我们画图来分析。由于实际情况太多太多我们这里画抽象图
左单旋 这里h 0 我们在最右边插入一个节点使AVL树的右侧完全倾斜那么我们就需要向左侧旋转了。 如何向左旋转呢
我们将三个需要用到的节点命名一下分别为parentsubR以及subRL 根据搜索二叉树的性质我们知道subRL parent 但是小于subR所以就可以进行左单旋而不会破坏搜索的性质 左单旋就是 先将subRL插入到parent的右边 接着将parent插入到subR的左边 成功旋转之后图形变成下面的样子 这样左右子树的高度就一样了重新将AVL树调整平衡了 这里还有非常多的代码细节例如空指针parent指针的维护等等需要处理这里大家可以先尝试根据思路写出代码再跟后面的代码进行比较看看是否写对了。
这里只简单讲一下平衡因子的维护。 可以看到在左单旋只会影响parent和subR两个节点的bf且旋转后皆为0故不用向上继续调整。 右单旋
右单旋和左单旋类似是对称的这里只简单画出抽象图相信读者能够自己理解。 右单旋就是处理左边完全倾斜的情况向右边旋转进而调整平衡。 代码依旧在文末尾给出。 右左双旋
顾名思义先右单旋后左单旋构成右左双旋。 相信聪明的小伙伴在看到左单旋和右单旋的时候就会发现这两种情况都是插入在最右边和最左边造成完全倾斜。 而插入在右子树的左边和左子树的右边都没有列举出来。
这里右左双旋就是应对插入在右子树的左边这种情况的显然左右双旋就是应对插入在左子树的右边那种情况的这里讲右左双旋左右双旋留给大家自己思考。 左单旋和右单旋都不适合这种情况根本原因在于这种情况并不是完全倾斜很简单嘛 你不是完全倾斜我强行让你变成完全倾斜不就可以使用左单旋或者右单旋了嘛。 对于这种情况我们可以看到是subRL太高了导致的不平衡我们将subRL旋转到subR的位置岂不是可以造成完全倾斜了吗
这右单旋不就来了嘛使用右单旋就将subRL的右插入到subR的左再将subR插入到subRL的右即可。
右单旋完了之后就是下面的图形 映入眼帘的就是右边太高了出现了完全倾斜直接左单旋调整平衡即可。
这里同样有很多代码细节要维护好parent和bf以及处理好空指针的特殊情况。
这里还是只简单讲一下bf的维护 我们以终为始只看旋转前和旋转后的两幅图。 我们可以看到只有三个节点60 30 90的bf发生了变化。 也就是只有parentsubRsubRL三个节点的bf发生了变化。 这里最后subRL和subR的bf 变成了0parent的bf变成了-1。 但是一定是这样吗 这中情况是在c子树上插入新节点如果在b上插入新节点。 a和b的高度都是hparent的bf就是0c的高度是h-1d的高度是hsubR的bf就是1 问题就在于是在subRL的左子树插入还是右子树插入新节点。 如何分辨? 很简单去观察subRL的旋转前的bf 如果是1就是在右子树插入如果是-1就是在左子树插入 左右双旋
大体和右左双旋类似所以这里简单画个抽象图相信读者能够自行理解。
这里就是新节点插入在了左子树的右边导致不平衡先左单旋调整成完全倾斜在右单旋调整至平衡。 代码
#include assert.h
#include iostreamusing namespace std;namespace Avltree//命名空间名不能和类名相同不然会发生命名冲突
{templateclass K, class Vstruct AVLTreeNode{AVLTreeNodeK,V* _left nullptr;AVLTreeNodeK, V* _right nullptr;AVLTreeNodeK, V* _parent nullptr;pairK, V _kv;int _bf 0;//平衡因子AVLTreeNode(const pairK, V kv):_kv(kv){}};templateclass K,class Vclass AVLTree{typedef AVLTreeNodeK, V Node;private:Node* _root nullptr;//开始的时候要给空不然就是野指针了void RotateL(Node* parent)//左单旋{Node* subR parent-_right;Node* subRL subR-_left;Node* pparent parent-_parent;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;if (pparent nullptr){subR-_parent nullptr;_root subR;}else{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}subR-_parent pparent;}parent-_bf 0;subR-_bf 0;}void RotateR(Node* parent)//右单旋{Node* subL parent-_left;Node* subLR subL-_right;Node* pparent parent-_parent;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;if (pparent nullptr){subL-_parent nullptr;_root subL;}else{if (pparent-_left parent){pparent-_left subL;}else{pparent-_right subL;}subL-_parent pparent;}parent-_bf 0;subL-_bf 0;}void RotateRL(Node* parent){RotateR(parent-_right);RotateL(parent);}void RotateLR(Node* parent){RotateL(parent-_left);RotateR(parent);}void InOrder(Node* root){if (root nullptr)return;InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;InOrder(root-_right);}public:void inorder(){InOrder(_root);}bool find(const K key){Node* cur _root;while (cur){if (key cur-_kv.first){cur cur-_right;}else if (key cur-_kv.first){cur cur-_left;}else{return true;}}return false;}bool insert(const pairK, V kv){if (_root nullptr)//插入的时候要特殊处理空树{_root new Node(kv);return true;}Node* cur _root;Node* parent nullptr;while (cur){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;//如果已经在那就插入失败返回false}}//找到了开始插入cur new Node(kv);cur-_parent parent;if (kv.first parent-_kv.first)//插入的节点很大插在右边{parent-_bf;parent-_right cur;}else{parent-_bf--;parent-_left cur;}//插入完成调整平衡因子while (parent){if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){//开始旋转if (parent-_bf 2 cur-_bf 1)//右边太高了左单旋{RotateL(parent);}else if (parent-_bf -2 cur-_bf -1)//左边太高了右单旋{RotateR(parent);}else if (parent-_bf 2 cur-_bf -1)//右边高但是偏了{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateRL(parent);if (bf 0){parent-_bf subR-_bf subRL-_bf 0;}else if (bf 1){subRL-_bf subR-_bf 0;parent-_bf -1;}else if(bf -1){subRL-_bf parent-_bf 0;subR-_bf 1;}else{assert(false);}}else if (parent-_bf -2 cur-_bf 1)//左边高但是偏向右边{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateLR(parent);if (bf 0){parent-_bf subL-_bf subLR-_bf 0;}else if (bf 1){subL-_bf -1;parent-_bf subLR-_bf 0;}else if(bf -1){subLR-_bf subL-_bf 0;parent-_bf 1;}else{assert(false);}}}else{assert(false);//走到这里来就出现错误了}}return true;}};
}对于AVL树的删除和插入类似但是更加复杂些限于篇幅就暂且不讲AVL树的删除了感兴趣的读者可以参考《算法导论》和《数据结构用面向对象方法与C语言描述》殷人昆版。
