文章目录
- AVL树的概念
- AVL树基本框架
- AVL树的插入
- AVL树的插入（无旋转）
- AVL树的插入（旋转操作）
- 单旋
- 双旋
- 旋转代码
上面我们知道二叉搜索树在特殊情况下查找的时间复杂度为
O(N),
所以为了解决二叉搜索树不稳定的问题，我们引入了AVL树，也称为平衡二叉树。二叉搜索树相关知识点
AVL树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右
子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
我们如果发现平衡因子大于等于2的话，我们就会通过旋转操作使整颗树的平衡因子回到-1,0,1
AVL树基本框架
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)
{}
};
AVL树的基本结构
template<class K, class V>
struct AVLTree
{
typedef AVLTreeNode<K, V> Node;
private:
Node* _root;//定义一个根节点
};
AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。AVL树的插入过程可以分为两步：
- 按照二叉搜索树的方式插入新节点
- 调整节点的平衡因子
如何更新平衡因子
新增在右,父亲的bf加一
新增在左,父亲的bf减一
- 更新完成后,父亲的bf==1/-1,说明父亲插入前的bf一定是0,插入后一边高一边低,需要继续向上更新
- 更新完成后,父亲的bf==0,说明父亲在插入前的bf是1/-1,插入后两边高度一致,则不需要继续往上更新了
- 更新完成后,父亲的bf==2/-2,打破了平衡,父亲所在的子树要旋转处理
AVL树的插入（无旋转）
// 一:按照二叉搜索树的方式插入值;
// 二:调整平衡因子后旋转
bool Insert(const pair<K, V> &kv)
{
if (_root == nullptr) // 插入第一个节点
{
_root = new Node(kv);
return true;
}
Node *cur = _root;
Node *parent = nullptr;
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->_right)
parent->_bf++;
else
parent->_bf--;
if (parent->_bf == 0) // 不用更新
break;
else if (parent->_bf == 1 || parent->_bf == -1) // 高度出现变化,往上更新
{
parent = parent->_parent;
cur = cur->_parent;
}
else if (abs(parent->_bf) == 2) // parent所在的子树不平衡了,旋转处理
{
// 后面旋转
}
}
}
AVL树的插入（旋转操作）
单旋
基础旋转
左单旋
右单旋
双旋
先左旋再右旋
先右旋再左旋
旋转代码
void RotateL(Node *parent) // 左旋
{
Node *subR = parent->_right;
Node *subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
Node *parentParent = parent->_parent;
parent->_parent = subR;
if (subRL)
subRL->_parent = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
parent->_bf = subR->_bf = 0;
}
void RotateR(Node *parent) // 右旋
{
Node *subL = parent->_left;
Node *subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node *parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
subL->_bf = parent->_bf = 0;
}
void RotateRL(Node *parent) // 先右再左
{
Node *subR = parent->_right;
Node *subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
// subRL自己就是新增
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (bf == -1)
{
// subRL的左子树新增
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1)
{
// subRL的右子树新增
parent->_bf = -1;
subRL->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false);
}
}
void RotateLR(Node *parent) // 先做再右 复用
{
RotateL(parent->_left);
RotateR(parent);
}
