打码网站建设,深圳教育科技网站建设,wordpress socket,成都品牌设计公司排名AVL树的概念
二叉搜索树虽可以缩短查找的效率#xff0c;但如果数据有序或接近有序二叉搜索树将退化为单支树#xff0c;查找元素相当于在顺序表中搜索元素#xff0c;效率低下#xff0c;时间复杂度为O#xff08;N#xff09;#xff1b;
两位俄罗斯的数学家G.M.Ade…AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下时间复杂度为ON
两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。AVL树即是高度平衡的二叉搜索树。
一棵AVL树是一棵平衡二叉搜索树也能是一棵空树。
AVL树的性质
①它的左右子树都是AVL树
②左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
③如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在log_2N,搜索的时间复杂度是log_2N。 AVL树的定义
AVL树的定义中①拥有键值对。②多加一个双亲节点用于调整平衡二叉树。③增加平衡因子用于判断插入或删除后是否还是一棵AVL树。
templateclass K,class V
struct AVLTreeNode
{pairK, V _kv;//键值对AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf;//balance factorAVLTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};AVL树的插入
AVL树的插入分成两步第一步是按照二叉搜索树的方式来新增节点。第二步是是调整节点使其成为一棵平衡的二叉搜索树。
先展示代码我们分析以下思路
1.首先按照二叉搜索树的方式来新增节点但这需要新增一个双亲指针方便后续在调节节点。因此在新增节点的最后部分的代码中我们需要让cur-_parent指向双亲节点parent。
2.完成二叉搜索树的创建后开始去判断各个节点的平衡因子。 ①当平衡因子_bf等于0的时候说明parent节点一边高一边矮新增的这个节点填上了矮的地方这种情况就不需要更新了直接beak掉。 ②当平衡因子_bf等于1或者-1的时候说明parent原本的平衡因子是0parent两边一样高新增了节点之后有一边变高了。这种情况需要继续往上走。 ③当平衡因子_bf等于2或-2的时候说明之前parent-_bf 1 或者 -1现在插入严重不平衡违反规则此时需要原地旋转即以当前节点为轴旋转。 随后将重点分析当平衡因子是2或-2的时候说明需要通过旋转调节节点。那该如何去旋转呢 bool Insert(const pairK, V kv){//一开始是一棵空树if (_root nullptr){_root new Node(kv);return true;}//一开始不是空树Node* parent nullptr;Node* cur _root;//寻找插入的地方是左子树还是右子树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;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}//更新平衡因子判断插入后的树是否是一棵AVL树while (parent){//插入的是在父节点的左边即是左孩子if (cur parent-_left){parent-_bf--;//一般是右-左因此如果是插入在左边那就是减一}else //是右孩子{parent-_bf;}//更新完平衡因子后判断是否是一棵AVL树//如果平衡因子是0任何节点的平衡因子都没被改变if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){//如果平衡因子是1或-1那么就说明父节点往上的节点的平衡因子有可能被改变了cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){//旋转//右单旋----高出来的那一部分按下去if (parent-_bf -2 cur-_bf -1){RotateR(parent);}else if(parent-_bf2 cur-_bf 1)//左单旋{RotateL(parent);}else if (parent-_bf -2 cur-_bf 1) //先左旋后右旋{RotateLR(parent);}else if (parent-_bf 2 cur-_bf -1) //先右旋再左旋{RotateRL(parent);}}else //不排除在创建一棵AVL树的时候代码写错了{assert(false);}}return true;}
旋转节点
旋转的要求
⭐让这颗子树左右高度之差不超过1
⭐旋转过程中继续保持他是搜索树
⭐更新调整孩子节点的平衡因子
⭐让这颗子树的高度跟插入前保持一致。因为这样就不会对上层的平衡因子造成影响此时就可以结束对这棵树的更新旋转。
旋转的情况有四种
①新节点插入较高左子树的左侧---左左右单旋 这种情况是新增的节点位于比较高的左子树的左侧的某个位置上此时在往上检查平衡因子发现值为60的节点是平衡因子为-2说明左子树的高度是比右子树高的这里选择右减左所以当我们的判断条件if(parent-_bf-2 cur-_bf -1)成立时就表示着符合当前情况。所以我们需要将60的节点的平衡因子减小那就是将它按下去以60的节点为轴旋转
⭐旋转的动作因为b是30节点的右孩子根据二叉搜索树的性质b子树所有的值肯定是大于30小于60的而且60节点需要下来说明60节点是要成为30节点的右孩子的因此b子树就需要成为60节点的左孩子了。
⭐当然我们需先判断一下30节点的右孩子是否为空即30节点没有右孩子。如果没有右孩子那么就不能让它指向60节点的左孩子。
⭐然而我们旋转的这颗树可能是一颗子树因此需要判断一下60节点的双亲节点是否为空如果为空说明它不是子树此时就可以让_root指向subL成为新的根然后subL的双亲节点置为nullptr因为subL-parent原本是指向60节点的。
⭐如果不为空那就说明它是一棵子树那么就让60节点的双亲节点的左或右孩子点指向30节点30节点的双亲指向60原先的双亲节点。
右单旋的代码如下 void RotateR(Node* parent){//一开始例子中的60节点便是parent//先创建指向30节点的指针和指向b节点的指针Node* subL parent-_left;Node* subLR subL-_right;//这一步是让60节点的左孩子指向b节点parent-_left subLR;//这一步判断b节点是否为空,如果不为空那么就让它的双亲节点指向60节点本来是指向subL的if (subLR){subLR-_parent parent;}//上面两步成功将b节点改链接到60节点上去//先保存60节点的双亲节点Node* ppNode parent-_parent;//让30节点subL的右孩子指向60节点即60节点链接到了30节点subL的右孩子上subL-_right parent;//60节点的双亲节点指向30节点subLparent-_parent subL;//判断60节点原本的双亲节点是否为空//为空if (ppNode nullptr){_root subL;_root-_parent nullptr;}else //不为空说明是一棵子树{if (ppNode-_left parent) //如果parent是原先的双亲节点的左孩子{ppNode-_left subL; }else //如果parent是原先的双亲节点的右孩子{ppNode-_right subL;}//链接后再让成为新根后的30节点subL的双亲节点指向ppNodesubL-_parent ppNode;}//最后将30节点subL和60节点parent的平衡因子修改//subL-_bf parent-_bf 0;//此时右单旋完成//因为旋转的要求是让这颗子树的高度跟插入前保持一致//那就说明此时完成旋转的这树不会对上层的平衡因子造成影响此时就可以结束对这棵树的更新旋转}
②新节点插入较高右子树的右侧---右右左单旋 这种情况是新增的节点位于比较高的右子树的右侧的某个位置上此时在往上检查平衡因子发现值为30的节点是平衡因子为2说明右子树的高度是比左子树高的这里选择右减左所以当我们的判断条件if(parent-_bf2 cur-_bf 1)成立时就表示着符合当前情况。所以我们需要将30的节点的平衡因子减小那就是将它按下去以30的节点为轴旋转
⭐旋转的动作因为b是60节点的左孩子根据二叉搜索树的性质b子树所有的值肯定是大于30小于60的而且30节点需要下来说明30节点是要成为60节点的左孩子孩子的因此b子树就需要成为30节点的右孩子了。
⭐同样的我们需先判断一下60节点的左孩子是否为空即60节点没有左孩子。如果没有左孩子那么就不能让它指向30节点的右孩子。
⭐同样的需要盘点一下是否是一棵子树。因此需要判断一下30节点的双亲节点是否为空如果为空说明它不是子树此时就可以让_root指向subR成为新的根然后subR的双亲节点置为nullptr因为subR-parent原本是指向30节点的。
⭐如果不为空那就说明它是一棵子树那么就让30节点的双亲节点的左或右孩子点指向60节点60节点的双亲指向30原先的双亲节点。
左单旋代码如下 void RotateL(Node* parent){//创建60节点subR右右是左旋嘛Node* subR parent-_right;//创建指向b节点的指针subRLNode* subRL subR-_left;//先让parent的右孩子节点指向subRL。parent-_right subRL;//判断subRL是否为空不为空那就让subRL的父节点指向parentif (subRL){subRL-_parent parent;}//上面步骤成功将b节点链接到了parent上//先把parent的父节点保存起来不管存在不存在Node* ppNode parent-_parent;//接下来就是把parent按下了成为subR的左孩子让subR成为新根subR-_left parent;parent-_parent subR;//让subR成为新根if (ppNode nullptr){_root subR;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}//修改平衡因子parent-_bf subR-_bf 0;}
③新节点插入较高左子树的右侧---左右先左单旋再右单旋 这种情况是新增的节点位于比较高的左子树的右侧的某个位置上此时在往上检查平衡因子发现值为parent节点的平衡因子为-2说明左子树的高度是比右子树高的这里选择右减左所以当我们的判断条件if(parent-_bf-2 cur-_bf 1)成立时就表示着符合当前情况。这种情况采取的旋转方式是先左旋后右旋。左旋的轴是subL节点右旋的轴就是parent节点。
此时我们复用左单旋和右单旋的情况即可。但是需要注意的是尽管在右单旋和左单旋中已经对平衡因子进行了修改但我们通过画图可以看出来修改过的平衡因子并不符合实际上的值因此我们需要重新修改一遍。
代码如下 void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;//记录调整节点之前subLR的平衡因子因为subLR最后是新根//开始调整RotateL(parent-_left);RotateR(parent);//修改平衡因子if (bf -1)//说明是在左子树上新增节点即图中的b子树{parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else if (bf 1)//说明是在右子树c上新增节点{parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if(bf0)//说明subLR自己就是新增的节点{parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else{assert(false);}}
④新节点插入较高右子树的左侧---右左先右单旋再左单旋 这种情况是新增的节点位于比较高的右子树的左侧的某个位置上此时在往上检查平衡因子发现值为parent节点的平衡因子为2说明右子树的高度是比左子树高的这里选择右减左所以当我们的判断条件if(parent-_bf2 cur-_bf -1)成立时就表示着符合当前情况。这种情况采取的旋转方式是先右旋后左旋。右旋的轴是subR节点左旋的轴就是parent节点。
此时我们复用左单旋和右单旋的情况即可。但是需要注意的是尽管在右单旋和左单旋中已经对平衡因子进行了修改但我们通过画图可以看出来修改过的平衡因子并不符合实际上的值因此我们需要重新修改一遍。
代码如下 void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;//记录调整节点之前subRL的平衡因子因为subRL最后是新根RotateR(parent-_right);RotateL(parent);if (bf 1) //在右子树上新增节点{parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else if (bf -1) //在左子树上新增节点{parent-_bf 0;subR-_bf -1;subRL-_bf 0;}else if (bf 0) //说明subRL本身就是那个新增的节点{parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else{assert(false);}}
总结
假如以pParent为根的子树不平衡即pParent的平衡因子为2或者-2分以下情况考虑 ①pParent的平衡因子为2说明pParent的右子树高设pParent的右子树的根为pSubR。 当pSubR的平衡因子为1时执行左单旋 当pSubR的平衡因子为-1时执行右左双旋 ②pParent的平衡因子为-2说明pParent的左子树高设pParent的左子树的根为pSubL 当pSubL的平衡因子为-1是执行右单旋 当pSubL的平衡因子为1时执行左右双旋 旋转完成后原pParent为根的子树个高度降低已经平衡不需要再向上更新。
验证AVL树
由于AVL树是在二叉搜索树的基础上加了平衡性后得到的树因此需要确认一棵树是AVL树那么就需要以下两步
1.先确定是否是一棵二叉搜索树如果中序遍历可得到一个有序的序列就说明为二叉搜索树。
2.验证其是否平衡①每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)。②节点的平衡因子是否计算正确。
代码如下
①中序遍历 void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}
②计算高度 int Height(Node* root){if (root nullptr){return 0;}//先计算左子树的高度int ln Height(root-_left);//然后计算右子树的高度int rn Height(root-_right);return ln rn ? ln 1 : rn 1;}
③验证平衡 bool IsBalance(){return _IsBalance(_root);}bool _IsBalance(Node* root){if (root nullptr)return true;//计算当前节点root的平衡因子int leftHeight Height(root-_left);int rightHeight Height(root-_right);//如果不同那就将当前节点的值打印出来并提升异常if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}//通过递归验证每一个节点的平衡因子是否符合return abs(rightHeight - leftHeight) 2 _IsBalance(root-_left) _IsBalance(root-_right);}
AVL树性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即log_2 (N)。
但是如果要对AVL树做一些结构修改的操作性能非常低下因为做修改就很大可能需要进行旋转每一次旋转都是比较消耗性能的
