天津商城网站制作,wordpress最好用的企业主题,双云官方网站,帮境外赌场做网站是否有风险 #x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;数据结构 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 上一篇博客#xff1a;【数据… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接数据结构 长路漫漫浩浩万事皆有期待 上一篇博客【数据结构】搜索二叉树(C实现) 文章目录 AVL树的概念AVL树结点的定义AVL树的插入AVL树的旋转左单旋右单旋左右双旋右左双旋 AVL树的验证AVL树的查找AVL树的修改AVL树的删除AVL树的性能总结 AVL树的概念
二叉搜索树虽然可以提高我们查找数据的效率但如果插入二叉搜索树的数据是有序或接近有序的此时二叉搜索树会退化为单支树在单支树当中查找数据相当于在单链表当中查找数据效率是很低下的。
因此两位俄罗斯的数学家G.M.A delson-Velskii和E.M.Landis在1962年发明了解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1需要对树中的结点进行调整即可降低树的高度从而减少平均搜索长度。
AVL树可以是一棵空树也可以是具有以下性质的一棵二叉搜索树 树的左右子树都是AVL树。 树的左右子树高度之差简称平衡因子的绝对值不超过1-1/0/1。 如果一棵二叉搜索树的高度是平衡的它就是AVL树。如果它有n个结点其高度可保持在O(logN)搜索时间复杂度也是O(logN)。
注意 这里所说的二叉搜索树的高度是平衡的是指树中每个结点左右子树高度之差的绝对值不超过1因为只有满二叉树才能做到每个结点左右子树高度之差均为0。
AVL树结点的定义
我们这里直接实现KV模型的AVL树为了方便后续的操作这里将AVL树中的结点定义为三叉链结构并在每个结点当中引入平衡因子右子树高度-左子树高度。除此之外还需编写一个构造新结点的构造函数由于新构造结点的左右子树均为空树于是将新构造结点的平衡因子初始设置为0即可。
templateclass K, class V
struct AVLTreeNode
{//三叉链AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;//存储的键值对pairK, V _kv;//平衡因子(balance factor)int _bf; //右子树高度-左子树高度//构造函数AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};注意 给每个结点增加平衡因子并不是必须的只是实现AVL树的一种方式不引入平衡因子也可以实现AVL树只不过会麻烦一点。
AVL树的插入
AVL树插入结点时有以下三个步骤 按照二叉搜索树的插入方法找到待插入位置。 找到待插入位置后将待插入结点插入到树中。 更新平衡因子如果出现不平衡则需要进行旋转。 因为AVL树本身就是一棵二叉搜索树因此寻找结点的插入位置是非常简单的按照二叉搜索树的插入规则 待插入结点的key值比当前结点小就插入到该结点的左子树。 待插入结点的key值比当前结点大就插入到该结点的右子树。 待插入结点的key值与当前结点的key值相等就插入失败。 如此进行下去直到找到与待插入结点的key值相同的结点判定为插入失败或者最终走到空树位置进行结点插入。 与二叉搜索树插入结点不同的是AVL树插入结点后需要更新树中结点的平衡因子因为插入新结点后可能会影响树中某些结点的平衡因子。 由于一个结点的平衡因子是否需要更新是取决于该结点的左右子树的高度是否发生了变化因此插入一个结点后该结点的祖先结点的平衡因子可能需要更新。
所以我们插入结点后需要倒着往上更新平衡因子更新规则如下 新增结点在parent的右边parent的平衡因子。 新增结点在parent的左边parent的平衡因子−−。 每更新完一个结点的平衡因子后都需要进行以下判断 如果parent的平衡因子等于-1或者1表明还需要继续往上更新平衡因子。 如果parent的平衡因子等于0表明无需继续往上更新平衡因子了。 如果parent的平衡因子等于-2或者2表明此时以parent结点为根结点的子树已经不平衡了需要进行旋转处理。 判断理由说明
parent更新后的平衡因子为 -1或1 分析只有0经过−−/操作后会变成-1/1说明新结点的插入使得parent的左子树或右子树增高了即改变了以parent为根结点的子树的高度从而会影响parent的父结点的平衡因子因此需要继续往上更新平衡因子。
parent更新后的平衡因子为0 分析只有-1/1经过/−−操作后会变成0说明新结点插入到了parent左右子树当中高度较矮的一棵子树插入后使得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因为新增结点最终会插入到一个空树当中在新增结点插入前其父结点的状态有以下两种可能 1.其父结点是一个左右子树均为空的叶子结点其平衡因子是0新增结点插入后其平衡因子更新为-1/1。 2.其父结点是一个左子树或右子树为空的结点其平衡因子是-1/1新增结点插入到其父结点的空子树当中使得其父结点左右子树当中较矮的一棵子树增高了新增结点后其平衡因子更新为0。 综上所述当parent的平衡因子为-2/2时cur的平衡因子必定是-1/1而不会是0。
根据此结论我们可以将旋转处理分为以下四类 当parent的平衡因子为-2cur的平衡因子为-1时进行右单旋。 当parent的平衡因子为-2cur的平衡因子为1时进行左右双旋。 当parent的平衡因子为2cur的平衡因子为-1时进行右左双旋。 当parent的平衡因子为2cur的平衡因子为1时进行左单旋。 并且在进行旋转处理后就无需继续往上更新平衡因子了因为旋转后树的高度变为插入之前了即树的高度没有发生变化也就不会影响其父结点的平衡因子了。具体原因请看后面的旋转讲解。
代码如下
//插入函数
bool Insert(const pairK, V kv)
{if (_root nullptr) //若AVL树为空树则插入结点直接作为根结点{_root new Node(kv);return true;}//1、按照二叉搜索树的插入方法找到待插入位置Node* cur _root;Node* parent nullptr;while (cur){if (kv.first cur-_kv.first) //待插入结点的key值小于当前结点的key值{//往该结点的左子树走parent cur;cur cur-_left;}else if (kv.first cur-_kv.first) //待插入结点的key值大于当前结点的key值{//往该结点的右子树走parent cur;cur cur-_right;}else //待插入结点的key值等于当前结点的key值{//插入失败不允许key值冗余return false;}}//2、将待插入结点插入到树中cur new Node(kv); //根据所给值构造一个新结点if (kv.first parent-_kv.first) //新结点的key值小于parent的key值{//插入到parent的左边parent-_left cur;cur-_parent parent;}else //新结点的key值大于parent的key值{//插入到parent的右边parent-_right cur;cur-_parent parent;}//3、更新平衡因子如果出现不平衡则需要进行旋转while (cur ! _root) //最坏一路更新到根结点{if (cur parent-_left) //parent的左子树增高{parent-_bf--; //parent的平衡因子--}else if (cur parent-_right) //parent的右子树增高{parent-_bf; //parent的平衡因子}//判断是否更新结束或需要进行旋转if (parent-_bf 0) //更新结束新增结点把parent左右子树矮的那一边增高了此时左右高度一致{break; //parent树的高度没有发生变化不会影响其父结点及以上结点的平衡因子}else if (parent-_bf -1 || parent-_bf 1) //需要继续往上更新平衡因子{//parent树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子cur parent;parent parent-_parent;}else if (parent-_bf -2 || parent-_bf 2) //需要进行旋转此时parent树已经不平衡了{if (parent-_bf -2){if (cur-_bf -1){RotateR(parent); //右单旋}else //cur-_bf 1{RotateLR(parent); //左右双旋}}else //parent-_bf 2{if (cur-_bf -1){RotateRL(parent); //右左双旋}else //cur-_bf 1{RotateL(parent); //左单旋}}break; //旋转后就一定平衡了无需继续往上更新平衡因子(旋转后树高度变为插入之前了)}else{assert(false); //在插入前树的平衡因子就有问题}}return true; //插入成功
}AVL树的旋转
左单旋
说明 由于插入新结点后可能并不会立即进行旋转操作而可能是在更新其祖先结点的过程中出现了不平衡而进行的旋转操作因此用长方形表示下面的子树。
旋转示意图如下
左单旋的步骤如下 让subR的左子树作为parent的右子树。 让parent作为subR的左子树。 让subR作为整个子树的根。 更新平衡因子。 左单旋后满足二叉搜索树的性质 subR的左子树当中结点的值本身就比parent的值大因此可以作为parent的右子树。 parent及其左子树当中结点的值本身就比subR的值小因此可以作为subR的左子树。 平衡因子更新如下
可以看到经过左单旋后树的高度变为插入之前了即树的高度没有发生变化所以左单旋后无需继续往上更新平衡因子。
代码如下
//左单旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;Node* parentParent parent-_parent;//1、建立subR和parent之间的关系parent-_parent subR;subR-_left parent;//2、建立parent和subRL之间的关系parent-_right subRL;if (subRL)subRL-_parent parent;//3、建立parentParent和subR之间的关系if (parentParent nullptr){_root subR;subR-_parent nullptr; //subR的_parent指向需改变}else{if (parent parentParent-_left){parentParent-_left subR;}else //parent parentParent-_right{parentParent-_right subR;}subR-_parent parentParent;}//4、更新平衡因子subR-_bf parent-_bf 0;
}注意 结点是三叉链结构改变结点关系时需要跟着改变父指针的指向。
右单旋
说明 由于插入新结点后可能并不会立即进行旋转操作而可能是在更新其祖先结点的过程中出现了不平衡而进行的旋转操作因此用长方形表示下面的子树。
旋转示意图如下
右单旋的步骤如下 让subL的右子树作为parent的左子树。 让parent作为subL的右子树。 让subL作为整个子树的根。 更新平衡因子。 右单旋后满足二叉搜索树的性质 subL的右子树当中结点的值本身就比parent的值小因此可以作为parent的左子树。 parent及其右子树当中结点的值本身就比subL的值大因此可以作为subL的右子树。 平衡因子更新如下
可以看到经过右单旋后树的高度变为插入之前了即树的高度没有发生变化所以右单旋后无需继续往上更新平衡因子。
代码如下
//右单旋
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;Node* parentParent parent-_parent;//1、建立subL和parent之间的关系subL-_right parent;parent-_parent subL;//2、建立parent和subLR之间的关系parent-_left subLR;if (subLR)subLR-_parent parent;//3、建立parentParent和subL之间的关系if (parentParent nullptr){_root subL;_root-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subL;}else //parent parentParent-_right{parentParent-_right subL;}subL-_parent parentParent;}//4、更新平衡因子subL-_bf parent-_bf 0;
}注意 结点是三叉链结构改变结点关系时需要跟着改变父指针的指向。
左右双旋
说明 由于插入新结点后可能并不会立即进行旋转操作而可能是在更新其祖先结点的过程中出现了不平衡而进行的旋转操作因此用长方形表示下面的子树。 图中在b子树当中新增结点或是在c子树当中新增结点均会引发左右双旋动图中以在b子树当中新增结点为例。 动图当中的旋转示意图如下
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。
1、当subLR原始平衡因子是0时左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0。
可以看到经过左右双旋后树的高度变为插入之前了即树的高度没有发生变化所以左右双旋后无需继续往上更新平衡因子。
代码如下
//左右双旋
void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf; //subLR不可能为nullptr因为subL的平衡因子是1//1、以subL为旋转点进行左单旋RotateL(subL);//2、以parent为旋转点进行右单旋RotateR(parent);//3、更新平衡因子if (bf 1){subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 0){subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{assert(false); //在旋转前树的平衡因子就有问题}
}右左双旋
说明 由于插入新结点后可能并不会立即进行旋转操作而可能是在更新其祖先结点的过程中出现了不平衡而进行的旋转操作因此用长方形表示下面的子树。 图中在b子树当中新增结点或是在c子树当中新增结点均会引发右左双旋动图中以在c子树当中新增结点为例。 动图当中的旋转示意图如下
1、插入新结点。
2、以90为旋转点进行右单旋。
3、以30为旋转点进行左单旋。
右左双旋的步骤如下 以subR为旋转点进行右单旋。 以parent为旋转点进行左单旋。 更新平衡因子。 右左双旋后满足二叉搜索树的性质 右左双旋后实际上就是让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;//1、以subR为轴进行右单旋RotateR(subR);//2、以parent为轴进行左单旋RotateL(parent);//3、更新平衡因子if (bf 1){subRL-_bf 0;parent-_bf -1;subR-_bf 0;}else if (bf -1){subRL-_bf 0;parent-_bf 0;subR-_bf 1;}else if (bf 0){subRL-_bf 0;parent-_bf 0;subR-_bf 0;}else{assert(false); //在旋转前树的平衡因子就有问题}
}AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制也就是说AVL树也是二叉搜索树因此我们可以先获取二叉树的中序遍历序列来判断二叉树是否为二叉搜索树。
代码如下
//中序遍历
void Inorder()
{_Inorder(_root);
}
//中序遍历子函数
void _Inorder(Node* root)
{if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first ;_Inorder(root-_right);
}
但中序有序只能证明是二叉搜索树要证明二叉树是AVL树还需验证二叉树的平衡性在该过程中我们可以顺便检查每个结点当中平衡因子是否正确。
采用后序遍历变量步骤如下 1.从叶子结点处开始计算每课子树的高度。每棵子树的高度 左右子树中高度的较大值 1 2.先判断左子树是否是平衡二叉树。 3.再判断右子树是否是平衡二叉树。 4.若左右子树均为平衡二叉树则返回当前子树的高度给上一层继续判断上一层的子树是否是平衡二叉树直到判断到根为止。若判断过程中某一棵子树不是平衡二叉树则该树也就不是平衡二叉树了
代码如下
//判断是否为AVL树
bool IsAVLTree()
{int hight 0; //输出型参数return _IsBalanced(_root, hight);
}
//检测二叉树是否平衡
bool _IsBalanced(Node* root, int hight)
{if (root nullptr) //空树是平衡二叉树{hight 0; //空树的高度为0return true;}//先判断左子树int leftHight 0;if (_IsBalanced(root-_left, leftHight) false)return false;//再判断右子树int rightHight 0;if (_IsBalanced(root-_right, rightHight) false)return false;//检查该结点的平衡因子if (rightHight - leftHight ! root-_bf){cout 平衡因子设置异常 root-_kv.first endl;}//把左右子树的高度中的较大值1作为当前树的高度返回给上一层hight max(leftHight, rightHight) 1;return abs(rightHight - leftHight) 2; //平衡二叉树的条件
}
AVL树的查找
AVL树的查找函数与二叉搜索树的查找方式一模一样逻辑如下 1.若树为空树则查找失败返回nullptr。 2.若key值小于当前结点的值则应该在该结点的左子树当中进行查找。 3.若key值大于当前结点的值则应该在该结点的右子树当中进行查找。 4.若key值等于当前结点的值则查找成功返回对应结点。 代码如下
//查找函数
Node* Find(const K key)
{Node* cur _root;while (cur){if (key cur-_kv.first) //key值小于该结点的值{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);if (ret nullptr) //未找到指定key值的结点{return false;}ret-_kv.second value; //修改结点的valuereturn true;
}方法二
还有一种方法就是模仿CSTL库当中map的实现方式将插入函数的返回值设置为pair类型的插入函数的返回值逻辑如下 若待插入结点的键值key在map当中不存在则结点插入成功并返回插入后结点的指针和true。 若待插入结点的键值key在map当中已经存在则结点插入失败并返回map当中键值为key的结点的指针和false。 我们只需要对插入函数的返回值做一点点修改即可代码如下
//插入函数
pairNode*, bool Insert(const pairK, V kv)
{if (_root nullptr) //若AVL树为空树则插入结点直接作为根结点{_root new Node(kv);return make_pair(_root, true); //插入成功返回新插入结点和true}//1、按照二叉搜索树的插入方法找到待插入位置Node* cur _root;Node* parent nullptr;while (cur){if (kv.first cur-_kv.first) //待插入结点的key值小于当前结点的key值{//往该结点的左子树走parent cur;cur cur-_left;}else if (kv.first cur-_kv.first) //待插入结点的key值大于当前结点的key值{//往该结点的右子树走parent cur;cur cur-_right;}else //待插入结点的key值等于当前结点的key值{//插入失败不允许key值冗余return make_pair(cur, false); //插入失败返回已经存在的结点和false}}//2、将待插入结点插入到树中cur new Node(kv); //根据所给值构造一个新结点Node* newnode cur; //记录新插入的结点if (kv.first parent-_kv.first) //新结点的key值小于parent的key值{//插入到parent的左边parent-_left cur;cur-_parent parent;}else //新结点的key值大于parent的key值{//插入到parent的右边parent-_right cur;cur-_parent parent;}//3、更新平衡因子如果出现不平衡则需要进行旋转while (cur ! _root) //最坏一路更新到根结点{if (cur parent-_left) //parent的左子树增高{parent-_bf--; //parent的平衡因子--}else if (cur parent-_right) //parent的右子树增高{parent-_bf; //parent的平衡因子}//判断是否更新结束或需要进行旋转if (parent-_bf 0) //更新结束新增结点把parent左右子树矮的那一边增高了此时左右高度一致{break; //parent树的高度没有发生变化不会影响其父结点及以上结点的平衡因子}else if (parent-_bf -1 || parent-_bf 1) //需要继续往上更新平衡因子{//parent树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子cur parent;parent parent-_parent;}else if (parent-_bf -2 || parent-_bf 2) //需要进行旋转此时parent树已经不平衡了{if (parent-_bf -2){if (cur-_bf -1){RotateR(parent); //右单旋}else //cur-_bf 1{RotateLR(parent); //左右双旋}}else //parent-_bf 2{if (cur-_bf -1){RotateRL(parent); //右左双旋}else //cur-_bf 1{RotateL(parent); //左单旋}}break; //旋转后就一定平衡了无需继续往上更新平衡因子(旋转后树高度变为插入之前了)}else{assert(false); //在插入前树的平衡因子就有问题}}return make_pair(newnode, true); //插入成功返回新插入结点和true
}
然后我们再对运算符[ ]进行重载[ ]的重载逻辑如下 调用插入函数插入键值对。 拿出从插入函数获取到的结点。 返回该结点value的引用。 这样一来当我们使用[key]时其返回值逻辑如下 如果key不在树中则先插入键值对key, V()然后返回该键值对中value的引用。 如果key已经在树中则返回键值为key结点value的引用。 如此一来我们既可以用[ ]来进行指定key值结点value的修改又可以用[ ]进行数据的插入了并且插入时更方便。
代码如下
//operator[]重载
V operator[](const K key)
{//调用插入函数插入键值对pairNode*, bool ret Insert(make_pair(key, V()));//拿出从插入函数获取到的结点Node* node ret.first;//返回该结点value的引用return node-_kv.second;
}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的父结点的平衡因子因此无需继续往上更新平衡因子。
parent更新后的平衡因子为 0 分析只有-1/1经过/−−操作后会变成0说明本次删除操作使得parent的左右子树当中较高的一棵子树的高度降低了即改变了以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;while (cur){if (key cur-_kv.first) //所给key值小于当前结点的key值{//往该结点的左子树走parent cur;cur cur-_left;}else if (key cur-_kv.first) //所给key值大于当前结点的key值{//往该结点的右子树走parent cur;cur cur-_right;}else //找到了待删除结点{if (cur-_left nullptr) //待删除结点的左子树为空{if (cur _root) //待删除结点是根结点{_root _root-_right; //让根结点的右子树作为新的根结点if (_root)_root-_parent nullptr;delete cur; //删除原根结点return true; //根结点无祖先结点无需进行平衡因子的更新操作}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 //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent cur;Node* minRight cur-_right;while (minRight-_left){minParent minRight;minRight minRight-_left;}cur-_kv.first minRight-_kv.first; //将待删除结点的key改为minRight的keycur-_kv.second minRight-_kv.second; //将待删除结点的value改为minRight的valuedelParentPos minParent; //标记实际删除结点的父结点delPos minRight; //标记实际删除的结点break; //删除结点有祖先结点需更新平衡因子}}}if (delParentPos nullptr) //delParentPos没有被修改过说明没有找到待删除结点{return false;}//记录待删除结点及其父结点用于后续实际删除Node* del delPos;Node* delP delParentPos;//更新平衡因子while (delPos ! _root) //最坏一路更新到根结点{if (delPos delParentPos-_left) //delParentPos的左子树高度降低{delParentPos-_bf; //delParentPos的平衡因子}else if (delPos delParentPos-_right) //delParentPos的右子树高度降低{delParentPos-_bf--; //delParentPos的平衡因子--}//判断是否更新结束或需要进行旋转if (delParentPos-_bf 0)//需要继续往上更新平衡因子{//delParentPos树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子delPos delParentPos;delParentPos delParentPos-_parent;}else if (delParentPos-_bf -1 || delParentPos-_bf 1) //更新结束{break; //delParent树的高度没有发生变化不会影响其父结点及以上结点的平衡因子}else if (delParentPos-_bf -2 || delParentPos-_bf 2) //需要进行旋转此时delParentPos树已经不平衡了{if (delParentPos-_bf -2){if (delParentPos-_left-_bf -1){Node* tmp delParentPos-_left; //记录delParentPos右旋转后新的根结点RotateR(delParentPos); //右单旋delParentPos tmp; //更新根结点}else if(delParentPos-_left-_bf 1){Node* tmp delParentPos-_left-_right; //记录delParentPos左右旋转后新的根结点RotateLR(delParentPos); //左右双旋delParentPos tmp; //更新根结点}else //delParentPos-_left-_bf 0{Node* tmp delParentPos-_left; //记录delParentPos右旋转后新的根结点RotateR(delParentPos); //右单旋delParentPos tmp; //更新根结点//平衡因子调整delParentPos-_bf 1;delParentPos-_right-_bf -1;break; //更正}}else //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左旋转后新的根结点RotateL(delParentPos); //左单旋delParentPos tmp; //更新根结点}else //delParentPos-_right-_bf 0{Node* tmp delParentPos-_right; //记录delParentPos左旋转后新的根结点RotateL(delParentPos); //左单旋delParentPos tmp; //更新根结点//平衡因子调整delParentPos-_bf -1;delParentPos-_left-_bf 1;break; //更正}}//delParentPos树的高度变化会影响其父结点的平衡因子需要继续往上更新平衡因子delPos delParentPos;delParentPos delParentPos-_parent;//break; //error}else{assert(false); //在删除前树的平衡因子就有问题}}//进行实际删除if (del-_left nullptr) //实际删除结点的左子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_right;if (del-_right)del-_right-_parent parent;}else //实际删除结点是其父结点的右孩子{delP-_right del-_right;if (del-_right)del-_right-_parent parent;}}else //实际删除结点的右子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_left;if (del-_left)del-_left-_parent parent;}else //实际删除结点是其父结点的右孩子{delP-_right del-_left;if (del-_left)del-_left-_parent parent;}}delete del; //实际删除结点return true;
}AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个结点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即logN。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。
因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的即不会改变可以考虑AVL树但当一个结构经常需要被修改时AVL树就不太适合了。
总结
今天我们比较详细地学习了AVL树的相关知识了解了一些有关的底层原理。接下来我们将进行红黑树的学习。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
