专门做水果的网站昆明软件开发公司推荐

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

专门做水果的网站,昆明软件开发公司推荐,最新新闻热点事件看法,一个公司可以做两个网站不文章目录 1.AVL树1.1 AVL树的概念1.2 AVL树节点的定义1.3 AVL树的插入1.4 AVL树的旋转1.4.1 左单旋1.4.2 右单旋1.4.3 右左双旋1.4.4 左右双旋 1.5 AVL树的平衡验证1.6 AVL树的删除1.7 AVL树的性能 1.AVL树 在前面#xff0c;我们已经介绍过了二叉搜索树#xff0c;也了解到… 文章目录 1.AVL树1.1 AVL树的概念1.2 AVL树节点的定义1.3 AVL树的插入1.4 AVL树的旋转1.4.1 左单旋1.4.2 右单旋1.4.3 右左双旋1.4.4 左右双旋 1.5 AVL树的平衡验证1.6 AVL树的删除1.7 AVL树的性能 1.AVL树 在前面我们已经介绍过了二叉搜索树也了解到二叉搜索树查找的效率非常的高。但是在数据有序或接近有序时它就会退化成单边树那样效率就变得非常低了。所以我们也一直说二叉搜索树的搜索的时间复杂度是O(N)(高度次)并不是O(log2N)。
因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理即采用平衡树来实现。 1.1 AVL树的概念 由于二叉搜索树可能会退化两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。 为什么要求左右子树的高度之差不超过1就可以呢 对于所有形状的子树来说如果他有2n-1个节点那它就可以保持绝对的平衡如果他有2n (n 1)个节点就无法做到绝对的平衡最好的结果就是子树高度相差一。 一棵AVL树要么是空树要么是具有以下性质的二叉搜索树 它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果他有n个节点其高度可保持在log2N搜索的时间复杂度就是log2N。 1.2 AVL树节点的定义 为了方便确认一棵树是否是AVL树我们在节点中定义一个平衡因子通过它来记录每棵树左右子树的高度。 如果右子树比左子树高一层那平衡因子就是1如果左右子树一样高那平衡因子就是0如果左子树比右子树高一层那平衡因子就是-1。此时AVL树的性质都没有被打破。 当左子树比右子树高两层那平衡因子就是-2或者右子树比左子树高两层平衡因子就是2此时AAVL树的性质就被打破了需要调整。 在调整失衡的AVL树时我们需要频繁的访问其父节点因此我们给每个节点定义一个指向父亲的指针 templateclass K, class V struct AVLTreeNode {pairK, V _kv; //存放数据AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _prev; //指向当前节点的父亲int _bf;//平衡因子AVLTreeNode(const pairK,V kv):_kv(kv),_left(nullptr),_right(nullptr),prev(nullptr),_bf(0){} };1.3 AVL树的插入 AVL树的插入与普通二叉搜索树的插入基本一致。唯一的区别就是AVL树插入节点后需要判断AVL树是否失衡存在失衡就需要调整。 我们平衡因子是使用右子树的高度-左子树的高度因此如果新节点插入到父节点的右边那父亲的平衡因子1如果新节点插入到父亲节点的左边那父亲的平衡因子-1。 对于情况二来说新节点的插入不会影响其祖先的平衡因子的改变因为子树的高度没有改变。 对于情况一来说新节点的插入会影响其祖先的平衡因子的改变因为子树的高度变高了。 所以对于情况一来说我们新插入节点后还要观察其祖先的平衡因子是否变化变化后是否需要调整。 那么下面我们就先将节点插入到树中 bool insert(const pairK, V kv){//插入前是空树if (_root nullptr){//新插入的节点就是根_root new Node(kv);_root-_prev nullptr;return true;}else{Node* cur _root;Node* parent nullptr;//寻找插入位置while (cur){if (cur-_kv.first kv.first){parent cur;//记录父节点以便后序连接cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;//节点已经存在插入失败}}//已找到了插入位置cur new Node(kv);//判断连接在父亲的哪一侧if (parent-_kv.first kv.first)parent-_right cur;elseparent-_left cur;cur-_prev parent;//指向父亲//判断树是否失衡//…}}更新父亲/祖先的平衡因子 //判断树是否失衡while (parent){//更新父亲的平衡因子if (parent-_left cur)parent-_bf–;elseparent-_bf;if (parent-_bf 0)//属于情况二不影响祖先break;//情况一影响祖先的平衡因子需要继续更新else if (parent-_bf 1 || parent-_bf -1){cur parent;parent cur-_prev;}else if (parent-_bf 2 || parent-_bf -2){//旋转处理break;}else{assert(false);//平衡因子异常了}}1.4 AVL树的旋转 AVL树的旋转分为四种情况 左单旋右单旋左右双旋右左双旋 下面我们对这四种情况具体分析 1.4.1 左单旋 新节点插入到较高右子树的右侧- -左单旋 在旋转过程中有以下几种情况需要考虑 7节点的左孩子可能存在也可能不存在6可能是根节点也可能是子树 如果是根节点旋转完成后根节点就是7如果是子树可能是某个节点的左子树也可能是右子树需要判断以后连接
void RotateL(Node* parent){Node* subR parent-_right;//父亲的右孩子Node* subRL subR-_left;//右孩子的左孩子//升高度连孙子parent-_right subRL;if (subRL)subRL-_prev parent;Node* parentPrev parent-_prev;//降高度变父亲subR-_left parent;parent-_prev subR;//连接旋转后的子树subR-_prev parentPrev;if (parentPrev nullptr){//如果原父亲就是根旋转后的儿子变根_root subR;}else{//原父亲是子树判断儿子连接在哪一边if (parentPrev-_left parent)parentPrev-_left subR;elseparentPrev-_right subR;}//更新平衡因子subR-_bf 0;parent-_bf 0;}1.4.2 右单旋 新节点插入到较高左子树的左侧- - 右旋 在旋转过程中有以下几种情况需要考虑 5节点的右孩子可能存在也可能不存在6可能是根节点也可能是子树 如果是根节点旋转完成后根节点就是5如果是子树可能是某个节点的左子树也可能是右子树需要判断以后连接 void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;//升高度连孙子parent-_left subLR;if (subLR)subLR-_prev parent;Node* parentPrev parent-_prev;//降高度变父亲subL-_right parent;parent-_prev subL;//新父亲指向前subL-_prev parentPrev;if (nullptr parentPrev){//如果原父亲就是根旋转后的儿子变根_root subL;}else{//原父亲是子树判断儿子连接在哪一边if (parentPrev-_left parent)parentPrev-_left subL;elseparentPrev-_right subL;}subL-_bf 0;parent-_bf 0;}1.4.3 右左双旋 新节点插入到较高右子树的左侧- -右左双旋 所以为了解决这种情况我们可以将这种歪脖树先变成一棵单边树然后再进行单旋即可。
为了满足所有情况我们下面使用抽象图再画一遍 观察上图我们可以发现双旋就是一种抛弃自己的孩子独自登基的感觉因此对于旋转后平衡因子的改变取决于新节点插入到哪一边最后又到哪里去。 void RotateRL(Node* parent){//由于单旋会改变节点的位置以及平衡因子所以提前记录Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);//修改平衡因子if (bf 0)//subRL插入前是空{parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else if (bf 1)//subRL之前是一棵树新节点插入其 右侧{parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else //subRL之前是一棵树新节点插入其 左侧{parent-_bf 0;subR-_bf -1;subRL-_bf 0;}}1.4.4 左右双旋 新节点插入到较高左子树的右侧–左右双旋 最简单的情况2的右子树插入前为空
抽象图 跟右左双旋基本一样这里就不赘述了咱们直接开旋。 平衡因子的改变也需要小心。 void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 0) // subLR插入前为空{parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else if (bf 1) //subLR是一棵树新节点插入到树的 右侧{parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else //subLR是一棵树新节点插入到树的 左侧{parent-_bf 1;subL-_bf 0;subLR-_bf 0;}}下面就是更新平衡因子的整体思路 //判断树是否失衡while (parent){//更新父亲的平衡因子if (parent-_left cur)parent-_bf–;elseparent-_bf;if (parent-_bf 0)//属于情况二不影响祖先break;//情况一影响祖先的平衡因子需要继续更新else if (parent-_bf 1 || parent-_bf -1){cur parent;parent cur-_prev;}else if (parent-_bf 2 || parent-_bf -2){//旋转处理//左单旋// p cur// cur — p new// newif (parent-_bf 2 cur-_bf 1)RotateL(parent);//右单旋// p cur// cur — new p// newelse if (parent-_bf -2 cur-_bf -1)RotateR(parent);//右左双旋// p p cur// cur – cur – p new// new newelse if (parent-_bf 2 cur-_bf -1)RotateRL(parent);//左右双旋// p p cur// cur – cur – new p // new newelse if (parent-_bf -2 cur-_bf 1)RotateLR(parent);elseassert(false);break;//旋转后以parent为根的树已经平衡无需继续向上更新}else{assert(false);//平衡因子异常了}总结 假如以Parent为根的子树不平衡即Parent的平衡因子为2或者-2分以下情况考虑 Parent的平衡因子为2说明Parent的右子树高设Parent的右子树的根为SubR 当SubR的平衡因子为1时执行左单旋当SubR的平衡因子为-1时执行右左双旋 Parent的平衡因子为-2说明Parent的左子树高设Parent的左子树的根为SubL 当SubL的平衡因子为-1是执行右单旋当SubL的平衡因子为1时执行左右双旋
旋转完成后原Parent为根的子树个高度降低已经平衡不需要再向上更新。 1.5 AVL树的平衡验证 AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树 验证其为平衡树 每个节点子树高度差的绝对值不能超过1节点的平衡因子是否计算正确 int Height(Node* root){if (root nullptr)return 0;int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}bool _isBalanceTree(){return isBalanceTree(_root);}bool isBalanceTree(Node* root){if (root nullptr)//空树也是平衡二叉搜索树return true;int leftHeight Height(root-_left);int rightHeight Height(root-_right);int gap rightHeight - leftHeight; //计算root的平衡因子// 如果计算出的平衡因子与root的平衡因子不相等或者//root平衡因子的绝对值超过1则一定不是AVL树if (gap ! root-_bf || (gap 1 || gap -1)){return false;}return isBalanceTree(root-_left) isBalanceTree(root-_right);}1.6 AVL树的删除 因为AVL树也是二叉搜索树可按照二叉搜索树的方式将节点删除(分析有无左右孩子若仅有一个孩子则直接将删除节点连接孩子若有两个孩子将删除节点替换为删除节点的左子树的最大或右子树的最小)然后再更新平衡因子只不过与插入不同的是删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。 1.7 AVL树的性能 AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即log2N。 但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。 因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。