正规网站建设团队是什么,dedecms 子网站,有后台的网站,个人作品集网站模板免费下载欢迎光临 #xff1a; 羑悻的小杀马特-CSDN博客 目录 一AVL树的介绍#xff1a;
二AVL树的实现#xff1a;
1结构框架#xff1a;
2节点的插入#xff1a;
旋转#xff1a;
21左单旋#xff1a;
2.1.1左单旋介绍及步骤#xff1a;
2.1.2左单旋代码实… 欢迎光临 羑悻的小杀马特-CSDN博客 目录 一·AVL树的介绍
二·AVL树的实现
1·结构框架
2·节点的插入
旋转
2·1左单旋
2.1.1左单旋介绍及步骤
2.1.2左单旋代码实现
2.1.3左单旋技巧总结
2·2右单旋
2.2.1右单旋介绍及步骤
2.2.2右单旋代码实现
2.2.3右单旋技巧总结
2·3左右双旋
2.3.1左右双旋介绍及步骤
2.3.2左右双旋代码实现 2.3.3左右双旋技巧总结
2.4右左双旋
2.4.1右左双旋介绍及步骤
2.4.2右左双旋代码实现 2.4.3右左双旋技巧总结
旋转系列的总结
3.节点的查找
4.检验AVL树是否平衡
三·AVL树的代码汇总 一·AVL树的介绍
AVL树它的左右⼦树都是AVL树且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树 通过控制⾼度差去控制平衡。
因此为了能记录它是否平衡这里引入了一个新名词也就是平衡因子balance factor某个结点的平衡因子就是它右子树的高度减去左子树的高度也就是说这个树要是AVL树那么它的平衡因子一定是-1或0或1否则就要旋转调整后面会介绍到。 那为啥高度差不能都为0呢如⼀棵树是2个结点4个结点等情况下⾼度差最好就是1⽆法作为⾼度差是0因此这样设计是比较合理的 当然因为这样设计就趋近于完全二叉树那么高度就可以理解为log(n)那么此时它的增删查改也可以这么认为成log(n)。
二·AVL树的实现
1·结构框架
templateclass K, class V
struct AVLTreeNode
{// 需要parent指针后续更新平衡因子可以看到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), _bf(0){}
};
templatetypename K,typename V
class AVLTree {
public:using node AVLTreeNodeK, V;
private:node* _root nullptr;
};
2·节点的插入
这里插入其实和上次写的二叉搜索树的插入差不多但是就多了控制高度平衡以及对平衡因子的控制操作。
也就是我们找到空位置连接插入后然后把它的parent处节点的平衡因子更新一下看一下是否符合条件然后分情况决定继续向上遍历查找还是停止还是旋转。下面分为三种情况 1·情况一恰好为0也就是原来是-1或者1变来的此时就不需要向上调整了为什么呢因为未插入前parent作为一个节点的右孩子或者左孩子那么这个节点的假设是左孩子是parent可以发现此时插入还是不插入这个节点的平衡因子都不变故这时就不需要向上判断。 如 2·情况二恰好为1或者-1也就是从-2或者0变来的那么此时它变化了可能会导致上面变化因此还要向上继续遍历找平衡因子的变化。 3·情况三恰好是-2或者是2那么此时就不符合平衡规则那就涉及到旋转了下面会讲到。 旋转 这里旋转是为了什么呢1·保持搜索树的原则。2·可以降低树的高度。3·可以保证树的平衡。因此根据parent为2或者-2以及它的左或右孩子为1或-1的几种情况可以把它分为左单旋右单旋左右双旋右左双旋等。 2·1左单旋
2.1.1左单旋介绍及步骤
左单旋肯定是右边高这里为了方便对下面很多节点这里直接把剩下的子树抽象化因为它是平衡二叉树故因此可以把再你插入之前将要变成2或者-2的节点作为parent以及它的下面分割下来成为抽象的树部分如 这样的话左单旋也就是在最右边的h当然这里的h0高度的下面插入一个节点 然后通过左单旋变为平衡状态 这里我们可以看出来就是把pr的左指针指向parentparent的右指针指向pr1但是这里就忽视了最终要的父亲指针此时也要注意把pr1注意是否为空的父亲指针指向parent然后保存原先parent的父亲指针也要判断一下parent是否为根节点从而单独做处理然后把此时的连接连成pr即可了。
2.1.2左单旋代码实现
下面展示一下代码
void RotateL(node* parent) {//左旋node* subr parent-_right;node* subrl subr-_left;//处理sublrparent-_right subrl;if (subrl) subrl-_parent parent;//sublr为空不能访问node* pp parent-_parent;//保存parent的父节点指针//调节新旧“parent”位置subr-_left parent;parent-_parent subr;if (pp nullptr) {_root subr;subr-_parent nullptr;}else {if (parent pp-_left) pp-_left subr;else pp-_right subr;subr-_parent pp;}parent-_bf subr-_bf 0;}
2.1.3左单旋技巧总结 技巧总结这里对于左单旋的操作进行一下总结把parent节点向下压然后把 pr的左孩子也就是prl作为parent右孩子其他注意连接即可。 2·2右单旋
2.2.1右单旋介绍及步骤
右单旋肯定是左边高其实也是根左单旋大差不差下面上图 这里也和上面类似只不过是把parent的左指针指向plrpl的右指针指向parent还有一些其他的注意连接方法右单旋也就是在最左边的h插入使它变为h1 这里与左单旋大差不差因此就不重复了。
2.2.2右单旋代码实现
代码
void RotateR(node* parent) {//右旋node* subl parent-_left;node* sublr subl-_right;parent-_left sublr;if (sublr) sublr-_parent parent;node* pp parent-_parent;subl-_right parent;parent-_parent subl;if (pp nullptr) {_root subl;subl-_parent nullptr;}else {if (parent pp-_left) pp-_left subl;else pp-_right subl;subl-_parent pp;}parent-_bf subl-_bf 0;
}2.2.3右单旋技巧总结 技巧总结把parent向下压然后把plr与parent的左指针相连然后注意parent指针的控制即可。 2·3左右双旋
2.3.1左右双旋介绍及步骤
这里为什么叫这个呢其实它的步骤可以分为先对parent的孩子进行左单旋然后再对parent进行右单旋即可。这里我们可以这么理解即就是在进行右单旋的插入图把节点插在中间的h上即可而这时根据h0;分为了三种情况对应的是平衡因子的变化 情况一就是h为0的情况那么此时到最后进行旋转后它们的平衡因子都是0。 情况二插入h的右边那么旋转后pl的平衡因子就是-1其他都是零。 情况三插入h的左边那么旋转后parent的平衡因子就是1。 那么我们写代码的时候怎么区分这三种情况就成了写左右双旋的关键了即这时候我们得到的插入后的plr这个节点的bf一定是如果是0就是第一种情况如果是-1就是第三种情况 如果是1就是第二种情况因此可以根据这个进行代码的编写。 步骤1首先先把pl左旋然后parent进行右旋这时大概结构就搞好了也就是高度OK了步骤2接下来就是平衡因子的更改可以根据我们旋转之前保存的pl的bf分情况进行对旋转后parentpl和plr三个节点处平衡因子进行更新操作。 2.3.2左右双旋代码实现
代码展示
void RotateLR(node* parent) {//左右双旋node* subl parent-_left;node* sublr subl-_right;int bf sublr-_bf;RotateL(subl);RotateR(parent);if (bf -1) {//插入的是sublr的左支sublr-_bf 0;subl-_bf 0;parent-_bf 1;}else if (bf 1) {//插入的是sublr的右支sublr-_bf 0;subl-_bf -1;parent-_bf 0;}else if (bf 0) {//插入前sublr为空sublr-_bf 0;subl-_bf 0;parent-_bf 0;}else{assert(false);}} 2.3.3左右双旋技巧总结 技巧总结就是把parent节点压下来plr节点提到最上面之后pl连接它的左指针parent连接它的右指针然后plr的左孩子给pl右指针右孩子给parent左指针。 2.4右左双旋
2.4.1右左双旋介绍及步骤
这里其实和左右双旋一样但是是左旋最初的那个图在中间的h插入然后也是分为那三种情况。 情况1h0最后插入的就是prl这个节点那么此时parentprl和pr平衡因子都是0. 情况2h1,但是插入的那个h的右边那么此时pr的bf是0parent的bf是-1然后prl的平衡因子就是0。 情况3 h1,但是插入的那个h的左边那么此时pr的bf是1parent的bf是0然后prl的平衡因子就是0。 跟左右双旋一样那么我们写代码的时候怎么区分这三种情况就成了写右左双旋的关键了即这时候我们得到的插入后的plr这个节点的bf一定是如果是0就是第一种情况如果是-1就是第三种情况 如果是1就是第二种情况因此可以根据这个进行代码的编写。 步骤1类似还是pr右旋然后parent左旋链接好形状。 步骤2更新平衡因子如果第一种情况此时parentprprl的平衡因子都是0第二种情况prl是0parent是-1pr是0第三种情况prl还是0parent是0pr是1。 2.4.2右左双旋代码实现
代码
void RotateRL(node* parent) {//右左双旋node* subr parent-_right;node* subrl subr-_left;int bf subrl-_bf;RotateR(subr);RotateL(parent);if (bf -1) { //插入的是subrl的左支subrl-_bf 0;subr-_bf 1;parent-_bf 0;}else if (bf 1) {//插入的是subrl的右支subrl-_bf 0;subr-_bf 0;parent-_bf -1;}else if (bf 0) {//插入前subrl为空subrl-_bf 0;subr-_bf 0;parent-_bf 0;}else{assert(false);}} 2.4.3右左双旋技巧总结 技巧总结就是把parent节点压下来prl节点提到最上面之后parent连接它的左指针pr连接它的右指针然后prl的左孩子给parent右指针右孩子给pr左指针。 旋转系列的总结 这里对上面四种旋转方式如何进行的做一个总结 1·首先是左单旋和右单旋:可以这么想向哪一边旋转就是另一边高故就是插入的是最边上才导致增高的根据此画出相应的图来都是parent被拽下来然后少的孩子用旁边的离得最近的孩子补上其次就是注意各个节点对应的指针的连接。 2·左右双旋和右左双旋:可以这么理解左右右单旋的图只是节点插在了中间的h处再分三种情况判断平衡因子右左左单旋的图节点插在了中间的h操作就是plr或者prl中间h分出去的节点或者是h0新插入的节点提到最上面然后pl成左支或者pr成右支然后被截下来的plr或者prl的左支向左补右支向右补最后处理好节点之间的连接即可。 3.节点的查找
node* Find(const K key)
{node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return nullptr;
}
4.检验AVL树是否平衡
导致其不平衡的条件有两个要么高度不符合要求要么就是高度正确而平衡因子未更新正确。
因此可以根据这两个条件来写代码完成检验操作。
int treehight(node* root) {if (root nullptr) return 0;int lefthight treehight(root-_left);int righthight treehight(root-_right);return lefthight righthight ? lefthight 1 : righthight 1;
}bool _IsBalanceTree(node* root) {//不平衡肯定是在插入数据的时候没有更新正确导致//如高度没有控制好或者就是高度控制了当往上调整的时候平衡因子没有及时更新导致平衡因子不符合要求if (root nullptr) return true;int lefthight treehight(root-_left);int righthight treehight(root-_right);int gap abs(lefthight - righthight);if (gap 2){cout root-_kv.first :高度存在问题 endl;return false;}if (abs(root-_bf) ! gap) {cout root-_kv.first :平衡因子存在问题 endl;return false;}return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);}
这里顺便说一下删除操作如果没找到此节点就直接返回了要么就是删除的是叶子节点直接删除就可要么是删除一个节点它的左孩子为空或者右孩子为空那么此时删除这个节点后把另一端不为空的孩子补过去最后一种就是要删除节点的 左右孩子都不为空此时就要类似二叉搜索树删除一样找替代的孩子即此节点右孩子一直向左遍历找到最后一个节点与它替换在完成间接删除操作。这里就不做操作了大致就是这个意思。
三·AVL树的代码汇总
#pragma once
#includeiostream
#includeassert.h
#includestring
#includevector
#includealgorithm
using namespace std;
templateclass K, class V
struct AVLTreeNode
{// 需要parent指针后续更新平衡因子可以看到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), _bf(0){}
};
templatetypename K,typename V
class AVLTree {
public:using node AVLTreeNodeK, V;bool Insert(const pairK, V kv){if (_root nullptr) {_root new node(kv);return true;}else {//寻找空位置进行插入node* cur _root;node* parent nullptr;while (cur) {if (cur-_kv.first kv.first) {parent cur;cur cur-_left;}else if (cur-_kv.first kv.first) {parent cur;cur cur-_right;}else {return false;}}//插入cur new node(kv);if (kv.first parent-_kv.first) parent-_left cur;else parent-_right cur;cur-_parent parent;//更新平衡因子:平衡更新完要么找到parent的bf等于0要么找到了root发现它的平衡因子还是1或-1//保持parent始终是cur的父亲while (parent) {//cur仍旧是当前插入的节点if (cur parent-_left) parent-_bf--;else parent-_bf;if (parent-_bf 0) break;else if (parent-_bf -1 || parent-_bf 1) {cur parent;parent cur-_parent;}else if (parent-_bf 2 || parent-_bf -2) {//判断如何旋转if (parent-_bf 2 parent-_right -_bf -1) {RotateRL(parent);}else if (parent-_bf -2 parent-_left-_bf 1) {RotateLR(parent);}else if (parent-_bf 2 parent-_right-_bf 1) {RotateL(parent);}else if (parent-_bf -2 parent-_left-_bf -1) {RotateR(parent);}else {assert(false);}break;//这里由于给它旋转后肯定保证了parent出平衡因子为0故不用上调了}else assert(false);}return true;}}node* Find(const K key){node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return nullptr;}int treehight(node* root) {if (root nullptr) return 0;int lefthight treehight(root-_left);int righthight treehight(root-_right);return lefthight righthight ? lefthight 1 : righthight 1;}void InOrder() {_inorder(_root);}bool IsBalanceTree() {return _IsBalanceTree(_root);}
private:void RotateL(node* parent) {//左旋node* subr parent-_right;node* subrl subr-_left;//处理sublrparent-_right subrl;if (subrl) subrl-_parent parent;//sublr为空不能访问node* pp parent-_parent;//保存parent的父节点指针//调节新旧“parent”位置subr-_left parent;parent-_parent subr;if (pp nullptr) {_root subr;subr-_parent nullptr;}else {if (parent pp-_left) pp-_left subr;else pp-_right subr;subr-_parent pp;}parent-_bf subr-_bf 0;}void RotateR(node* parent) {//右旋node* subl parent-_left;node* sublr subl-_right;parent-_left sublr;if (sublr) sublr-_parent parent;node* pp parent-_parent;subl-_right parent;parent-_parent subl;if (pp nullptr) {_root subl;subl-_parent nullptr;}else {if (parent pp-_left) pp-_left subl;else pp-_right subl;subl-_parent pp;}parent-_bf subl-_bf 0;}void RotateLR(node* parent) {//左右双旋node* subl parent-_left;node* sublr subl-_right;int bf sublr-_bf;RotateL(subl);RotateR(parent);if (bf -1) {//插入的是sublr的左支sublr-_bf 0;subl-_bf 0;parent-_bf 1;}else if (bf 1) {//插入的是sublr的右支sublr-_bf 0;subl-_bf -1;parent-_bf 0;}else if (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的左支subrl-_bf 0;subr-_bf 1;parent-_bf 0;}else if (bf 1) {//插入的是subrl的右支subrl-_bf 0;subr-_bf 0;parent-_bf -1;}else if (bf 0) {//插入前subrl为空subrl-_bf 0;subr-_bf 0;parent-_bf 0;}else{assert(false);}}void _inorder(node* root) {if (root nullptr) return;_inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_inorder(root-_right);}bool _IsBalanceTree(node* root) {//不平衡肯定是在插入数据的时候没有更新正确导致//如高度没有控制好或者就是高度控制了当往上调整的时候平衡因子没有及时更新导致平衡因子不符合要求if (root nullptr) return true;int lefthight treehight(root-_left);int righthight treehight(root-_right);int gap abs(lefthight - righthight);if (gap 2){cout root-_kv.first :高度存在问题 endl;return false;}if (abs(root-_bf) ! gap) {cout root-_kv.first :平衡因子存在问题 endl;return false;}return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);}node* _root nullptr;
}; 这些也仅是个人对AVL有限的理解希望大佬多多指导。
