樊梓慕:个人主页
个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》
每一个不曾起舞的日子,都是对生命的辜负
目录
前言
1.概念
2.定义
3.插入
4.旋转
4.1右单旋
原理图与实现细节
代码实现
4.2左单旋
原理图与实现细节
代码实现
4.3先左旋再右旋
原理图与实现细节
代码实现
4.4先右旋再左旋
原理图与实现细节
代码实现
4.5插入的完整代码
5.验证
5.1验证二叉搜索特性
5.2验证平衡特性
前言
本篇文章主要与大家一起学习AVL树-平衡二叉搜索树。
我们前面学习二叉搜索树时,了解到如果插入的元素有序或者接近有序,二叉搜索树的结构就会退化成单支树甚至是链表,那么此时搜索的时间复杂度会退化,如果一个二叉搜索树可以一直保持平衡的话,那么他的时间复杂度是logN,即高度次,所以AVL树-平衡二叉搜索树的出现就是为了解决二叉搜索树不平衡的问题,从而保证搜索效率。
声明:本篇文章的图片样式取自 《Hello 算法》-github.com ,后博主根据文章内容对图片作了修改,大家感兴趣也可以了解一下这本书。
欢迎大家收藏以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。
=========================================================================
GITEE相关代码:樊飞 (fanfei_c) - Gitee.com
=========================================================================
1.概念
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查 找元素相当于在顺序表中搜索元素,效率低下。
因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
即AVL树满足以下条件:
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
比如:
2.定义
AVL树节点的定义:
template
struct AVLTreeNode
{
AVLTreeNode
AVLTreeNode
AVLTreeNode
int _bf; // 该节点的平衡因子
pair
AVLTreeNode(const pair
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
, _kv(kv)
{}
};
3.插入
那么如何用算法实现AVL树呢?
其实AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。
那么AVL树的插入过程可以分为两步:
按照二叉搜索树的方式插入新节点调整节点的平衡因子
即第一步我们就把二叉搜索树的插入代码copy一份过来,进行一定的修改:
template
class AVLTree
{
typedef AVLTreeNode
public:
bool Insert(const pair
{
/********* 普通二叉搜索树的插入 *********/
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;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
/**************************************/
return true;
}
private:
Node* _root = nullptr;
};
然后第二步就是调整平衡因子,让左右子树高度之差(平衡因子)不超过1.
当cur插入后,cur的父亲节点parent的平衡因子一定需要调整,再插入之前,parent的平衡因子分为三种情况:-1、0、1(插入之前一定满足AVL树规则),我们默认平衡因子=右子树高度-左子树高度,那么就分为以下两种情况:
如果cur插入到parent的左侧,只需给parent的平衡因子-1即可如果cur插入到parent的右侧,只需给parent的平衡因子+1即可
如果parent的平衡因子发生了变化,那么就证明祖先有可能会受影响,就要向上继续更新。
这里我们同样需要分情况讨论:
此时parent的平衡因子可能有三种情况:0,正负1, 正负2。
如果parent的平衡因子为0,说明插入之前parent的平衡因子为正负1,插入后被调整成0,此时满足AVL树的性质,插入成功,且高度没有发生变化。如果parent的平衡因子为正负1,说明插入前parent的平衡因子一定为0,插入后被更新成正负1,此时以parent为根的树的高度增加,需要继续向上更新。如果parent的平衡因子为正负2,则parent的平衡因子违反平衡树的性质,需要对其进行『 旋转』处理。
我们把上述逻辑转化成代码:
template
class AVLTree
{
typedef AVLTreeNode
public:
bool Insert(const pair
{
/********* 普通二叉搜索树的插入 *********/
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;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
/**************************************/
/************* 调整平衡因子 ************/
while (parent)
{
// 更新双亲的平衡因子
if(cur == parent->left)
parent->_bf--;
else
parent->_bf++;
// 更新后检测双亲的平衡因子
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
// 旋转处理
}
else
{
// 插入之前AVL树就有问题
assert(false);
}
}
return true;
}
private:
Node* _root = nullptr;
};
4.旋转
当节点的平衡因子为正负2时,则需要我们对该子树进行旋转处理。
那旋转最重要的是不能破坏我们二叉搜索树的特性,即旋转过后依旧满足左子树小于根,根小于右子树,那么怎么样进行旋转既能让二叉搜索树保持平衡,又能保持二叉搜索树的特性呢?
4.1右单旋
当新节点插入到较高左子树的左侧时(左左),我们需要进行『 右单旋』操作。
原理图与实现细节
一般有以下这两种情况以及对应的旋转操作:
(1)失衡节点的左孩子没有右孩子(subL无右孩子)
当subL无右孩子时,parent直接旋转到subL的右分支即可,我们不需要考虑subL的右孩子放到哪。
(2)失衡节点的左孩子有右孩子(subL有右孩子subLR)
当subL有右孩子时,parent如果旋转到subL的右孩子处,需要将subL的右孩子subLR放到旋转过来的parent节点的左分支上即可。
体现到代码中如何判断什么时候进行右旋呢?
观察图像得知,当parent平衡因子为-2 && cur平衡因子为-1时,进行右旋。
观察发现,这样旋转后依然满足二叉搜索树的特性,且旋转后该树平衡了。
那么接下来我们要进行代码实现:
这里有几个需要注意的细节:
细节1:subL是否有右孩子subLR,如果有我们需要更新subLR的双亲节点。细节2:parent是否是根节点,如果是根节点,我们需要更新根节点的值为subL;如果不是根节点,可能是某个节点的左子树,也可能是某个节点的右子树,我们需要更新subL的双亲节点为旋转之前parent双亲节点的左分支或右分支,所以我们需要提前保存parent的双亲结点ppnode。细节3:旋转结束后更新parent与subL的平衡因子为0;
代码实现
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
// 细节1
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = subL;
// 细节2
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
// 细节3
subL->_bf = 0;
parent->_bf = 0;
}
4.2左单旋
当新节点插入到较高右子树的右侧时(右右),我们需要进行『 左单旋』操作。
原理图与实现细节
一般有以下这两种情况以及对应的旋转操作:
(1)失衡节点的右孩子没有左孩子(subR无左孩子)
当subR无左孩子时,parent直接旋转到subR的左分支即可,我们不需要考虑subR的左孩子放到哪。
(2)失衡节点的右孩子有左孩子(subR有左孩子subRL)
当subR有左孩子时,parent如果旋转到subR的左孩子处,需要将subR的左孩子subRL放到旋转过来的parent节点的右分支上即可。
体现到代码中如何判断什么时候进行左旋呢?
观察图像得知,当parent平衡因子为2 && cur平衡因子为1时,进行左旋。
观察发现,这样旋转后依然满足二叉搜索树的特性,且旋转后该树平衡了。
那么接下来我们要进行代码实现:
这里有几个需要注意的细节:
细节1:subR是否有左孩子subRL,如果有我们需要更新subRL的双亲节点。细节2:parent是否是根节点,如果是根节点,我们需要更新根节点的值为subR;如果不是根节点,可能是某个节点的左子树,也可能是某个节点的右子树,我们需要更新subR的双亲节点为旋转之前parent双亲节点的左分支或右分支,所以我们需要提前保存parent的双亲结点ppnode。细节3:旋转结束后更新parent与subR的平衡因子为0;
代码实现
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
// 细节1
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = subR;
// 细节2
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
// 细节3
parent->_bf = 0;
subR->_bf = 0;
}
4.3先左旋再右旋
当新节点插入到较高左子树的右侧时(左右),仅使用左旋或右旋都无法使子树恢复平衡,所以我们需要进行『 先左旋再右旋』操作。
原理图与实现细节
体现到代码中如何判断什么时候进行先左旋再右旋呢?
观察图像得知,当parent平衡因子为-2 && cur平衡因子为1时,进行先左旋再右旋。
观察发现,这样旋转后依然满足二叉搜索树的特性,且旋转后该树平衡了。
如果是下面这种树,你会发现会有两种不同的情况,即新插入的节点是subLR的左树还是右树,这个问题决定了最后parent和subL的平衡因子。
如果是右树,如图『 节点4』,最后旋转结束,parent的平衡因子为0,subL的平衡因子为-1;如果是左树,如图『 节点2』,最后旋转结束,parent的平衡因子为1,subL的平衡因子为0;
所以根据上面的分析,我们需要知道新插入的节点是subLR的左树还是右树.
这个通过subLR的平衡因子就能判定:
如果为1,证明插入的节点是subLR的右树,即『 节点4』,所以最终subL的平衡因子为-1,parent的平衡因子为0;如果为-1,证明插入的节点是subLR的左树,即『 节点2』,所以最终parent的平衡因子为1,subL的平衡因子为0;如果为0,则为上上面图片的情况,最终parent和subL的平衡因子都为0。
代码实现
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
4.4先右旋再左旋
当新节点插入到较高右子树的左侧时(右左),仅使用左旋或右旋都无法使子树恢复平衡,所以我们需要进行『 先右旋再左旋』操作。
原理图与实现细节
体现到代码中如何判断什么时候进行先右旋再左旋呢?
观察图像得知,当parent平衡因子为2 && cur平衡因子为-1时,进行先右旋再左旋。
观察发现,这样旋转后依然满足二叉搜索树的特性,且旋转后该树平衡了。
如果是下面这种树,你会发现会有两种不同的情况,即新插入的节点是subRL的左树还是右树,这个问题决定了最后parent和subR的平衡因子。
如果是左树,如图『 节点2』,最后旋转结束,parent的平衡因子为0,subR的平衡因子为1;如果是右树,如图『 节点4』,最后旋转结束,parent的平衡因子为-1,subR的平衡因子为0;
所以根据上面的分析,我们需要知道新插入的节点是subRL的左树还是右树.
这个通过subRL的平衡因子就能判定:
如果为-1,证明插入的节点是subRL的左树,即『 节点2』,所以最终subR的平衡因子为1,parent的平衡因子为0;如果为1,证明插入的节点是subRL的右树,即『 节点4』,所以最终parent的平衡因子为-1,subR的平衡因子为0;如果为0,则为上上面图片的情况,最终parent和subR的平衡因子都为0。
代码实现
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == -1)
{
subRL->_bf = 0;
subR->_bf = 1;
parent->_bf = 0;
}
else if (bf == 1)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == 0)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
4.5插入的完整代码
bool Insert(const pair
{
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;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
while (parent)
{
if (cur == parent->left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
// 旋转处理
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else
{
RotateRL(parent);
}
break;
}
else
{
// 插入之前AVL树就有问题
assert(false);
}
}
return true;
}
5.验证
5.1验证二叉搜索特性
如何验证一个平衡二叉搜索树是否健康呢?
那是否符合二叉搜索很简单,我们只需要中序遍历一遍看看是不是有序的即可。
中序遍历:
//中序遍历
void Inorder()
{
_Inorder(_root);
}
//中序遍历子函数
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << " ";
_Inorder(root->_right);
}
创建子函数实现中序遍历的原因是:外部调用Inorder无法访问到private的根节点。
5.2验证平衡特性
验证平衡特性,我们可以获取左右子树的高度,然后利用这个高度计算差值,看看是否平衡即可。
首先是获取左右子树的高度:
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
//返回左右子树高的那一个+1作为当前树的高度
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
int Height()
{
return _Height(_root);
}
判断是否平衡:
bool _IsBalance(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
if (abs(rightHeight - leftHeight) >= 2)
{
cout << root->_kv.first << "不平衡" << endl;
return false;
}
if (rightHeight - leftHeight != root->_bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
观察上述验证平衡特性的代码,其实有很多重复计算,比如每次判断都需要重新计算该节点所有字数的高度,有没有什么办法保存这些高度呢?
其实我们可以采用后序遍历的思想,从最底下开始验证,这样就可以首先获取底层的高度,新增一个高度的参数,验证成功后利用引用将高度返回给上一层(输出型参数)。
bool _IsBalance(Node* root, int& height)
{
if (root == nullptr)
{
height = 0;
return true;
}
int leftHeight = 0, rightHeight = 0;
//后序的思想
//有一棵子树不平衡就返回false
if (!_IsBalance(root->_left, leftHeight)
|| !_IsBalance(root->_right, rightHeight))
{
return false;
}
if (abs(rightHeight - leftHeight) >= 2)
{
cout << root->_kv.first << "不平衡" << endl;
return false;
}
if (rightHeight - leftHeight != root->_bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
return true;
}
bool IsBalance()
{
int height = 0;
return _IsBalance(_root, height);
}
=========================================================================
如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容
博主很需要大家的支持,你的支持是我创作的不竭动力
~ 点赞收藏+关注 ~
=========================================================================
相关链接
发表评论