网站开发销售提成,网站投诉平台,如何注册有限公司,江苏省质量建设厅网站一、AVL树
不同搜索的对比#xff1a;1.暴力搜索时间复杂度是O(N)#xff1b;2.二分查找的时间复杂度是O(lgN)#xff0c;但是伴随着有序#xff0c;插入删除挪动数据的成本极高#xff1b;3.二叉搜索的时间复杂度是高度次数#xff0c;极端场景会退化为类似链表时间…一、AVL树
不同搜索的对比1.暴力搜索时间复杂度是O(N)2.二分查找的时间复杂度是O(lgN)但是伴随着有序插入删除挪动数据的成本极高3.二叉搜索的时间复杂度是高度次数极端场景会退化为类似链表时间复杂度是O(N)/O(lgN)4.平衡二叉搜索树5.多叉平衡搜素树6.哈希表快速搜索
平衡二叉搜索树有avl树和红黑树
1.1概念
AVL树又叫做高度平衡二叉搜索树
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过 1( 需要对树中的结点进行调整 )即可降低树的高度从而减少平均搜索长度。
AVL树要不是空树要不然就是1.左右子树都是AVL树平衡因子(右子树高度减去左子树高度)的绝对值小于等于1
满二叉树就是最平衡的AVL树
1.2AVL树的模拟实现
1.2.1插入原理 先创建搜索二叉树然后更新平衡因子然后解决平衡错误(旋转解决)
1.左子树插入会使得父亲的平衡因子–右子树会使得父亲的平衡因子平衡因子只会影响祖先
2.平衡因子变为0说明树的高度没有发生变化其他祖先的平衡因子不需要发生变化变为正负一才需要沿着祖先路径parent和cur向上调整
3.插入一个节点是平衡因子默认就是0
4.若平衡因子是2或者-2就不平衡了需要旋转旋转要注意1.保持子树是搜索树2.变成平衡树且降低整棵树的高度即左单旋对于右子树过高向左旋转使得parent-rightcur-left,cur-leftparent强行让parent 节点向下走一截旋转之后的高度相较于插入之前是没有变化的。在旋转的过程中除了更新平衡因子还需要更新parent_。右单旋类似
5更新到平衡因子为0或者旋转结束或者更新到根节点就插入结束
旋转原理插入前平衡因子是1/-1 h是子树的高度h是1或者0和之前是一样的如果h是2则a、b子树可以是 但是c只能是第三种因为第1和第2种都不会影响到30和60节点的平衡因子一共有36种可能的插入情况。即无法穷尽但是核心规则是不变的。
双旋
当parent与cur的平衡因子为异号时即是折线就是双旋否则就是直线单旋
右左双旋 h0就是简单的直线h1就是在60的左右叶子节点插入都会使得parent异常h2a和d可以是上述任意三种情况bc是一个节点。
先90为旋转点进行右旋然后30为旋转点进行左旋。即第一次旋转变成直线左单旋第二次单旋变成平衡。要注意双旋之后要更新平衡因子。
观察发现双旋的结果本质就是60的左给30右给90并且3090做了60的左右。
更新平衡因子分三种情况1、插入元素后对于30、60、9060的平衡因子为-1说明在60的左子树插入最终会使得60的右的平衡因子为1其他为02、60平衡因子为1则60左的平衡因子为-13、60的平衡因子为0则60左右的平衡因子为0。
但是双旋存在问题。学会使用自己写一个辅助程序帮助调试。对于循环可以if等于具体的值来打断点调试。
#pragma once#include cassertnamespace AvlTree
{template class K, class Vstruct AVLTreeNode{// 构造函数AVLTreeNode(const pairK, V kv) : kv_(kv), left_(nullptr), right_(nullptr), parent_(nullptr), bf_(0) {}// 成员pairK, V kv_;AVLTreeNodeK, V *left_;AVLTreeNodeK, V *right_;AVLTreeNodeK, V *parent_; // 三叉链便于旋转// 平衡因子int bf_;};template class K, class Vclass AVLTree{// 内嵌类型typedef AVLTreeNodeK, V node;public:// 默认构造函数AVLTree() : root_(nullptr) {}public:// 普通成员函数void rotatel(node *parent);void rotater(node *parent);void rotaterl(node *parent);void rotatelr(node *parent);bool insert(const pairK, V kv);int height(node *root);bool isavltree(){return _isavltree(root_);}void inorder(){_inorder(root_);}private:// 私有成员void _inorder(node *root);bool _isavltree(node *root);node *root_;};template class K, class Vvoid AVLTreeK, V::rotatel(node *parent){node *cur parent-right_;node *curleft cur-left_;parent-right_ curleft;node *ppnode parent-parent_;if (curleft)curleft-parent_ parent;parent-parent_ cur;cur-left_ parent;parent-bf_ 0;cur-bf_ 0;if (parent root_){root_ cur;cur-parent_ nullptr;}else{if (ppnode-left_ parent){ppnode-left_ cur;}else{ppnode-right_ cur;}cur-parent_ ppnode;}}template class K, class Vvoid AVLTreeK, V::rotater(node *parent){node *cur parent-left_;node *curright cur-right_;node *ppnode parent-parent_;parent-left_ curright;cur-right_ parent;if (curright)curright-parent_ parent;parent-parent_ cur;parent-bf_ 0;cur-bf_ 0;if (parent root_){root_ cur;cur-parent_ nullptr;}else{if (ppnode-left_ parent){ppnode-left_ cur;}else{ppnode-right_ cur;}cur-parent_ ppnode;}}template class K, class Vvoid AVLTreeK, V::rotaterl(node *parent){// 更新平衡因子node *cur parent-right_;node *curleft cur-left_;int bf curleft-bf_;rotater(parent-right_);rotatel(parent);if (bf 0){cur-bf_ 0;curleft-bf_ 0;parent-bf_ 0;}else if (bf -1){cur-bf_ 1;curleft-bf_ 0;parent-bf_ 0;}else if (bf 1){parent-bf_ -1;cur-bf_ 0;curleft-bf_ 0;}else{assert(false);}}template class K, class Vvoid AVLTreeK, V::rotatelr(node *parent){// 更新平衡因子node *cur parent-left_;node *curright cur-right_;int bf curright-bf_;rotatel(parent-left_);rotater(parent);if (bf 0){cur-bf_ 0;curright-bf_ 0;parent-bf_ 0;}else if (bf -1){cur-bf_ 0;curright-bf_ 0;parent-bf_ 1;}else if (bf 1){parent-bf_ 0;cur-bf_ -1;curright-bf_ 0;}else{assert(false);}}template class K, class Vbool AVLTreeK, V::insert(const pairK, V kv){if (root_ nullptr){root_ new node(kv);return true;}node *cur root_;node *parent cur;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;}}cur new node(kv);if (kv.first parent-kv_.first){parent-right_ cur;}else{parent-left_ cur;}cur-parent_ parent;// 控制平衡,更新平衡因子while (parent){if (cur parent-left_){parent-bf_--;}else{parent-bf_;}if (!parent-bf_){break;}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);break;}else if (parent-bf_ -2 cur-bf_ -1){// 右单旋rotater(parent);break;}else if (parent-bf_ 2 cur-bf_ -1){// 右左双旋rotaterl(parent);break;}else if (parent-bf_ -2 cur-bf_ 1){// 左右双旋rotatelr(parent);break;}else{assert(false);}}else{assert(parent-bf_ 2 parent-bf_ -2);}}return true;}template class K, class Vint AVLTreeK, V::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;}template class K, class Vbool AVLTreeK, V::_isavltree(node *root){if (root nullptr){return true;}int leftheight height(root-left_);int rightheight height(root-right_);if ((rightheight - leftheight) ! root-bf_){cout 平衡因子异常: root-kv_.first : root-kv_.second : root-bf_ endl;return false;}return abs(rightheight - leftheight) 2 _isavltree(root-left_) _isavltree(root-right_);}template class K, class Vvoid AVLTreeK, V::_inorder(node *root){if (root nullptr){return;}_inorder(root-left_);cout root-kv_.first : root-kv_.second endl;_inorder(root-right_);}
}
