【数据结构】AVL(平衡)二叉树——搜索性能的优化
1. AVL树的概念
在上篇博客:二叉搜索树中我有讲到,二叉搜索树可以缩短查找的效率,但最后发现 如果数据有序或接近有序时构造的二叉搜索树将退化为单支树,这时查找元素相当于在有序表中搜索元素,效率低下。
因此,两位俄罗斯的数学家又发明了一种解决上述问题的方法:AVL树。它最主要的特点是:当二叉树插入新结点后,如果能保证每个结点左右子树的高度差的绝对值不超过1(或许需要对树中节点的位置进行调整),即可降低树的高度,从而减少平均搜索长度。
一棵AVL树,要么是空树,要么是具有以下性质的二叉搜索树:保证严格平衡
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1,0,1)
问题1:下面这棵树是AVL树吗?
上图中,所有节点的平衡因子都在(-1,0,1)中,所以是一棵AVL树
问题2: 如果插入10 这个节点以后呢?
上图中,8,7两个节点更新后的平衡因子变为2 ,所以不再是AVL树。只有旋转调整才可以重新达到AVL平衡的状态。旋转调整的过程,我在下面会详细讲到。
2.AVL 树的功能实现——含代码
AVL 树和二叉树最本质的区别就是 含有平衡因子,保证严格平衡。
其实AVL树的查找,插入,删除都与二叉树相似,在上篇博客:二叉搜索树 中, 我讲过详细的过程,不太明白的小伙伴可以查看,并且在二叉搜索树的模拟实现 这篇博客中有完整的代码可以参考。
所以在下面,我主要讲一下 插入结点后怎样更新平衡因子,和怎样调节使达到平衡。
2.1 AVL 树结点的定义
template <class K, class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K,V>&kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
AVLTreeNode<K, V>* _left; //该节点的左孩子
AVLTreeNode<K, V>* _right; //该节点的右孩子
AVLTreeNode<K, V>* _parent; //该节点的双亲
pair<K, V> _kv; //该节点中的值
int _bf; //该节点的平衡因子
};
2.2 插入结点
- 插入节点的过程和二叉搜索树一样:先确定位置再进行插入
- 更新平衡因子,若绝对值大于1则需要旋转调节平衡因子
更新平衡因子的过程:
按二叉搜索树的规则将新结点插入后,AVL树的平衡可能遭到破坏,所以我们需要更新平衡因子,从而检测是否破坏了AVL 树的平衡性。
在插入前parent的平衡因子有三种情况:-1,0,1,插入时有两种情况:
1) 若新结点cur插入到结点 parent的左侧,只需给parent 的_bf 做-1操作
2)若新结点cur插入到结点 parent的右侧,只需给parent 的_bf 做+1操作
插入后parent 的平衡因子有 三种情况:0,正负1,正负2,此时分情况处理:
1)若parent平衡因子是0,则插入成功,直接返回true
2)若parent平衡因子是正负1,则继续向上更新直至根节点或|_bf|==2时做旋转处理
3)若parent平衡因子是正负2,则违反了平衡树的性质,需要做旋转处理使得重新平衡
while (parent)
{
if (parent->_left == cur)
parent->_bf--;
else
parent->_bf++;
if (parent->_bf == 0) break; //bf==0 插入成功
else if (parent->_bf == 1 || parent->_bf == -1) //|bf|==1 继续更新
{
cur = parent;
parent = cur->_parent;
}
else if //|bf|==2 做旋转调整
{
//旋转
}
旋转调节平衡的过程
AVL树的旋转分为以下四种:右单旋,左单旋,先右单旋再左单旋,先左单旋再右单旋 下面我通过抽象图帮助大家理解这四个旋转的过程
1.新结点插入较高左子树的左侧——左左:右单旋
这里cur和parent的bf 都是负数
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* pp = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pp->_left == parent)
{
pp->_left = subL;
subL->_parent = pp;
}
else
{
pp->_right = subL;
subL->_parent = pp;
}
}
subL->_bf = parent->_bf = 0;
}
2.新结点插入较高右子树的右侧——右右:左单旋
这里cur和parent的bf 都是正数
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pp = parent->_parent;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subR;
subR->_parent = pparent;
}
else
{
pparent->_right = subR;
subR->_parent = pparent;
}
}
parent->_bf = subR->_bf = 0;
}
3.新结点插入较高左子树的右侧——左右:先左单旋再右单旋
这里parent 的bf为负,cur 的bf为正
//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);//先左单旋
RotateR(parent);//再右单旋
if (bf == 0)
{
parent->_bf = subL->_bf = subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else
assert(false);
}
4.新结点插入较高右子树的左侧——右左:先右单旋再左单旋
这里parent 的bf为正,cur 的bf为负
//右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (bf == 0)
parent->_bf = subR->_bf = subRL->_bf = 0;
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else
assert(false);
}
关于AVL树完整的实现代码,可参考下篇博客:AVL树的完整实现:https://blog.****.net/ly_6699/article/details/89816571
3.AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点左右子树的高度差的绝对值不能超过1,这样可以保证查询时的高效性。
但很多人又发现,如果我们对AVL树做一些结构修改的操作,性能十分低下,比如:插入和删除时都要维护它的绝对平衡性,从而需要不断地旋转,直至达到完全平衡的状态,这样的操作太耗费时间和精力。
因此,如果需要一种查询高效且有序的数据结构,而且数据的个数是静态的,可以考虑用AVL树,但如果结构需要经常修改,最好慎用!!
这时,我们就想有没有另外一个更好的选择,既能保证查找效率,又能提高修改效率呢?巧了,就刚好有人提出了红黑树,完美的解决这些问题。
关于红黑树,我在下篇博客:红黑树 中会详细讲到,敬请期待。