做集群网站,隆力奇会员管理系统,排名优化价格,注塑模具东莞网站建设AVL 树的概念 二叉搜索树虽可以缩短查找的效率#xff0c;但如果数据有序或接近有序二叉搜索树将退化为单支树#xff0c;查找元素相当于在顺序表中搜索元素#xff0c;效率低下。因此#xff0c;两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一…
AVL 树的概念 二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法 当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。 一棵 AVL 树或者是空树或者是具有以下性质的二叉搜索树 它的左右子树都是AVL树。 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n)搜索时间复杂度O( l o g 2 n log_2 n log2n)。 AVL 树的基本结构
AVL 树的实现方式有很多我们这里选择一种较为简单的方式引入平衡因子来维护 AVL 树的高度。因为在实现 AVL 树的时候涉及调整树的高度此过程需要频繁的通过子节点找到父节点所以 AVL 树的节点需要定义成三叉链式存储。
AVL 树存储的数据我们定义成 key-val 键值对的形式因为 map 和 set 存储的数据就是键值对的形式而 map 和 set 又和 AVL 树有一定的关系。所以我们只需要模仿着做就行啦
#pragma oncetemplateclass K, class V
struct AVLTreeNode
{pairK, v _kv;AVLTreeNodeK, V* _parent;AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;int _bf; //平衡因子AVLTreeNode(const pairK, V kv):_kv(kv),_parent(nullptr),_left(nullptr),_right(nullptr){}
};templateclass K, class V
class AVLTree
{
public:typedef AVLTreeNodeK, V Node;
public:AVLTree():_root(nullptr){}private:Node* _root;
};这里解释一下 pair 是个啥 pair 是 C 标准库里面的一个模板类类中维护了两个变量。通过对象可以直接访问维护的两个变量。第一个通过 对象.first 访问第二个通过 对象.second 访问。你姐可以看作是 C 语言的结构体结构体中有两个变量仅此而已 bool insert(const pairK, V kv) AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。 那么 AVL树的插入过程可以分为两步 按照二叉搜索树的方式插入新节点。调整节点的平衡因子。 一个节点的平衡因子可以有两种计算方式
该节点左子树的高度减去右子树的高度。该节点右子树的高度减去左子树的高度。
我们选择使用第一种方式哈用左子树的高度减去右子树的高度来计算一个节点的平衡因子。其实用哪种都无所谓的。
废话不多说直接看插入节点的时候有哪些情况
插入节点之后无需旋转
AVL 树为什么需要旋转因为 AVL 树中的每个节点的平衡因子只能是 01或者 -1。一旦我们插入一个新的节点向上更新平衡因子的过程中发现某个节点的平衡因子不满足这个要求那么这就不是一颗 AVL 树了就必须进行旋转使得整棵树重新满足 AVL 树的性质。
插入一个节点之后一定会涉及到平衡因子的更新那么我们就得弄清楚下面这两个问题 问题一如何更新平衡因子 这个问题比较简单哈根据我们实现的 AVL 树平衡因子的定义左子树的高度减去右子树的高度。那么如果新插入 的节点是父节点的左孩子那么父节点的平衡因子就要加一如果新插入的节点是父节点的右孩子那么父节点的平衡因子就要减一。 问题二什么时候不用继续向上更新平衡因子了呢 当向上更新平衡因子的过程中如果父节点的平衡因子为 0 了就不需要继续更新平衡因子了这是为什么呢这就得弄清楚为什么插入一个节点需要向上更新平衡因子了需要更新平衡因子是因为插入一个新节点之后改变了父节点某颗子树的高度父节点的某一颗子树的高度改变了那么当然就需要更新平衡因子啦因为平衡因子是用左子树的高度减去右子树的高度嘛。相反如果更新平衡因子的过程中发现并没有改变父节点的某颗子树的高度当然就不必继续向上更新平衡因子啦 表现在平衡因子上就是父节点的平衡因子由 -1 或者 1 变成了 0。父节点的平衡因子由 -1 或者 1 变为 0说明插入一个新节点之后父节点的左右子树高度平衡了。但是以父节点为根节点的树整体高度并没有发生变化因此以父节点作为一颗左子树或者右子树向上更新平衡因子已经是无意义的行为了。 在上面的插入例子中我们观察到更新平衡因子的过程中如果 parent 的平衡因子更新之后为 0再向上更新平衡因子已经没有意义了原因最开始已经讲得很清楚啦
插入节点之后进行左单旋
插入的过程要是都像上面那样只需要更新更新平衡因子就好了但是那是不可能的当我们插入新节点向上更新平衡因子的过程中 parent 的平衡因子出现了 -2 或者 2 的情况那么就无法单纯通过更新平衡因子来实现插入了。就需要旋转节点使得整棵树再次满足 AVL 树的性质啦 在上面的例子中插入一个新的节点 17 在向上更新平衡因子的过程中发现 parent 的平衡因子为 -2这不满足 AVL 树的性质需要通过旋转来解决。
我们观察这种情况111517 三个节点呈现一条直线并且是从左上角到右下角的直线这个时候就我们要以 parent 为旋转点进行左单旋。
表现在平衡因子上parent 的平衡因子为 -2cur 的平衡因子为 -1进行左单旋。
左单旋的关键步骤
parent-_right cur-_left;
cur-left parent;在上面的例子中5 链接到 15 显然不是必须的如果旋转之前父节点的 _parent 就是 nullptr则不会有这一步。旋转完成后将 _parent 和 _cur的平衡因子改成 0就完成了新节点的插入。至于为什么可以直接改成 0等用抽象图来讲解AVL树的插入时会说明原因。
void RotateL(Node* parent)
{Node* cur parent-_right;Node* curLeft cur-_left;parent-_right curLeft; //左单旋的核心步骤之一if (curLeft) //如果curLeft不为空才需要向上链接我们讲解AVL树的插入。curLeft 全为空就没有进行链接curLeft-_parent parent;cur-_left parent; //左单旋的核心操作步骤之二//记录parent的父节点方便后续进行判断确定链接的方式Node* ppnode parent-_parent;parent-_parent cur;//处理一下特殊情况, 还可以使用 ppnode 是不是等于 nullptr 来判断if (parent _root) //parent 就是旋转之前的根节点那么就需要更新根节点{_root cur;cur-_parent nullptr;}else //如果不是的话就需要判断parent位于其父节点的左侧还是右侧进行对应的链接即可{if (ppnode-_left parent){ppnode-_left cur; //parent位于ppnode的左侧}else{ppnode-_right cur; //parent 位于ppnode 的右侧}cur-_parent ppnode;}//更新平衡因子cur-_bf parent-_bf 0;
}插入节点之后进行右单旋
右单旋和左单旋相差不大呢右单旋看起来就是一条从右上角到左下角的直线。
表现在平衡因子上parent 的平衡因子为 2cur 的平衡因子为 1进行右单旋。 右单旋的操作与左单旋同样也相差不大呢对称的嘛。
parent-_left cur-_right;
cur-_right parent;同左单旋5 链接到 1 也不是必须的如果旋转之前父节点的 _parent 就是 nullptr就不会有这一步。但是需要更新根节点为 cur并让 cur 的 _parent 指向空。如果父节点的parent不为空就需要判断 parent 是的 parent 的父节点的左孩子还是右孩子对 cur 进行不同方式的链接。右单旋后将 cur 与 parent 的平衡因子变为0。至于为什么后面讲。
void RotateR(Node* parent)
{Node* cur parent-_left;Node* curRight cur-_right;parent-_left curRight; //右单旋的核心操作之一//判断一下 curRight 是不是 nullptr只有不是 nullptr 才需要向上链接 parentif (curRight)curRight-_parent parent;//提前记录一下 parent 的父节点Node* ppnode parent-_parent;cur-_right parent; //右单旋的核心步骤之二parent-_parent cur; //向上链接父节点//判断parent是不是根节点, 判断方式依然是有两种哈一种是判断ppnode是不是等于nullptr// 另一种是判断 parent 是不是等于 _rootif (ppnode nullptr){_root cur;cur-_parent nullptr; //记得将根节点的父节点置为nullptr}else{//如果不是根节点那么就需要你判断 parent 处于 ppnode 的什么位置if (ppnode-_left parent){//位于左侧就链接左侧ppnode-_left cur;}else{//位于右侧当然就链接右侧啦ppnode-_right cur;}cur-_parent ppnode;}//更新平衡因子cur-_bf parent-_bf 0;
}插入节点之后进行左右双旋
其实只要弄清楚一个旋转其他的旋转就很好理解了我么来看看需要进行左右双旋的插入例子 我们看到需要左右双旋的形状就是一个折线从右上到左下再到右下。
表现在平衡因子上parent 的平衡因子为 2cur 的平衡因子为 -1进行左右双旋。
这种情况单旋是解决不了问题的需要分两步操作
以 cur 为旋转点进行左单旋。以 parent 为旋转点进行右单旋。 双旋更新平衡因子的策略会在 AVL 抽象图讲解中说明。
//左右双旋
void RotateLR(Node* parent)
{Node* cur parent-_left;Node* curRight cur-_right;int curRightBf curRight-_bf; //我们先记录一下 curRightBf 的平衡因子因为左单旋会修改平衡因子嘛, 还可以用来判断新插入的节点位于 curRight 的位置RotateL(cur); //以 cur 为旋转点进行左单旋RotateR(parent); //以 parent 为旋转点进行右单旋//更新平衡因子我们需要判断新插入的节点位于他的左侧还是右侧直接利用平衡因子判断哈if (curRightBf 0){parent-_bf 0;cur-_bf 0;curRight-_bf 0;}else if (curRightBf 1) //新插入的节点位于 curRight 的左侧{parent-_bf -1;cur-_bf 0;curRight-_bf 0;}else if (curRightBf -1)//新插入的节点位于 curRight 的右侧{parent-_bf 0;cur-_bf 1;curRight-_bf 0;}}插入节点之后进行右左双旋
左单旋你回了右单旋你也会了左右双旋你也会了接下来的右左双旋我相信你也一定会的这里就不在制作动图演示过程啦
右单旋的形状也是一个折线哈从左上到右下再到左下角的折线。
表现在平衡因子上parent 的平衡因子为 -2cur 的平衡因子为 1进行右左双旋。
//右左双旋
void RotateRL(Node* parent)
{Node* cur parent-_right;Node* curLeft cur-_left;int curLeftBf curLeft-_bf; //我们先记录一下 curLeftBf 的平衡因子因为右单旋会修改平衡因子嘛, 还可以用来判断新插入的节点位于 curLeft 的位置RotateR(cur); //以 cur 为旋转点进行右单旋RotateL(parent); //以 parent 为旋转点进行左单旋//更新平衡因子我们需要判断新插入的节点位于他的左侧还是右侧直接利用平衡因子判断哈if (curLeftBf 0) //curLeftBf为 0 说明 抽象图中的 b 和 c 均是空树经过左右双旋之后这三个节点的平衡因子其实已经被修改成为了 0 但是为了解耦嘛还是需要判断一下{parent-_bf 0;cur-_bf 0;curLeft-_bf 0;}else if (curLeftBf 1) //新插入的节点位于 curLeft 的左侧{parent-_bf 0;cur-_bf -1;curLeft-_bf 0;}else if (curLeftBf -1)//新插入的节点位于 curLeft 的右侧{parent-_bf 1;cur-_bf 0;curLeft-_bf 0;}
}AVL 树插入抽象图讲解
上面我们都是拿具体的例子来理解AVL树的插入你可能会说这能代表一切情况嘛
下面我们会用抽象图讲解 AVL 树的插入让我们一起来看看插入是不是这么个事儿。
我们来看左单旋的抽象图这个图是怎么抽象的呢
节点值为 8 和 6 的两个节点只是一个代表其值可以是满足 AVL 树的任意值。这里的 8 不一定是根节点有可能只是一颗 AVL 树中的一部分。abc 均表示一颗子树。下图中在 c 下方插入一个节点更新平衡因子时在 8 这个节点处检测到了异常的平衡因子截取了这个节点下面的所有节点。
用这个抽象图能将所有左单旋的情况抽象出来 左单旋之后的结果 我们看到左单旋之后parent 的左右子树高度相同cur 的左右子树的高度相同。这就是为什可以在左单旋之后能够直接将 cur 和 parent 的平衡因子更新为 0 的原因。
我们再来看右单旋的抽象图
在 a 子树中插入一个节点向上更新平衡因子的过程中parent 的平衡因子出现异常。 进行右单旋 同样的我们发现进行右单旋之后parent 的左右子树高度相等cur 的左右子树高度相等这就是为什么能够在进行右单旋之后直接将 parent 和 cur 的平衡因子更新为 0 的原因。
我们再来看左右双旋的抽象图
如下图我们可以看到想要发生左右双旋必然是在 b 或者 c 所在的子树插入一个新节点使得 3 的平衡因子变为 -19 的平衡因子变成 2符合左右双旋特征(插入在 a 下方是右单旋插入在 d 下方不用旋转) 我们可以看到左右双旋其实就是将 b 这个子树给给了 3 的右侧c 这个子树给给了 9 的左侧然后 39 分别充当 6 的左右子树。根据新节点插入如位置的不同平衡因子的更新略有不同因此我们需要判断新插入的节点位于 6 这个节点的左侧还是右侧。
如果在左侧 parent-_bf -1。cur-_bf 0。son-_bf 0; 如果在右侧 parent-_bf 0。cur-_bf 1。son-_bf 0。
接下来我们来看右左双旋
我们画出了左单旋的抽象图右单旋的抽象图左右单旋的抽象图那么你肯定能画出右左双旋的抽象图。这里就补在绘图了
检查 AVL 树插入是否正确
我们可以写几个函数来判断我们实现的 AVL 树的插入函数是否正确判断的依据就是 AVL 树自身的性质
对于每一个节点求出其左右子树的高度相减之后与节点存储的平衡因子作比较如果不同则 AVL 树的插入出问题了。左右子树高度之差的绝对值不大于 1。 int Height(Node* root){if (root nullptr)return 0;int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}//检查 AVL 树是否平衡bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root nullptr)return true;int leftHight Height(root-_left);int rightHight Height(root-_right);if (leftHight - rightHight ! root-_bf){cout 平衡因子异常 root-_kv.first 平衡因子 root-_bf endl;return false;}return abs(rightHight - leftHight) 2 IsBalance(root-_left) IsBalance(root-_right);}代码
bool insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);return true;}else{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);//新节点的插入位置parent 的左孩子还是parent的右孩子if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}//链接一下父节点cur-_parent parent;//更新平衡因子while (parent){//根据你的平衡因子ID定义来如果你定义的平衡因子时左子树的高度减去右子树的高度//就跟我写的代码一样如果你的平衡因子的定义是右子树的高度减去左子树的高度//parent 的平衡因子的跟新就跟写的相反就行了//如果cur在parent 的左侧parent 的平衡因子加加if (cur parent-_left){parent-_bf;}else //在右侧parent 的平衡因子减减{parent-_bf--;}//更新一次就要进行一次判断if (parent-_bf 0){break; //如果更新之后 parent 的平衡因子变成了0直接结束循环}else if (parent-_bf 1 || parent-_bf -1) //继续向上跟新平衡因子{cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){//AVL不平衡了需要旋转if (parent-_bf -2 cur-_bf -1){//以 parent 为旋转点进行左单旋RotateL(parent);}else if (parent-_bf 2 cur-_bf 1){//以 parent 为旋转点进行右单旋RotateR(parent);}else if (parent-_bf 2 cur-_bf -1){//先以 cur 为旋转电进行左单旋再以 parent 为旋转点进行右单旋RotateLR(parent);}else if (parent-_bf -2 cur-_bf 1){//先以 cur 为旋转电进行右单旋再以 parent 为旋转点进行左单旋RotateRL(parent);}//旋转之后 AVL 树一定是平衡的因此直接可以退出更新平衡因子的循环啦break;}else{//平衡因子如果出现上述枚举情况之外的情况那么一定是程序除了问题哈。//直接暴力结束程序assert(false);}}}return true;
}bool erase(const pairK, V kv)
AVL 树的删除比插入还复杂一些这里就不做讲解了有兴趣的 uu 可以自己去了解一下。面试的时候顶多考 AVL 树的插入呢~~
