域名备案成功如何做网站,自媒体全平台发布,网站内容页模板,网站文案框架文章目录 1.AVL树的概念2.AVL树的实现AVL树结点的定义AVL树的插入AVL树的旋转左单旋右单旋左右双旋右左双旋插入代码 AVL树的验证AVL树的查找AVL树的修改AVL树的删除AVL树的性能 AVL树的代码测试 1.AVL树的概念
二叉搜索树虽然可以提高我们查找数据的效率#xff0c;但如果插… 文章目录 1.AVL树的概念2.AVL树的实现AVL树结点的定义AVL树的插入AVL树的旋转左单旋右单旋左右双旋右左双旋插入代码 AVL树的验证AVL树的查找AVL树的修改AVL树的删除AVL树的性能 AVL树的代码测试 1.AVL树的概念
二叉搜索树虽然可以提高我们查找数据的效率但如果插入二叉搜索树的数据是有序或接近有序的此时二叉搜索树会退化为单支树在单支树当中查找数据相当于在单链表当中查找数据效率是很低下的。
因此两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
AVL树可以是一棵空树也可以是具有以下性质的一棵二叉搜索树
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树的高度是平衡的它就是AVL树。如果它有n个结点其高度可保持在O(logN)其搜索时间复杂度为O(logN)
注意 这里所说的二叉搜索树的高度是平衡的是指树中每个结点左右子树高度之差的绝对值不超过1因为只有满二叉树才能做到每个结点左右子树高度之差均为0。
2.AVL树的实现
AVL树结点的定义
我们这里直接实现KV模型的AVL树为了方便后续的操作这里将AVL树中的结点定义为三叉链结构并在每个结点当中引入平衡因子右子树高度-左子树高度。除此之外还需编写一个构造新结点的构造函数由于新构造结点的左右子树均为空树于是将新构造结点的平衡因子初始设置为0即可。
// AVL平衡树左右高度差不超过1
templateclass K, class V
struct AVLTreeNode {AVLTreeNodeK, V *_left;AVLTreeNodeK, V *_right;AVLTreeNodeK, V *_parent;pairK, V _kv;// 存储键值对的pair对象pair是一个模板类它可以用来存储两个不同类型的值,头文件utilityint _bf;// balance factor 平衡因子用于AVL树的平衡操作。 -1 0 1是正常的平衡因子AVLTreeNode(const pairK, V kv)// 构造函数传参为一个pair对象: _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0) {}
};注意 给每个结点增加平衡因子并不是必须的只是实现AVL树的一种方式不引入平衡因子也可以实现AVL树只不过会麻烦一点。
AVL树的插入
AVL树插入结点时有以下三个步骤 按照二叉搜索树的插入方法找到待插入位置。找到待插入位置后将待插入结点插入到树中。更新平衡因子如果出现不平衡则需要进行旋转。 因为AVL树本身就是一棵二叉搜索树因此寻找结点的插入位置是非常简单的按照二叉搜索树的插入规则 待插入结点的key值比当前结点小就插入到该结点的左子树。待插入结点的key值比当前结点大就插入到该结点的右子树。待插入结点的key值与当前结点的key值相等就插入失败。 如此进行下去直到找到与待插入结点的key值相同的结点判定为插入失败或者最终走到空树位置进行结点插入。 与二叉搜索树插入结点不同的是AVL树插入结点后需要更新树中结点的平衡因子因为插入新结点后可能会影响树中某些结点的平衡因子。 由于一个结点的平衡因子是否需要更新是取决于该结点的左右子树的高度是否发生了变化因此插入一个结点后该结点的祖先结点的平衡因子可能需要更新。 所以我们插入结点后需要倒着往上更新平衡因子更新规则如下 新增结点在parent的右边parent的平衡因子1。新增结点在parent的左边parent的平衡因子-1。 每更新完一个结点的平衡因子后都需要进行以下判断
如果parent的平衡因子等于-1或者1表明还需要继续往上更新平衡因子。如果parent的平衡因子等于0表明无需继续往上更新平衡因子了。如果parent的平衡因子等于-2或者2表明此时以parent结点为根结点的子树已经不平衡了需要进行旋转处理。
判断理由说明
parent更新后的平衡因子分析-1或1只有0经过–/操作后会变成-1/1说明新结点的插入使得parent的左子树或右子树增高了即改变了以parent为根结点的子树的高度从而会影响parent的父结点的平衡因子因此需要继续往上更新平衡因子。0只有-1/1经过/–操作后会变成0说明新结点插入到了parent左右子树当中高度较矮的一棵子树插入后使得parent左右子树的高度相等了此操作并没有改变以parent为根结点的子树的高度从而不会影响parent的父结点的平衡因子因此无需继续往上更新平衡因子。-2或2此时parent结点的左右子树高度之差的绝对值已经超过1了不满足AVL树的要求因此需要进行旋转处理。
注意 parent的平衡因子在更新前只可能是-1/0/1AVL树中每个结点的左右子树高度之差的绝对值不超过1。
而在最坏情况下我们更新平衡因子时会一路更新到根结点。例如下面这种情况 说明一下 由于我们插入结点后需要倒着往上进行平衡因子的更新所以我们将AVL树结点的结构设置为了三叉链结构这样我们就可以通过父指针找到其父结点进而对其平衡因子进行更新。当然我们也可以不用三叉链结构可以在插入结点时将路径上的结点存储到一个栈当中当我们更新平衡因子时也可以通过这个栈来更新祖先结点的平衡因子但是相对较麻烦。 若是在更新平衡因子的过程当中出现了平衡因子为-2/2的结点这时我们需要对以该结点为根结点的树进行旋转处理而旋转处理分为四种在进行分类之前我们首先需要进行以下分析 我们将插入结点称为cur将其父结点称为parent那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子更新完parent结点的平衡因子后若是需要继续往上进行平衡因子的更新那么我们必定要执行以下逻辑
cur parent;
parent parent-_parent;这里我想说明的是当parent的平衡因子为-2/2时cur的平衡因子必定是-1/1而不会是0。
理由如下 若cur的平衡因子是0那么cur一定是新增结点而不是上一次更新平衡因子时的parent否则在上一次更新平衡因子时会因为parent的平衡因子为0而停止继续往上更新。
而cur是新增结点的话其父结点的平衡因子更新后一定是-1/0/1而不可能是-2/2因为新增结点最终会插入到一个空树当中在新增结点插入前其父结点的状态有以下两种可能 其父结点是一个左右子树均为空的叶子结点其平衡因子是0新增结点插入后其平衡因子更新为-1/1。其父结点是一个左子树或右子树为空的结点其平衡因子是-1/1新增结点插入到其父结点的空子树当中使得其父结点左右子树当中较矮的一棵子树增高了新增结点后其平衡因子更新为0。 综上所述当parent的平衡因子为-2/2时cur的平衡因子必定是-1/1而不会是0。
根据此结论我们可以将旋转处理分为以下四类 当parent的平衡因子为-2cur的平衡因子为-1时进行右单旋。当parent的平衡因子为-2cur的平衡因子为1时进行左右双旋。当parent的平衡因子为2cur的平衡因子为-1时进行右左双旋。当parent的平衡因子为2cur的平衡因子为1时进行左单旋。 并且在进行旋转处理后就无需继续往上更新平衡因子了因为旋转后树的高度变为插入之前了即树的高度没有发生变化也就不会影响其父结点的平衡因子了。
AVL树的旋转
左单旋
旋转示意图如下 左单旋的步骤如下
让subR的左子树作为parent的右子树。让parent作为subR的左子树。让subR作为整个子树的根。更新平衡因子。
左单旋后满足二叉搜索树的性质
subR的左子树当中结点的值本身就比parent的值大因此可以作为parent的右子树。parent及其左子树当中结点的值本身就比subR的值小因此可以作为subR的左子树。
平衡因子更新如下 可以看到经过左单旋后树的高度变为插入之前了即树的高度没有发生变化所以左单旋后无需继续往上更新平衡因子。
代码如下
// 左单旋
void RotateLeft(Node *parent) {Node *subR parent-_right;// 要旋转的parent的右子树Node *subRL subR-_left; // 子树的左子树// 旋转链接parent-_right subRL;// subRL不为nullptrif (subRL) {subRL-_parent parent;}// 需要记录要旋转的树还有没有父亲Node *ppnode parent-_parent;subR-_left parent;parent-_parent subR;// 如果ppnode为nullptr说明parent一开始为根旋转后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;
}注意 结点是三叉链结构改变结点关系时需要跟着改变父指针的指向。
右单旋
旋转示意图如下 右单旋的步骤如下 让subL的右子树作为parent的左子树。让parent作为subL的右子树。让subL作为整个子树的根。更新平衡因子。 右单旋后满足二叉搜索树的性质 subL的右子树当中结点的值本身就比parent的值小因此可以作为parent的左子树。parent及其右子树当中结点的值本身就比subL的值大因此可以作为subL的右子树。 平衡因子更新如下 可以看到经过右单旋后树的高度变为插入之前了即树的高度没有发生变化所以右单旋后无需继续往上更新平衡因子。
代码如下
// 右单旋
void RotateRight(Node *parent) {Node *subL parent-_left;//parent的左数Node *subLR subL-_right;//subL的右树parent-_left subLR;//将subLR的右数作为parent的左数if (subLR) {subLR-_parent parent;//更新subLR的父亲}Node *ppnode parent-_parent;//记录祖先结点subL-_right parent; //subL的右数更新为parentparent-_parent subL;//更新parent的父亲//祖先结点链接更新后的父亲(subL)if (ppnode nullptr) {_root subL;_root-_parent nullptr;} else {if (ppnode-_left parent) {ppnode-_left subL;} else {ppnode-_right subL;}subL-_parent ppnode;}//更新平衡因子parent-_bf subL-_bf 0;
}注意 结点是三叉链结构改变结点关系时需要跟着改变父指针的指向。
左右双旋
左右双旋的步骤如下 1、插入新结点。 2、以30为旋转点进行左单旋。 3、以90为旋转点进行右单旋。 左右双旋的步骤如下 以subL为旋转点进行左单旋。以parent为旋转点进行右单旋。更新平衡因子。 左右双旋后满足二叉搜索树的性质
左右双旋后实际上就是让subLR的左子树和右子树分别作为subL和parent的右子树和左子树再让subL和parent分别作为subLR的左右子树最后让subLR作为整个子树的根结合图理解。
subLR的左子树当中的结点本身就比subL的值大因此可以作为subL的右子树。
subLR的右子树当中的结点本身就比parent的值小因此可以作为parent的左子树。
经过步骤1/2后subL及其子树当中结点的值都就比subLR的值小而parent及其子树当中结点的值都就比subLR的值大因此它们可以分别作为subLR的左右子树。
左右双旋后平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况 1、当subLR原始平衡因子是-1时左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0。 2、当subLR原始平衡因子是1时左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0。 3、当subLR原始平衡因子是0时左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0。 可以看到经过左右双旋后树的高度变为插入之前了即树的高度没有发生变化所以左右双旋后无需继续往上更新平衡因子。
代码如下
// 双旋(左右旋转)
void RotateLR(Node *parent) {Node *subL parent-_left;Node *subLR subL-_right;// subLR的平衡因子决定了在哪里插入int bf subLR-_bf;RotateLeft(parent-_left);RotateRight(parent);//更新平衡因子if (bf 1) {parent-_bf 0;subLR-_bf 0;subL-_bf -1;} else if (bf -1) {parent-_bf 1;subLR-_bf 0;subL-_bf 0;} else if (bf 0) {parent-_bf 0;subLR-_bf 0;subL-_bf 0;} else {assert(false);}
}右左双旋
右左双旋的步骤如下 1、插入新结点。 2、以90为旋转点进行右单旋。从subR的位置开始右单旋转 3、以30为旋转点进行左单旋。以parent开始右单旋 4.更新平衡因子 右左双旋后满足二叉搜索树的性质
右左双旋后实际上就是让subRL的左子树和右子树分别作为parent和subR的右子树和左子树再让parent和subR分别作为subRL的左右子树最后让subRL作为整个子树的根结合图理解。
subRL的左子树当中的结点本身就比parent的值大因此可以作为parent的右子树。subRL的右子树当中的结点本身就比subR的值小因此可以作为subR的左子树。经过步骤1/2后parent及其子树当中结点的值都就比subRL的值小而subR及其子树当中结点的值都就比subRL的值大因此它们可以分别作为subRL的左右子树。 右左双旋后平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况 1、当subRL原始平衡因子是1时左右双旋后parent、subR、subRL的平衡因子分别更新为-1、0、0。 2、当subRL原始平衡因子是-1时左右双旋后parent、subR、subRL的平衡因子分别更新为0、1、0。 3、当subRL原始平衡因子是0时左右双旋后parent、subR、subRL的平衡因子分别更新为0、0、0。 可以看到经过右左双旋后树的高度变为插入之前了即树的高度没有发生变化所以右左双旋后无需继续往上更新平衡因子。
// 双旋(右左旋转)
void RotateRL(Node *parent) {Node *subR parent-_right;Node *subRL subR-_left;int bf subRL-_bf;//右单旋从parent-right开始旋转RotateRight(parent-_right);RotateLeft(parent);//更新平衡因子if (bf 1) {parent-_bf -1;subRL-_bf 0;subR-_bf 0;} else if (bf -1) {parent-_bf 0;subRL-_bf 0;subR-_bf 1;} else if (bf 0) {parent-_bf 0;subRL-_bf 0;subR-_bf 0;} else {assert(false);}
}插入代码
bool Insert(const pairK, V kv) {//空树就new一个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-_right;} else if (kv.first cur-_kv.first) {parent cur;cur cur-_left;} else {// 相等则不插入,return false;}}// cur走到了合适的位置cur new Node(kv);// 选择插入到parent的左边还是右边if (kv.first parent-_kv.first) {parent-_left cur;} else {parent-_right cur;}// cur链接parentcur-_parent parent;// 更新平衡因子// 1.如果更新完以后平衡因子没有出现问题(|bf|1)不需要处理// 2.如果更新完以后平衡出现问题(|bf|1)需要处理(旋转)// 插入新增节点。会影响祖先的平衡因子(全部或者部分)// 1、cur parent-right parent-bf// 2、cur parent-left parent-bf--// 什么决定了是否继续往上更新祖先节点取决于parent所在的子树高度是否变化变了继续更新不变则不再更新// a、parent-bf1 || parent-bf -1 parent所在的子树变了需要继续更新祖先节点// b、parent-bf2 || parent-bf -1 parent所在的子树不平衡需要处理这颗子树(旋转)// c、parent-bf0, parent所在的子树高度不变不用继续网上更新。插入结束 为什么?// 说明插入前parent-bf1 or -1插入之前一边高一边低。插入节点插入矮的那边它的高度不变while (parent) {//插入后,判断孩子插入到左边还是右边 进行 --平衡因子if (cur parent-_right) {parent-_bf;} else {parent-_bf--;}if (parent-_bf 1 || parent-_bf -1) {// 更新祖先节点的bfparent parent-_parent;cur cur-_parent;} else if (parent-_bf 0) {// 平衡不需要处理break;} else if (parent-_bf 2 || parent-_bf -2) {// 需要旋转处理// 当parent-bf 2 cur-bf 1 右边高需要左单旋// 当parent-_bf -2 cur-_bf -1 左边高需要右单旋// 当parent-_bf -2 cur-_bf 1 需要左右双旋转// 当parent-_bf 2 cur-_bf -1 需要右左双旋转if (parent-_bf 2 cur-_bf 1) {RotateLeft(parent);} else if (parent-_bf -2 cur-_bf -1) {RotateRight(parent);} else if (parent-_bf -2 cur-_bf 1) {RotateLR(parent);} else if (parent-_bf 2 cur-_bf -1) {RotateRL(parent);}break;}}return true;
}AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制也就是说AVL树也是二叉搜索树因此我们可以先获取二叉树的中序遍历序列来判断二叉树是否为二叉搜索树。
代码如下
void _InOrder(Node *root) {if (root nullptr) {return;}_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);
}void InOrder() {_InOrder(this-_root);cout endl;
}但中序有序只能证明是二叉搜索树要证明二叉树是AVL树还需验证二叉树的平衡性在该过程中我们可以顺便检查每个结点当中平衡因子是否正确。
采用后序遍历变量步骤如下 从叶子结点处开始计算每课子树的高度。每棵子树的高度 左右子树中高度的较大值 1先判断左子树是否是平衡二叉树。再判断右子树是否是平衡二叉树。若左右子树均为平衡二叉树则返回当前子树的高度给上一层继续判断上一层的子树是否是平衡二叉树直到判断到根为止。若判断过程中某一棵子树不是平衡二叉树则该树也就不是平衡二叉树了 代码如下
// 判断是否是平衡树
bool _IsBalanace(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 节点平衡因子异常 endl;return false;}return abs(leftHeight - rightHeight) 2 _IsBalanace(root-_left) _IsBalanace(root-_right);
}bool IsBalanace() {return _IsBalanace(this-_root);
}AVL树的查找
AVL树的查找函数与二叉搜索树的查找方式一模一样逻辑如下 若树为空树则查找失败返回nullptr。若key值小于当前结点的值则应该在该结点的左子树当中进行查找。若key值大于当前结点的值则应该在该结点的右子树当中进行查找。若key值等于当前结点的值则查找成功返回对应结点。 代码如下
Node *Find(const K key) {Node *cur _root;while (cur) {//key值小于该结点的值if (key cur-_kv.first) {//在该结点的左子树当中查找cur cur-_left;} else if (key cur-_kv.first) {//key值大于该结点的值cur cur-_right;//在该结点的右子树当中查找} else {//找到了目标结点return cur;//返回该结点}}return nullptr;
}AVL树的修改
实现修改AVL树当中指定key值结点的value我们可以实现一个Modify函数该函数当中的逻辑如下
调用查找函数获取指定key值的结点。对该结点的value进行修改。
代码如下
bool Modify(const K key, const V value) {Node *ret Find(key);//没找到key则返回falseif (ret nullptr) {return false;}ret-_kv.second value;return true;
}AVL树的删除
要进行结点的删除首先需要在树中找到对应key值的结点寻找待删除结点的方法和二叉搜索树相同
先找到待删除的结点。若找到的待删除结点的左右子树均不为空则需要使用替换法进行删除。
替换法删除指的是让待删除结点左子树当中key值最大的结点或待删除结点右子树当中值最小的结点代替待删除结点被删除代码中以后者为例然后再将待删除结点的key值以及value值都改为代替其被删除的结点的值即可。
在找到实际需要被删除的结点后我们先不进行实际的删除而是先进行平衡因子的更新不然后续更新平衡因子时特别麻烦而更新平衡因子时的规则与插入结点时的规则是相反的
更新规则如下
删除的结点在parent的右边parent的平衡因子–删除的结点在parent的左边parent的平衡因子
并且每更新完一个结点的平衡因子后都需要进行以下判断
如果parent的平衡因子等于-1或者1表明无需继续往上更新平衡因子了。如果parent的平衡因子等于0表明还需要继续往上更新平衡因子。如果parent的平衡因子等于-2或者2表明此时以parent结点为根结点的子树已经不平衡了需要进行旋转处理。
判断理由说明
parent更新后的平衡因子分析-1或1只有0经过–/操作后会变成-1/1说明原来parent的左子树和右子树高度相同现在我们删除一个结点并不会影响以parent为根结点的子树的高度从而变化影响parent的父结点的平衡因子因此无需继续往上更新平衡因子。0只有-1/1经过–/操作后会变成0说明本次删除操作使得parent的左右子树当中较高的一棵子树的高度降低了即改变了以parent为根结点的子树的高度从而会影响parent的父结点的平衡因子因此需要继续往上更新平衡因子。-2或2此时parent结点的左右子树高度之差的绝对值已经超过1了不满足AVL树的要求因此需要进行旋转处理。
注意parent的平衡因子在更新前只可能是-1/0/1AVL树中每个结点的左右子树高度之差的绝对值不超过1。
而在最坏情况下删除结点后更新平衡因子时也会一路更新到根结点。例如下面这种情况 在更新完平衡因子后我们再进行实际删除结点的操作因为实际删除结点的左右子树当中至少有一个为空树因此我们实际删除结点时的逻辑如下
若实际删除结点的左子树为空则让其parent链接到实际删除结点的右子树最后再删除结点即可。若实际删除结点的右子树为空则让其parent链接到实际删除结点的左子树最后再删除结点即可。但是要注意因为结点是三叉链结构因此在链接结点的过程中需要建立两个结点之间的双向关系。
在进行旋转处理时我们将其分为以下六种情况
当parent的平衡因子为-2parent的左孩子的平衡因子为-1时进行右单旋当parent的平衡因子为-2parent的左孩子的平衡因子为1时进行左右双旋当parent的平衡因子为-2parent的左孩子的平衡因子为0时也进行右单旋当parent的平衡因子为2parent的右孩子的平衡因子为-1时进行右左双旋当parent的平衡因子为2parent的右孩子的平衡因子为1时进行左单旋当parent的平衡因子为2parent的右孩子的平衡因子为0时也进行左单旋
与插入结点不同的是删除结点时若是进行了旋转处理那么在进行旋转处理后我们必须继续往上更新平衡因子因为旋转的本质就是降低树的高度旋转后树的高度降低了就会影响其父结点的平衡因子因此我们还需要继续往上更新平衡因子。
注意 上述旋转处理的六种情况当中若属于情况三或情况六那么在旋转后无需继续往上更新平衡因子因为这两种情况旋转后树的高度并没有发生变化。
代码如下
bool Erase(const K key) {//遍历二叉树Node *parent nullptr;Node *cur _root;//用于标记实际的删除结点及其父结点Node *delParentPos nullptr;Node *delPos nullptr;//找key值while (cur) {if (key cur-_kv.first) {parent cur;cur cur-_left;} else if (key cur-_kv.first) {parent cur;cur cur-_right;} else {//找到待删除结点//待删除结点的左子树为空if (cur-_left nullptr) {//待删除结点是根结点让根结点的右子树作为新的根结点if (cur _root) {_root _root-_right;if (_root) {_root-_parent nullptr;}delete cur;} else {//带删除结点不是根结点delParentPos parent;//标记实际删除结点的父结点delPos cur; //标记实际删除的结点}break; 跳出循环,之后更新平衡因子} else if (cur-_right nullptr) {//待删除结点的右子树为空//待删除结点是根结点,让根结点的左子树作为新的根结点if (cur _root) {_root _root-_left;if (_root) {_root-_parent nullptr;}delete cur;return true;} else {//带删除结点不是根结点delParentPos parent;delPos cur;}break;//跳出循环,之后更新平衡因子} else { //待删除结点左右两边都不为空//使用替换法进行删除//找右子树中的最小结点成为待删除结点作为子树的根Node *minParent cur;Node *minRight cur-_right;//最小结点在最左边while (minRight-_left) {minParent minRight;minRight minRight-_left;}//更新待删除结点cur-_kv.first minRight-_kv.first;cur-_kv.second minRight-_kv.second;//更新待删除的结点此时待删除的结点就是minRightdelParentPos minParent;delPos minRight;//跳出循环,更新平衡因子break;}}}//key值不对走到了nullptr,还没有找到key说明要找的key不存在,返回falseif (delPos nullptr) {//删除结点没有修改过,则返回falsereturn false;}//记录待删除结点及其父结点用于后续实际删除Node *del delPos;Node *delParent delParentPos;//更新平衡因子//待删除的结点不是根while (delPos ! _root) {//删除结点在父结点左边需要在右边需要--if (delPos delParentPos-_left) {delParentPos-_bf;} else if (delPos delParent-_right) {delParentPos-_bf--;}//判断是否更新结束或需要进行旋转//_bf 0 需要向上更新//_bf -1/1 不需要更新//_bf -2/2 需要旋转if (delParentPos-_bf 0) {//delParentPos树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子delPos delParentPos;delParentPos delParentPos-_parent;} else if (delParentPos-_bf -1 || delParentPos-_bf 1) {//delParent树的高度没有发生变化不会影响其父结点及以上结点的平衡因子break;} else if (delParentPos-_bf -2 || delParentPos-_bf 2) {//6种旋转if (delParentPos-_bf -2) {if (delParentPos-_left-_bf -1) {Node *tmp delParentPos-_left;//记录delParentPos右旋转后新的根结点RotateRight(delParentPos); //右单旋delParentPos tmp; //更新根结点} else if (delParentPos-_left-_bf 1) {Node *tmp delParentPos-_left-_right;//记录delParentPos左右双旋后新的根结点RotateLR(delParentPos); //左右双旋delParentPos tmp;} else {Node *tmp delParentPos-_left;RotateRight(delParentPos);//右单旋delParentPos tmp; //更新根结点//平衡因子调整delParentPos-_bf 1;delParentPos-_right-_bf -1;break;}} else if (delParentPos-_bf 2) {if (delParentPos-_right-_bf -1) {Node *tmp delParentPos-_right-_left;//记录delParentPos右左旋转后新的根结点RotateRL(delParentPos); //右左双旋delParentPos tmp;} else if (delParentPos-_right-_bf 1) {Node *tmp delParentPos-_right;//记录delParentPos左旋转后新的根结点RotateLeft(delParentPos); //左旋转delParentPos tmp;} else {//bf0Node *tmp delParentPos-_right;RotateLeft(delParentPos);delParentPos tmp;//更新平衡因子delParentPos-_bf -1;delParentPos-_bf 1;break;}}//旋转后delParentPos树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子delPos delParentPos;delParentPos delParentPos-_parent;} else {//在删除前树的平衡因子就有问题assert(false);}}//进行实际删除if (del-_left nullptr) { //实际删除结点的左子树为空if (del delParent-_left) {//实际删除结点是其父结点的左孩子//让父亲的左孩子指向被删除结点的有孩子delParent-_left del-_right;//如果有孩子不为空,绑定右孩子的父亲if (del-_right) {del-_right-_parent delParent;}} else {//实际删除结点是其父结点的右孩子//直接领养被删除结点的右孩子,右孩子不为空则绑定父亲delParent-_right del-_right;if (del-_right) {del-_right-_parent delParent;}}} else {//实际删除结点的右子树为//实际删除结点是其父结点的左孩子if (del delParent-_left) {//被删除结点父亲领养被删除结点的左孩子delParent-_left del-_left;//绑定父亲if (del-_left) {del-_left-_parent delParent;}} else {//实际删除结点是其父结点的右孩子//领养被删除结点左孩子,并绑定父亲delParent-_right del-_left;if (del-_left) {del-_left-_parent delParent;}}}delete del;return true;
}AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个结点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即logN。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。
因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的即不会改变可以考虑AVL树但当一个结构经常需要被修改时AVL树就不太适合了。
AVL树的代码测试
AVLTree.h文件
#pragma once
#include assert.h
#include iostream
#include utility
using namespace std;// AVL平衡树左右高度差不超过1
templateclass K, class V
struct AVLTreeNode {AVLTreeNodeK, V *_left;AVLTreeNodeK, V *_right;AVLTreeNodeK, V *_parent;pairK, V _kv;// 存储键值对的pair对象pair是一个模板类它可以用来存储两个不同类型的值,头文件utilityint _bf;// balance factor 平衡因子用于AVL树的平衡操作。 -1 0 1是正常的平衡因子AVLTreeNode(const pairK, V kv)// 构造函数传参为一个pair对象: _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0) {}
};templateclass K, class V
class AVLTree {
public:typedef AVLTreeNodeK, V Node;bool Insert(const pairK, V kv) {//空树就new一个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-_right;} else if (kv.first cur-_kv.first) {parent cur;cur cur-_left;} else {// 相等则不插入,return false;}}// cur走到了合适的位置cur new Node(kv);// 选择插入到parent的左边还是右边if (kv.first parent-_kv.first) {parent-_left cur;} else {parent-_right cur;}// cur链接parentcur-_parent parent;// 更新平衡因子// 1.如果更新完以后平衡因子没有出现问题(|bf|1)不需要处理// 2.如果更新完以后平衡出现问题(|bf|1)需要处理(旋转)// 插入新增节点。会影响祖先的平衡因子(全部或者部分)// 1、cur parent-right parent-bf// 2、cur parent-left parent-bf--// 什么决定了是否继续往上更新祖先节点取决于parent所在的子树高度是否变化变了继续更新不变则不再更新// a、parent-bf1 || parent-bf -1 parent所在的子树变了需要继续更新祖先节点// b、parent-bf2 || parent-bf -1 parent所在的子树不平衡需要处理这颗子树(旋转)// c、parent-bf0, parent所在的子树高度不变不用继续网上更新。插入结束 为什么?// 说明插入前parent-bf1 or -1插入之前一边高一边低。插入节点插入矮的那边它的高度不变while (parent) {//插入后,判断孩子插入到左边还是右边 进行 --平衡因子if (cur parent-_right) {parent-_bf;} else {parent-_bf--;}if (parent-_bf 1 || parent-_bf -1) {// 更新祖先节点的bfparent parent-_parent;cur cur-_parent;} else if (parent-_bf 0) {// 平衡不需要处理break;} else if (parent-_bf 2 || parent-_bf -2) {// 需要旋转处理// 当parent-bf 2 cur-bf 1 右边高需要左单旋// 当parent-_bf -2 cur-_bf -1 左边高需要右单旋// 当parent-_bf -2 cur-_bf 1 需要左右双旋转// 当parent-_bf 2 cur-_bf -1 需要右左双旋转if (parent-_bf 2 cur-_bf 1) {RotateLeft(parent);} else if (parent-_bf -2 cur-_bf -1) {RotateRight(parent);} else if (parent-_bf -2 cur-_bf 1) {RotateLR(parent);} else if (parent-_bf 2 cur-_bf -1) {RotateRL(parent);}break;}}return true;}void InOrder() {_InOrder(this-_root);cout endl;}bool IsBalanace() {return _IsBalanace(this-_root);}int Height() {return _Height(this-_root);}int _Height(Node *root) {if (root nullptr)return 0;int leftHeight _Height(root-_left) 1;int rightHeight _Height(root-_right) 1;return leftHeight rightHeight ? leftHeight : rightHeight;}// 判断是否是平衡树bool _IsBalanace(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 节点平衡因子异常 endl;return false;}return abs(leftHeight - rightHeight) 2 _IsBalanace(root-_left) _IsBalanace(root-_right);}bool Modify(const K key, const V value) {Node *ret Find(key);//没找到key则返回falseif (ret nullptr) {return false;}ret-_kv.second value;return true;}bool Erase(const K key) {//遍历二叉树Node *parent nullptr;Node *cur _root;//用于标记实际的删除结点及其父结点Node *delParentPos nullptr;Node *delPos nullptr;//找key值while (cur) {if (key cur-_kv.first) {parent cur;cur cur-_left;} else if (key cur-_kv.first) {parent cur;cur cur-_right;} else {//找到待删除结点//待删除结点的左子树为空if (cur-_left nullptr) {//待删除结点是根结点让根结点的右子树作为新的根结点if (cur _root) {_root _root-_right;if (_root) {_root-_parent nullptr;}delete cur;} else {//带删除结点不是根结点delParentPos parent;//标记实际删除结点的父结点delPos cur; //标记实际删除的结点}break; 跳出循环,之后更新平衡因子} else if (cur-_right nullptr) {//待删除结点的右子树为空//待删除结点是根结点,让根结点的左子树作为新的根结点if (cur _root) {_root _root-_left;if (_root) {_root-_parent nullptr;}delete cur;return true;} else {//带删除结点不是根结点delParentPos parent;delPos cur;}break;//跳出循环,之后更新平衡因子} else { //待删除结点左右两边都不为空//使用替换法进行删除//找右子树中的最小结点成为待删除结点作为子树的根Node *minParent cur;Node *minRight cur-_right;//最小结点在最左边while (minRight-_left) {minParent minRight;minRight minRight-_left;}//更新待删除结点cur-_kv.first minRight-_kv.first;cur-_kv.second minRight-_kv.second;//更新待删除的结点此时待删除的结点就是minRightdelParentPos minParent;delPos minRight;//跳出循环,更新平衡因子break;}}}//key值不对走到了nullptr,还没有找到key说明要找的key不存在,返回falseif (delPos nullptr) {//删除结点没有修改过,则返回falsereturn false;}//记录待删除结点及其父结点用于后续实际删除Node *del delPos;Node *delParent delParentPos;//更新平衡因子//待删除的结点不是根while (delPos ! _root) {//删除结点在父结点左边需要在右边需要--if (delPos delParentPos-_left) {delParentPos-_bf;} else if (delPos delParent-_right) {delParentPos-_bf--;}//判断是否更新结束或需要进行旋转//_bf 0 需要向上更新//_bf -1/1 不需要更新//_bf -2/2 需要旋转if (delParentPos-_bf 0) {//delParentPos树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子delPos delParentPos;delParentPos delParentPos-_parent;} else if (delParentPos-_bf -1 || delParentPos-_bf 1) {//delParent树的高度没有发生变化不会影响其父结点及以上结点的平衡因子break;} else if (delParentPos-_bf -2 || delParentPos-_bf 2) {//6种旋转if (delParentPos-_bf -2) {if (delParentPos-_left-_bf -1) {Node *tmp delParentPos-_left;//记录delParentPos右旋转后新的根结点RotateRight(delParentPos); //右单旋delParentPos tmp; //更新根结点} else if (delParentPos-_left-_bf 1) {Node *tmp delParentPos-_left-_right;//记录delParentPos左右双旋后新的根结点RotateLR(delParentPos); //左右双旋delParentPos tmp;} else {Node *tmp delParentPos-_left;RotateRight(delParentPos);//右单旋delParentPos tmp; //更新根结点//平衡因子调整delParentPos-_bf 1;delParentPos-_right-_bf -1;break;}} else if (delParentPos-_bf 2) {if (delParentPos-_right-_bf -1) {Node *tmp delParentPos-_right-_left;//记录delParentPos右左旋转后新的根结点RotateRL(delParentPos); //右左双旋delParentPos tmp;} else if (delParentPos-_right-_bf 1) {Node *tmp delParentPos-_right;//记录delParentPos左旋转后新的根结点RotateLeft(delParentPos); //左旋转delParentPos tmp;} else {//bf0Node *tmp delParentPos-_right;RotateLeft(delParentPos);delParentPos tmp;//更新平衡因子delParentPos-_bf -1;delParentPos-_bf 1;break;}}//旋转后delParentPos树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子delPos delParentPos;delParentPos delParentPos-_parent;} else {//在删除前树的平衡因子就有问题assert(false);}}//进行实际删除if (del-_left nullptr) { //实际删除结点的左子树为空if (del delParent-_left) {//实际删除结点是其父结点的左孩子//让父亲的左孩子指向被删除结点的有孩子delParent-_left del-_right;//如果有孩子不为空,绑定右孩子的父亲if (del-_right) {del-_right-_parent delParent;}} else {//实际删除结点是其父结点的右孩子//直接领养被删除结点的右孩子,右孩子不为空则绑定父亲delParent-_right del-_right;if (del-_right) {del-_right-_parent delParent;}}} else {//实际删除结点的右子树为//实际删除结点是其父结点的左孩子if (del delParent-_left) {//被删除结点父亲领养被删除结点的左孩子delParent-_left del-_left;//绑定父亲if (del-_left) {del-_left-_parent delParent;}} else {//实际删除结点是其父结点的右孩子//领养被删除结点左孩子,并绑定父亲delParent-_right del-_left;if (del-_left) {del-_left-_parent delParent;}}}delete del;return true;}private:void _InOrder(Node *root) {if (root nullptr) {return;}_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}// 左单旋void RotateLeft(Node *parent) {Node *subR parent-_right;// 要旋转的parent的右子树Node *subRL subR-_left; // 子树的左子树// 旋转链接parent-_right subRL;// subRL不为nullptrif (subRL) {subRL-_parent parent;}// 需要记录要旋转的树还有没有父亲Node *ppnode parent-_parent;subR-_left parent;parent-_parent subR;// 如果ppnode为nullptr说明parent一开始为根旋转后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;}// 右单旋void RotateRight(Node *parent) {Node *subL parent-_left;//parent的左数Node *subLR subL-_right;//subL的右树parent-_left subLR;//将subLR的右数作为parent的左数if (subLR) {subLR-_parent parent;//更新subLR的父亲}Node *ppnode parent-_parent;//记录祖先结点subL-_right parent; //subL的右数更新为parentparent-_parent subL;//更新parent的父亲//祖先结点链接更新后的父亲(subL)if (ppnode nullptr) {_root subL;_root-_parent nullptr;} else {if (ppnode-_left parent) {ppnode-_left subL;} else {ppnode-_right subL;}subL-_parent ppnode;}//更新平衡因子parent-_bf subL-_bf 0;}// 双旋(左右旋转)void RotateLR(Node *parent) {Node *subL parent-_left;Node *subLR subL-_right;// subLR的平衡因子决定了在哪里插入int bf subLR-_bf;RotateLeft(parent-_left);RotateRight(parent);//更新平衡因子if (bf 1) {parent-_bf 0;subLR-_bf 0;subL-_bf -1;} else if (bf -1) {parent-_bf 1;subLR-_bf 0;subL-_bf 0;} else if (bf 0) {parent-_bf 0;subLR-_bf 0;subL-_bf 0;} else {assert(false);}}// 双旋(右左旋转)void RotateRL(Node *parent) {Node *subR parent-_right;Node *subRL subR-_left;int bf subRL-_bf;//右单旋从parent-right开始旋转RotateRight(parent-_right);RotateLeft(parent);//更新平衡因子if (bf 1) {parent-_bf -1;subRL-_bf 0;subR-_bf 0;} else if (bf -1) {parent-_bf 0;subRL-_bf 0;subR-_bf 1;} else if (bf 0) {parent-_bf 0;subRL-_bf 0;subR-_bf 0;} else {assert(false);}}Node *Find(const K key) {Node *cur _root;while (cur) {//key值小于该结点的值if (key cur-_kv.first) {//在该结点的左子树当中查找cur cur-_left;} else if (key cur-_kv.first) {//key值大于该结点的值cur cur-_right;//在该结点的右子树当中查找} else {//找到了目标结点return cur;//返回该结点}}return nullptr;}private:Node *_root nullptr;
};
AVL树测试代码
#include AVLTree.h
#include cstdlib
#include ctime
#include iostream
using namespace std;void Test_AVLTree1() {int a[] {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};AVLTreeint, int t1;for (auto e: a) {// 条件断点if (e 14) {int x 0;// 不能为空语句}t1.Insert(make_pair(e, e));cout e 插入: t1.IsBalanace() endl;// 为了测试插入哪个异常所以加上了打印// 屏蔽右左旋转的平衡因子更新观察现象}t1.Erase(1);t1.InOrder();cout t1.IsBalanace() endl;
}void Test_AVLTree2() {srand(time(nullptr));const size_t n 1000000;AVLTreeint, int t;for (size_t i 0; i n; i) {size_t x rand();t.Insert(make_pair(x, x));}//t.InOrder();cout t.IsBalanace() endl;cout t.Height() endl;
}int main() {Test_AVLTree1();return 0;
}
