国外 平面设计 网站,舟山企业网站建设,seo云优化如何,平面设计广告设计引入
二叉搜索树有其自身的缺陷#xff0c;假如往树中 插入的元素有序或者接近有序#xff0c;二叉搜索树就会退化成单支树#xff0c;时间复杂度会退化成O(N)#xff0c;因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理#xff0c;即采用平衡树来实现。简…引入
二叉搜索树有其自身的缺陷假如往树中 插入的元素有序或者接近有序二叉搜索树就会退化成单支树时间复杂度会退化成O(N)因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理即采用平衡树来实现。简单来说就是之前二叉搜索树由于可能在某一个节点上一直深入按照最坏情况算这的时间复杂度就高了起来而AVL树这其中之一的平衡树
1.AVL树的概念 二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查 找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均 搜索长度 AVL树又称高度平衡二叉搜索树 任何AVL树都满足一下条件: 它的左右子树都是AVL树任何树及其子树的高度差(也就是平衡因子)的绝对值不超过1 比如 当然平衡因子不一定是必须的它只是一种控制方式(让我们更便捷地控制这棵树)
为何是不超过1而不是0呢0不是更加平衡吗
由于树的节点是一个个插入的无法保证绝对的平衡(有些情况无法满足高度差为0)因此高度差不超过1
2.AVL树节点的定义
和二叉搜索树类似只不过多了个平衡因子
//AVL树的节点
templateclass K,class V
struct AVLTreeNode
{AVLTreeNodeK,V* _left;AVLTreeNodeK,V* _right;AVLTreeNodeK,V* _parent;int _bf 0;//平衡因子pairK, V _kv;//构造AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}};3.AVL树的插入
3.1插入 AVL树就是在二叉搜索树的基础上引进了平衡因子(bf)因此AVL树也可以看做二叉搜索树 AVL树的插入过程可以分为两步: 以二叉搜索树的方式插入新节点调整节点的平衡因子 二叉搜索树的方式插入
bool insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (kv.first cur-_kv.first)//插入的值比遍历的值大{parent cur;//cur往下遍历时父节点同时要往下走cur cur-_right;//往右走}else if (kv.first cur-_kv.first)//插入的值比遍历的值小{parent cur;cur cur-_left;//往左走}else//说明插入的值已经存在return false{return false;}}//走到这说明已经找到可以插入的地方 //创建一个新节点cur new Node(kv);//判断插入的节点该连接到父节点的左还是右if (cur-_kv.first parent-_kv.first)//cur 的值大于父节点的值连右{parent-_right cur;}else{parent-_left cur;}//接下来就是判断平衡因子的时候了return true;} 判断平衡因子
平衡因子 右子树高度-左子树高度
插入节点会影响哪些节点的平衡因子呢新增节点的部分祖先
更新原则
若cur是此父节点的左子树(节点)那么父节点的平衡因子-- 是右子树(节点)那么父节点平衡因子
是否继续更新取决于父节点的高度是否变化是否会影响爷爷节点 一直往上走直至parent为nullptr(根节点的父节点为空)或者平衡因子为0或者平衡因子为2(需要旋转) 当cur(新增节点插入后)有三种情况 情况1 更新后 父节点(parent)的平衡因子(bf)为 0 parent所在子树高度不变不会影响爷爷说明更新前parent的bf为1或-1往父节点矮的那边插入节点左右均衡parent所在子树的高度不变 情况2 更新后 父节点的平衡因子为1或-1parent所在子树高度改变了会影响爷爷继续往上更新说明更新前parent的bf为0(本身平衡了)往p的任意一边插入使父节点变得不均衡但不违反规则 情况3 更新后父节点的平衡因子为2或-2说明父节点所在的子树违反了平衡规则需要旋转处理 //接下来就是判断平衡因子的时候了cur-_parent parent;while (parent){if (cur parent-_left)//cur在父左 父bf--{parent-_bf--;}else//cur在父右 父bf{parent-_bf;}if (parent-_bf 0)//父bf0 break{break;}else if (parent-_bf 1 || parent-_bf -1)//父bf为1 or -1继续往上{cur cur-_parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){//平衡因子为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)//两边都高左右双旋{RotateLR(parent);}else//右左双旋{RotateRL(parent);}}else{assert(false);}}
合起来 bool insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (kv.first cur-_kv.first)//插入的值比遍历的值大{parent cur;//cur往下遍历时父节点同时要往下走cur cur-_right;//往右走}else if (kv.first cur-_kv.first)//插入的值比遍历的值小{parent cur;cur cur-_left;//往左走}else//说明插入的值已经存在return false{return false;}}//走到这说明已经找到可以插入的地方 //创建一个新节点cur new Node(kv);//判断插入的节点该连接到父节点的左还是右if (cur-_kv.first parent-_kv.first)//cur 的值大于父节点的值连右{parent-_right cur;}else{parent-_left cur;}//接下来就是判断平衡因子的时候了cur-_parent parent;//若cur是此父节点的左子树(节点)那么父节点的平衡因子-- 是右子树(节点)那么父节点平衡因子//一直往上走直至parent为nullptr(根节点的父节点为空)或者平衡因子为0或者平衡因子为2(需要旋转)while (parent){if (cur parent-_left)//cur在父左 父bf--{parent-_bf--;}else//cur在父右 父bf{parent-_bf;}if (parent-_bf 0)//父bf0 break{break;}else if (parent-_bf 1 || parent-_bf -1)//父bf为1 or -1继续往上{cur cur-_parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){//平衡因子为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)//两边都高左右双旋{RotateLR(parent);}else//右左双旋{RotateRL(parent);}}else{assert(false);}}return true;}
3.2旋转
如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种左单旋、右单旋、左右双旋以及右左双旋
左单旋——新节点插入较高右子树的右侧---右右 void RotateL(Node* parent)//左单旋{//sub是parent subR是parent的右节点subRL是subR的左节点Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;//父节点的右节点指向subRL//subRL可能为空节点也就是这颗树(子树)只有sub(parent节点)、subR、以及新增节点这三个节点 如果subRL为空就不用将其父节点指向sub了if (subRL){subRL-_parent parent;}Node* ppnode parent-_parent;parent-_parent subR;//把父节点的父节点指向subR//父节点(sub)有可能是一颗树(子树)的根节点 //如果(sub)是一颗树的根节点的话 subR直接为根节点subR的parent直接是空if (parent _root){subR _root;subR-_parent nullptr;}else//sub是一颗子树的根节点 {//得看sub是其父节点的左节点还是右节点//然后subR连接sub的父节点if (parent ppnode-_left){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}//sub和subR平衡因子置为0subR-_bf 0;parent-_bf 0;} 右单旋——新节点插入较高左子树的左侧---左左 //右单旋思路和左单旋差不多void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){subL _root;subL-_parent nullptr;}else{if (parent ppnode-_left){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}subL-_bf 0;parent-_bf 0;} 左右双旋—— 新节点插入较高左子树的右侧---左右(先左单旋再右单旋)
左右两边都高单旋解决不了问题 //左右双旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;//subLR的平衡因子不同时对其它节点的平衡因子的改变也不同int bf subLR-_bf;RotateL(parent-_left);//先走左单旋RotateR(parent);//再走右单旋if (bf -1)//若subLR的bf为-1则新增节点是subLR的左子树{subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 1)//若subLR的bf为1则新增节点是subLR的右子树{subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (bf 0) //若subLR的bf为0,那么subLR其本身就是新增节点{subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{assert(false);}}
右左双旋——新节点插入较高右子树的左侧---右左(先右单旋再左单旋) void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);if (bf -1){subRL-_bf 0;subR-_bf 1;parent-_bf 0;}else if (bf 1){subRL-_bf 0;subR-_bf 0;parent-_bf -1;}else if (bf 0){subRL-_bf 0;subR-_bf 0;parent-_bf 0;}else{assert(false);}} 4.判断是否为AVL树
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步
1. 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树 void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first [ root-_bf ] endl;_Inorder(root-_right);}void Inorder(){_Inorder(_root);}
2. 验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) 节点的平衡因子是否计算正确 int _Height(Node* root){if (root nullptr)return;int leftHight Height(root-_left);int rightHight Height(root-_right);return leftHight rightHight ? leftHight 1 : rightHight 1;}int Height(){return _Height(_root);}bool _IsAVLTree(Node* root)
{if (root nullptr){return true;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);if (abs(leftHeight - rightHeight) 2){cout 不平衡 endl;return false;}if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return _IsAVLTree(root-_left)_IsAVLTree(root-_right);
}bool IsAVLTree(){return _IsAVLTree(_root);}
如果走前序递归的话计算高度和前序递归会存在大量重复所以还是走后序的同时求高度
后序先走左子树判断平衡返回高度再走右子树判断平衡返回高度
bool _IsAVLTree(Node* root, int height){if (root nullptr){height 0;return true;}//走个后序int leftHeight, rightHeight 0;if (!_IsAVLTree(root-_left, leftHeight) || !_IsAVLTree(root-_right, rightHeight)){return false;}if (abs(leftHeight - rightHeight) 2){cout 不平衡 endl;return false;}if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}height leftHeight rightHeight ? leftHeight 1 : rightHeight 1;return true;}bool IsAVLTree(){int height 0;return _IsAVLTree(_root, height);}
