国内外包网站,wordpress标题在那个文件里,怎么做网站上的销售代,自适应h5网页模板目录 一、AVL树介绍1.1 概念1.2 定义 二、AVL树的实现2.1 插入2.2 旋转2.2.1 左单旋2.2.2 右单旋2.2.3 左右双旋2.2.4 右左双旋 一、AVL树介绍
1.1 概念
AVL树是高度平衡的二叉搜索树#xff0c;相比普通的二叉搜索树#xff0c;它防止了变成单支树的情况。因为AVL树每插入… 目录 一、AVL树介绍1.1 概念1.2 定义 二、AVL树的实现2.1 插入2.2 旋转2.2.1 左单旋2.2.2 右单旋2.2.3 左右双旋2.2.4 右左双旋 一、AVL树介绍
1.1 概念
AVL树是高度平衡的二叉搜索树相比普通的二叉搜索树它防止了变成单支树的情况。因为AVL树每插入一个新的节点它都会调整使左右子树的高度差的绝对值不超过1从而降低了树的高度提高了搜索效率。
特点
左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)搜索时间复杂度O( l o g 2 n log_2 n log2n)有平衡因子控制高度差右子树高度减去左子树高度 1.2 定义
AVL树是三叉链结构即左孩子指针、右孩子指针和双亲指针多了一个双亲指针方便找到上一个节点。定义它的数据域为kv模型的类型。定义平衡因子作用是记录当前节点的左右子树高度之差。
templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;int _bf;pairK, V _kv;AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}
};二、AVL树的实现
2.1 插入
AVL树的插入过程与二叉搜索树的插入过程是一样的只不过在此基础上增加了调整节点的平衡因子。所以总结为两个步骤
按照二叉搜索树的方式插入新节点调整节点的平衡因子 没标数字的是新插入的节点 调整平衡因子首先要从cur和parent入手即新插入的节点和插入节点的上一个节点。如果插入节点cur是parent的右边则parent的平衡因子1反之则-1。整个调整过程是一个循环因为刚开始改变的是下面的平衡因子上面节点的平衡因子也可能会随之改变。循环条件为parent不为空还要其他条件可以终止循环下面细讲。
所以根据parent的平衡因子的值可以分为3步
parent的平衡因子为0parent的平衡因子为1或者-1parent的平衡因子为2或者-2 这里说明下没有parent的平衡因子可能为3/-3的情况如果出现了说明之前的树有问题 1️⃣parent的平衡因子为0 此情况说明原来的parent的左边或者右边存在一个节点新插入的节点在parent没有节点的一侧parent两边都有节点平衡因子为0不影响上面的节点调整结束跳出循环。 2️⃣parent的平衡因子为1或者-1 如果parent的平衡因子为1或者-1则会影响上面的节点所以让parent节点转换为它的上一个节点cur转换为parent向上更新以次类推。每次循环还是要经过cur是parent的左边还是右边才能确定parent的平衡因子是1还是-1。直到cur为根节点parent为空时循环结束。
3️⃣parent的平衡因子为2或者-2 当parent向上更新到某个节点时(有可能不是根节点)它的平衡因子为2或者-2这时违背了AVL树的规则因此要进行处理——旋转来改变树的高度差使其左右之树的高度差的绝对值不超过1
下图的树插入节点后要发生旋转
旋转后高度差恢复平衡跳出循环。 总结 AVL树插入节点要进行调整平衡因子调整结束有3种 1.parent为空——已经调整到根节点了 2.parent的平衡因子为0——不影响上面节点 3.旋转后——树恢复平衡状态 代码
//插入
bool Insert(const pairK, V kv)
{//如果根为空if (_root nullptr){_root new Node(kv);return true;}//非空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;}else{parent-_left cur;}cur-_parent parent;//调整平衡因子while (parent){if (parent-_left cur){parent-_bf--;}else{parent-_bf;}if (parent-_bf 0)//不需要修改直接跳出{break;}else if (parent-_bf 1 || parent-_bf -1)//向上更新{cur cur-_parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2)//要旋转{//旋转有4种情况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);//右左双旋-先右后左}break;//旋转后跳出}else{assert(false);//之前树就有问题}}return true;
}2.2 旋转
这里就开始详细分析AVL树的旋转了旋转分为4种情况有左单旋、右单旋、左右双旋和右左双旋。发生这4种旋转的条件不一样下面逐个分析
2.2.1 左单旋
整体思路cur的左孩子变成parent的右孩子cur的左孩子可能为空parent变成cur的左孩子cur连接原来parent的双亲有可能原来的parent就是根节点如果是cur变成根
先来简单的图示分析 parent是平衡因子为2的节点cur是平衡因子为1的节点为调整成平衡parent要变成cur的左孩子而在此之前cur的左孩子要先变成parent的右孩子上面的图节点较少所以cur没有左孩子最终平衡。
通过上面的例子可以基本了解左单旋的整个过程下面来较多节点的例子 定义两个临时变量subR指向parent的右孩子即cur的位置(后面的操作就可以不用cur)subRL为subR的左孩子。
按照上面的步骤subRL变成parent的右孩子parent变成subR的左孩子定义一个ppnode节点为原来parent的双亲如果parent是在ppnode的左边则ppnode的左边连接subR反之则右边连接subR。如果parent原来是根节点那么根节点就变成subR。最后修改parent和subR的平衡因子它们的平衡因子都变成了0
有个问题旋转有4种情况怎么知道用哪种呢其实上面的两种图示已经显示出左单旋的条件。当parent的平衡因子为2并且cur的平衡因子为1时要进行的旋转为左单旋。
代码
//左单旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;//不为空if (subRL){subRL-_parent parent;}subR-_left parent;Node* ppnode parent-_parent;parent-_parent subR;//处理parent如果为根if (parent _root){_root subR;subR-_parent nullptr;}//不为根处理与ppnode的连接else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}//修改平衡因子parent-_bf 0;subR-_bf 0;
}2.2.2 右单旋
整体思路cur的右孩子变成parent的左孩子parent变成cur的右孩子cur连接原来parent的双亲。
简单图示 parent是平衡因子为-2的节点cur是平衡因子为-1的节点为调整成平衡cur的右孩子要先变成parent的右孩子parent变成cur的右孩子然后修改平衡因子最终平衡。
用较多节点的例子来分析 定义两个临时变量subL指向parent的左孩子subLR指向subL的右孩子。
subLR变成parent的左孩子parent变成subL的右孩子定义一个ppnode节点为原来parent的双亲步骤同左单旋。最后修改parent和subL的平衡因子它们的平衡因子都变成了0 通过例子可知发生右单旋的条件是parent的平衡因子为-2cur的平衡因子为-1
代码
//右单旋
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;//不为空if (subLR){subLR-_parent parent;}subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}//修改平衡因子parent-_bf 0;subL-_bf 0;
}2.2.3 左右双旋
左右双旋是先左单旋再右单旋。左单旋的是parent的左子树右单旋的是包括parent的当前树。既然已经有单旋了为什么还要双旋呢如图 通过上面例子可知如果插入的位置与前面(左单旋或者右单旋插入时的位置)不同只有左或者右旋转不能使树变平衡因此要进行双旋。
左右双旋的情况主要分为以下3类 当插入的节点是subLR时subLR的平衡因子为0插入的节点在subLR的左边subLR的平衡因子为-1插入的节点在subLR的右边subLR的平衡因子为1通过图示可知发生左右双旋的条件是parent的平衡因子为-2cur的平衡因子为1。这3种情况经过左右双旋后subLR的平衡因子都变成0但是parent和subL的平衡因子是有区别的。
下面来看看3种情况的旋转 1️⃣插入的新节点是subLR
2️⃣插入的新节点在subLR的左边
3️⃣插入的新节点在subLR的右边
通过上面的图发现当插入的新节点是subLRsubLR的平衡因子为0旋转后subL和parent的平衡因子也为0插入的新节点在subLR的左边subLR的平衡因子为-1旋转后subL的平衡因子为0parent的平衡因子为1插入的新节点在subLR的右边subLR的平衡因子为1旋转后subL的平衡因子为-1parent的平衡因子为0。
代码
//左右双旋-先左后右
void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;//提前保存原来的bfRotateL(subL);RotateR(parent);//旋转后不同情况最后的bf会不一样subLR-_bf 0;//确定的if (bf -1){subL-_bf 0;parent-_bf 1;}else if (bf 1){subL-_bf -1;parent-_bf 0;}else if (bf 0){subL-_bf 0;parent-_bf 0;}else{assert(false);}
}2.2.4 右左双旋
右左双旋是先右单旋再左单旋。右单旋的是parent的右子树左单旋的是包括parent的当前树。
右左双旋也分为3类 当插入的节点是subRL时subRL的平衡因子为0插入的节点在subRL的左边subRL的平衡因子为-1插入的节点在subRL的右边subRL的平衡因子为1通过图示可知发生右左双旋的条件是parent的平衡因子为2cur的平衡因子为-1。这3种情况经过右左双旋后subRL的平衡因子固定都变成了0但是parent和subL的平衡因子有区别。
下面是3种情况的旋转 1️⃣插入的新节点是subRL
2️⃣插入的新节点在subRL的左边
3️⃣插入的新节点在subRL的右边
插入的新节点是subRLsubRL的平衡因子为0旋转后subR和parent的平衡因子也为0插入的新节点在subRL的左边subRL的平衡因子为-1旋转后subR的平衡因子为1parent的平衡因子为0插入的新节点在subRL的右边subRL的平衡因子为1旋转后subR的平衡因子为0parent的平衡因子为-1。
代码
//右左双旋-先右后左
void RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);subRL-_bf 0;if (bf -1){subR-_bf 1;parent-_bf 0;}else if (bf 1){subR-_bf 0;parent-_bf -1;}else if (bf 0){subR-_bf 0;parent-_bf 0;}else{assert(false);}
}
