🐱作者:一只大喵咪1201
🐱专栏:《数据结构与算法》
🔥格言:你只管努力,剩下的交给时间!
AVL树
- 🌲AVL树
- 🌴AVL树的插入
- 🌴AVL树的旋转
- 左单旋
- 右单旋
- 左右双旋
- 右左双旋
- 🌴AVL树的验证
- 🌴AVL数的删除(了解)
- 🌴AVL数的性能
- 🌴总结
我们知道,二叉搜索树的搜索效率非常高,平均时间复杂度是O(log2N),但是当数据原本就有序时,插入二叉树中就会形成单支结构,此时搜索的时间复杂度就是O(N)。
为了避免二叉搜索树的这个缺陷,在它的基础上提出了AVL树(高度平衡二叉搜索树)和红黑树。
🌲AVL树
- AVL树:当向二叉搜索树中插入新节点后,要保证每个节点的左右子树高度差的绝对值不超过1。
根据高度差不超过1的规制,可以避免二叉搜索树出现单支的情况,使其更加接近完全二叉树,保证搜索效率是O(log2N)。
AVL树的性质:
- 它的左右子树都是AVL树。
- 左右子树的高度差(简称平衡因子)的绝对值不超过1。
注意: 一颗空树或者只有一个根的树也属于AVL树。
- 平衡因子 = 右子树高度 - 左子树高度
- a和b两种情况下根节点的平衡因子都是是0,因为此时左右子树高度相同。
- c情况下根节点的平衡因子是-1,因为此时左子树比右子树多一个节点。
- d情况下根节点的平衡因子是1,因为此时左子树比右子树少一个节点。
在AVL树中,每个节点的平衡因子只能是1,0,-1三种情况,一旦不是这三种就需要进行调整,保证平衡因子不会出现第四种情况。
插入新节点10以后,导致多个节点的平衡因子发生了变化:
- 节点9的平衡因子从0变成了1,说明新节点插入到了节点9的右边。
- 节点8的平衡因子从1变成了2,因为新节点插入到了节点8的右子树中。
- 节点8的平衡因子不再是1,0,-1三个数中的一个,所以就需要进行调整。
至于怎么调整一会儿本喵再详细讲解。
🌴AVL树的插入
破坏二叉搜索树平衡的操作主要就是插入,所以我们主要来看看AVL树是如何插入的,是如何在插入过程中保证平衡的。
节点的定义:
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;//键值对
AVLTreeNode* _left;//左子树
AVLTreeNode* _right;//右子树
AVLTreeNode* _parent;//父节点
int _bf;//平衡因子balance factor
//节点的构造函数
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
};
- 节点中的值是一个键值对。
- 是一个三叉链的结构,不仅有左右子节点的指针,还有父节点的指针。
- 平衡因子用来衡量该节点的状态,默认情况下是0。
AVL树的定义:
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode Node;
public:
bool insert(const pair<K, V>& kv)
{
//............
}
protected:
Node* _root = nullptr;//缺省值
};
和二叉搜索树一样,AVL树种也是只有一个成员变量根,给根一个缺省值,默认情况下它是空树。
插入:
AVL树的插入和二叉搜索树的插入在前半部分一模一样,大于根的插入到右边,小于根的插入到左边,区别在于AVL树插入后的调整。
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool insert(const pair<K, V>& kv)
{
//空树时直接插入
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
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);
//判断当前节点是父节点的左子节点还是右子节点
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//更新平衡因子,进行调整
break;
}
}
上面代码是将节点插入到二叉搜索树中的代码,不再解释,最重要的是后面的更新平衡因子,这才是AVL树的重点。
🌴AVL树的旋转
平衡因子不是-1/0/1的节点进行调整,调整的方式是旋转,下面本喵来详细介绍一下如何旋转。
每一个子树都是一个AVL树,所以子树的平衡因子发生变化,势必会对其父节点以及祖父节点等祖宗节点有影响,可能会引发一系列的调整。
当子树更新完毕后,是否继续向上更新平衡因子的依据是子树的高度是否发生变化:
- parent->_bf == 0,说明之前是-1或者1,说明插入之前,该节点的左右子树一边高一边低,此次插入填平了,但是高度没有发生变化,所以不用继续向上更新。
- parent->_bf == 1 或者 parent->_bf == -1,说明之前是,两边一样高,此次插入导致一边高于另外一边,高度发生了变化,所以需要继续向上更新。
- parent->_bf == 2 或者 parent->_bf == -1,说明之前是1或者-1,本来就左右不平衡,此次插入导致更加不平衡,违反了规则,需要进行旋转处理。
更新平衡因子的代码:
//更新平衡因子,进行调整
while (parent)//最差更新到根
{
//左边新插入,平衡因子减一
if (cur == parent->_left)
{
parent->_bf--;
}
//右边新插入,平衡因子加一
else
{
parent->_bf++;
}
//跟新后的平衡因子是0,说明高度没有变化,不用继续更新
if (parent->_bf == 0)
{
break;
}
//新插入节点,高度发生了变化,向上更新
else if(parent->_bf==1 || parent->_bf == -1)
{
//向上更新父节点
cur = parent;
parent = parent->_parent;
}
//高度差超出1,进行旋转
else if(parent->_bf == 2 || parent->_bf == -2)
{
//旋转
//更新旋转后的平衡因子
}
//前面出错,正常情况下不会进入这里
else
{
//出错直接退出
assert(false);
}
旋转的作用:
- 让这颗子树左右高度差不超过1。
- 旋转过程中继续保持它是搜索树。
- 更新旋转节点和其孩子节点的平衡因子。
- 让这颗子树的高度跟插入之前保持一直。
左单旋
- 插入新节点以后,右子树的高度发生了变化,最终变成了2,需要进行旋转。
旋转过程:
- 30变成60的左子节点,60变成根节点。
- 30和60的平衡因子都变成了0。
在上图的基础上,左右子树同时增加一层节点,如下图:
- 插入新节点后,右子树高度发生了变化,最后变成了2,需要进行旋转。
旋转过程:
- 40变成30的右子节点
- 30变成60的左子节点
- 60变成根节点
- 30和60的平衡因子变成0。
在上图基础上再增加一层节点,如下图:
此时30的左子树有两层,右子树有3层。
- 左子树的两层有三种情况,如黑色箭头指向的,这里使用红色框代表两层子树。
- 右子树中要想让新增节点引起旋转,新增的两层节点必须如上图所示。
- 新插入的节点可以插入的位置有两个,如上图实线圈和虚线圈所示。
旋转过程:
- 60的左子树变成30的右子树。
- 30变成60的左子树。
- 60变成根。
- 30和60的平衡因子变成0。
从新增两层开始就有多种情况了,当层数越多,情况就越多,所以使用抽象图来代表有多层子树的情况:
a,b,c都是高度为h的AVL子树。
- 在子树c处插入新节点,此时c子树高度变成了h+1,更新平衡因子,最终导致30的平衡因子变成了2,需要进行旋转。
旋转过程:
- 60的左子树变成30的右子树。
- 30变成60的左子树。
- 60变成根。
- 30和60的平衡因子变成0。
通过上面具象图和抽象图插入节点后的旋转,我们可以总结出一些规律:
- 插入新的节点后,平衡因子发生了变化的3个节点在同一条直线上,平衡因子为2的节点在最上边,其余两个依次排在右下方。
//用左单旋的代码条件
parent->_bf == 2 && cur->_bf == 1;
旋转过程:
- subRL成为parent的右子树。
- parent成为subR的左子树。
- subR成为根。
- parent个subR的平衡因子变成0。
上面所述的旋转就左旋。形象的理解就是将左边高的一端按下去。
将左单旋的具体实现封装在一个函数中,在更新平衡因子的过程中调用左单旋来调整结构。
右单旋
右单旋的结构只是和左单旋的结构方向不一样,其他都一样,本喵就不再画具象图推演了,直接上抽象图:
a,b,c都是高度为h的AVL子树。
- 在子树a处插入新节点,此时a子树高度变成了h+1,更新平衡因子,最终导致60的平衡因子变成了-2,需要进行旋转。
旋转过程:
- 30的右子树成员60的左子树。
- 60成为30的右子树。
- 30成为根。
- 60和30的平衡因子变成0。
右单旋的规律:
- 插入新的节点后,平衡因子发生了变化的3个节点在同一条直线上,平衡因子为-2的节点在最上边,其余两个依次排在左下方。
//用右单旋的代码条件
parent->_bf == -2 && cur->_bf == -1;
旋转过程:
- subLR成为parent的左子树。
- parent成为subL的右子树。
- subL成为根。
- parent和subL的平衡因子成为0。
形象的理解就是右边高,将右边按下去。
右单旋实现代码:
//右旋实现
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
//不为空才会链接
subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
//旋转后与旧树的链接
if (ppNode == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
//新根是子树
else
{
//在左子树插入的
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
//在右子树插入的
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
//更新平衡因子
parent->_bf = subL->_bf = 0;
}
只是逻辑和左单旋相反,其他一样,不再进行详细讲解。
左右双旋
- 插入新节点后,左子树的高度发生变化,根节点90的平衡因子最终变成-2。
旋转过程:
- 左子树先进行左单旋:
- 30变成40的左子树。
- 40变成根节点。
- 再整体进行右单旋:
- 90变成40的右子树。
- 40变成根节点。
- 90和40的平衡因子变成0。
在上图基础上各个子树再增加一层节点:
插入的节点为红色圈,可插入的位置有两个。
- 插入新的节点后,左子树的高度发生了变化,根节点90的平衡因子变成了-2。
旋转过程:
- 先进行左单旋:
- 50的左子树变成30的右子树(图中左子树为空,所以不用管)。
- 30变成50的左子树。
- 50变成子树的根。
- 再进行右单旋:
- 50的右子树变成90的左子树。
- 90变成50的右子树。
- 50变成根。
- 90的平衡因子变成0,30的平衡因子变成-1,50的平衡因子变成0。
在上图基础上再增加一层节点:
相对于最开始来说一共增加了两层,红色框表示两层,这两层右三种情况,如黑色简单所指。
- 插入新节点后,左子树高度发生了变化,根节点90的平衡因子变成-2。
旋转过程:
- 先进行左单旋:
- 50的左子树变成30的右子树。
- 30变成50的左子树。
- 50变成子树的根。
- 再进行右单旋:
- 50的右子树变成90的左子树。
- 90变成50的右子树。
- 50成为根。
- 30的平衡因子变成-1,90和50的平衡因子变成0。
将上面具象图画成抽象图:
h表示子树的高度,紫色框表示插入的节点。
- 插入新节点后,左子树的高度发生变化,根节点90的平衡因子变成-2。
//用左右双旋的代码条件
parent->_bf == -2 && cur->_bf == 1;
旋转过程:
- 先进行左单旋:
- 60的左子树变成30的右子树。
- 30变成60的左子树。
- 60成为子树的根。
- 再进行右单旋:
- 60的右子树成为90的左子树。
- 90成为60的右子树。
- 60成为根。
- 60的平衡因子变成0,90的平衡因子变成1,30的平衡因子变成0。
左右双旋规律:
- 插入新的节点后,平衡因子发生了变化的3个节点形成一个左边突出的拐,平衡因子为-2的节点在最上边,左下方是平衡因子为1的节点,最后一个在1节点的右下方,该节点的平衡因子可能是-1也可能是1。
平衡因子更新:
双旋中,旋转很好实现,直接复用前面的左单旋和右单旋就可以,难点在于双旋过后平衡因子的更新。从上面具象图和抽象图中看不出一点平衡因子的变化规律。
换个角度来看:
- 子树b在旋转前是60的左子树,旋转后成为了30的右子树。
- 子树c在旋转前是60的右子树,旋转后成为了90的左子树。
- 节点60在旋转前是子树根,旋转后成了新的根。
一步到位的来看,旋转就是将节点60的左右子树分摊给了30个90,而它自己做了新的根。
- 新插入的节点如果在子树b,那么旋转后30的右子树高度就会加一,导致30的平衡因子是0,90的平衡因子是1。
- 新插入的节点如果在子树c,那么旋转后90的左子树高度就会加一,导致90的平衡因子是0,30的平衡因子是-1。
- 新的根节点60的平衡因子是0。
自己是新增:
- 插入新节点后,60的平衡因子是0,说明它自己就是新增节点。
- 此时旋转过后,平衡因子变化了的3个节点的平衡因子都变成了0。
左右双旋代码实现:
重点在于平衡因子的更新,左单旋和右单旋直接复用前面的代码即可。
右左双旋
右左双旋和左右双旋逻辑相反,同样也不再画具象图了,直接看抽象图:
- 插入新节点后,右子树的高度发生了变化,最终根节点30的平衡因子变成了2。
//右左双旋的代码条件
parent->_bf == 2 && cur->_bf == -1;
旋转过程:
- 先进行右单旋:
- 60的右子树变成90的左子树。
- 90变成60的右子树。
- 60成为子树根。
- 再进行左单旋:
- 60的左子树变成30的右子树。
- 30变成60的左子树。
- 60成为根。
- 90的平衡因子变成0,30的平衡因子变成-1,60的平衡因子变成0。
右左双旋规律:
- 插入新节点后,变化了平衡因子的3个节点,组成一个右边退出的拐,平衡因子为2的节点在最上边,为-1的节点在其右下方,剩下一个在其左下方。
平衡因子更新:
同样忽略旋转过程,直接对比最开始和旋转后的结构:
更新方法和左右双旋的方式一样,就不再对图详细解释了,直接看代码:
//右左双旋实现
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;//在单旋转之前拿到平衡因子
RotateR(subR);//先进行右单旋
RotateL(parent);//在进行左单旋
//更新平衡因子
//插入subRL的左边
if (bf == -1)
{
//右单旋后,该分支成为parent的右子树
//parent的平衡因子为0
parent->_bf = 0;
//左单旋后,另一个分支成为subR的左子树
//subR的平衡因子是1
subR->_bf = 1;
}
//插入subRL的右边
else if (bf == 1)
{
//右单旋后,另一分支成为parent的右子树
//parent的平衡因子为-1
parent->_bf = -1;
//左单旋后,该分支成为subR的左子树
//subR的平衡因子为0
subR->_bf = 0;
}
//subRL就是新插入的节点
else if (bf == 0)
{
//parent和subR的平衡因子都是0
parent->_bf = 0;
subR->_bf = 0;
}
//出错
else
{
//正常情况下不会进入这里
assert(false);
}
//新根的平衡因子为0
subRL->_bf = 0;
}
只是逻辑和左右双旋相反,就不再详细讲解了。
注意:
- 旋转过后,平衡因子的更新最好是在封装的旋转函数中更新,如果在外面更新会因为指向关系混乱而出错。
- 双旋时,在左右单旋之前拿到平衡因子,否则会因为旋转改变平衡因子导致判断出问题。
🌴AVL树的验证
上面已经实现了AVL树的插入,包括旋转的插入,此时我们通过插入就能成功建立一颗AVL树。
写几个测试用例看看创建是否能够成功,插入的数值是键值对,如上图所示,并且按照升序打印出来。
- 但是这只能证明二叉搜索树创建成功了,到底是不是AVL树是无法证明。
为了证明这是AVL树需要专门写一个函数来检查一下。
如上图所示,是专门用来检测是否是AVL树的。
- 通过检测,上面的三个测试用例都是AVL树。
这样拿三个例子可能不具有代表性,下面我门用随机数来检测:
- 插入十万个随机数,经过多次检测运行,发现都是AVL数,此时说明我们的AVL数成功实现了。
🌴AVL数的删除(了解)
AVL树也是二叉搜索树,可按照二叉搜索树的方式将节点删除,然后再更新平衡因子,只不过与删除不同的是,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。
情况比较复杂,有兴趣的小伙伴可以自行了解,推荐《数据结构-用面向对象方法与C++描述》殷人昆版。
🌴AVL数的性能
AVL数是二叉搜索树,而且左右子树的高度差不会超过1,所以它非常接近完全二叉树,可以保证搜索的时间复杂度在O(log2N),而不会出现单只的情况。
但是还是存在一定的效率损失问题:
- 插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,
有可能一直要让旋转持续到根的位置。
虽然旋转保证了搜索的时间复杂度在O(log2N),但是又增加了旋转的时间复杂度,主要是体现在插入数据时。
也就是说,AVL树的结构在修改时会导致效率低下。
🌴总结
AVL树是在二叉搜索树的基础上增加左右子树高度不超过1的限制,但是在修改结构的时候又因为旋转导致了效率降低,后面的红黑树就克服了这个问题,下篇文章见。