[C++][数据结构][AVL树]详细讲解
目录
- 1.AVL树的概念
- 2.AVL树节点的定义
- 3. AVL树的插入
- 4.AVL树的旋转
- 1.新节点插入较高左子树的左侧 — 左左:右单旋
- 2.新节点插入较高右子树的右侧 — 右右:左单旋
- 3.新节点插入较高左子树的右侧 — 左右:先左单旋再右单旋
- 4.新节点插入较高右子树的左侧 — 右左:先右单旋再左单旋
- 5.AVL树的验证
- 6.AVL树的删除(了解)
- 7.AVL树的性能
1.AVL树的概念
二叉搜索树中,如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下,如何解决?
- 当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度
AVL树具有以下性质:
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
- 规定:平衡因子 = 右子树的高度 – 左子树的高度
- 规定:平衡因子 = 右子树的高度 – 左子树的高度
如果一棵二叉搜索树是高度平衡的,它就是AVL树
- 如果它有n个结点,其高度可保持在O(logN),搜索时间复杂度O(logN)
2.AVL树节点的定义
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv;
int _bf; // balance factor
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};
3. AVL树的插入
- AVL树就是在二叉搜索树的基础上引入了平衡因子,那么AVL树的插入过程可以分为两步:
- 按照二叉搜索树的方式插入新节点
- 调整节点的平衡因子
- 更新平衡因子的规则
- 新增在右,parent->_bf++; 新增在左,parent->_bf–;
- 更新后,parent->_bf == 1/-1
- 说明parent插入前的平衡因子是0,左右子树高度相等
- 插入后有一边高,parent高度变了,需要继续往上更新
- 更新后,parent->_bf == 0
- 说明parent插入前的平衡因子是1/-1,说明左右子树一边高一边低
- 插入后两边一样高,插入填上了矮的那边,parent所在子树高度不变,不需要继续网上更新
- 更新后,parent->_bf == 2/-2
- 说明parent插入前的平衡因子是1/-1,已经达到平衡临界值
- 插入变成2/-2,打破平衡,parent所在的子树需要旋转处理
- 更新后,abs(parent->_bf) > 2,不可能
- 如果存在,则说明插入前就不是AVL树,需要去检查之前操作的问题
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;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
// 控制平衡
// 1.更新平衡因子
while (parent)
{
if (cur == parent->_left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
if (parent->_bf == 0)
{
break;
}
else if (abs(parent->_bf) == 1)
{
parent = parent->_parent; // 继续向上更新
cur = cur->_parent;
}
else if(abs(parent->_bf) == 2)
{
// parent所在子树已经失衡,旋转调整
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 if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
else
{
assert(false); // 理论不会走到这
}
break;
}
else
{
assert(false); // 理论不会走到这
}
}
return true;
}
4.AVL树的旋转
- 如果在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构, 使之平衡化
- 根据节点插入位置的不同,AVL树的旋转分为四种
1.新节点插入较高左子树的左侧 – 左左:右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* grandParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (grandParent->_left == parent)
{
grandParent->_left = subL;
}
else
{
grandParent->_right = subL;
}
subL->_parent = grandParent;
}
subL->_bf = parent->_bf = 0;
}
2.新节点插入较高右子树的右侧 – 右右:左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) // 防止subRL本来就为空,对空指针访问
{
subRL->_parent = parent;
}
// 用于判断原来的parent是否是子树
Node* grandParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (grandParent->_left == parent)
{
grandParent->_left = subR;
}
else
{
grandParent->_right = subR;
}
subR->_parent = grandParent;
}
subR->_bf = parent->_bf = 0;
}
3.新节点插入较高左子树的右侧 – 左右:先左单旋再右单旋
- 将双旋变成单旋后再旋转
- 即:先对30进行左单旋,然后再对90进行右单旋,旋转完成后再考虑平衡因子的更新
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
subLR->_bf = 0;
if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
}
else if (bf == 0) // 原来的树/子树只有这三个节点
{
parent->_bf = 0;
subL->_bf = 0;
}
else
{
assert(false); // 理论不会走到这
}
}
4.新节点插入较高右子树的左侧 – 右左:先右单旋再左单旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
subRL->_bf = 0;
if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
}
else if (bf == 0)
{
parent->_bf = subR->_bf = 0;
}
else
{
assert(false); // 理论不会走到这
}
}
5.AVL树的验证
- AVL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分两步:
- 验证其为二叉搜索树
- 如果中序遍历可得到一个有序的序列,就说明为二叉搜索树
- 验证其为平衡树
- 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
- 节点的平衡因子是否计算正确
- 验证其为二叉搜索树
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBalance()
{
return _IsBalance(_root);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
int diff = rightHeight - leftHeight;
if (diff != root->_bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return abs(diff) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
int Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
return max(Height(root->_left), Height(root->_right)) + 1; //统计高度为后序
}
6.AVL树的删除(了解)
- 因为AVL树也是二叉搜索树,可按照二叉搜索树的方式将节点删除,然后再更新平衡因子
- 只不过与删除不同的是,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置
7.AVL树的性能
- AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度,即logN
- 但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:
- 插入时要维护其绝对平衡,旋转的次数比较多
- 更差的是在删除时, 有可能一直要让旋转持续到根的位置
- 因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合