目录
目录
一、AVL树的基本概念
1.1 基本概念
二、AVL树的模拟实现
2.1 AVL树节点的定义
2.2 插入操作
2.3 旋转操作
2.4 具体实现
一、AVL树的基本概念
1.1 基本概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log n)，搜索时间复杂度O(log n)。那么接下来就让我们来模拟实现一下吧。
二、AVL树的模拟实现
2.1 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;
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
,_bf(0)
{}
};这里采用了我们的KV模型进行定义。
2.2 插入操作
AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：
- 按照二叉搜索树的方式插入新节点
- 调整节点的平衡因子
插入很简单，就和我们的搜索二叉树的插入没什么两样，但是由于我们引入了平衡因子，一棵树的平衡可能被破坏，所以我们可能需要对树的结构进行调整。调整的方法等会再说，这里先说如何判断一颗树的平衡被破坏了。
pCur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
1. 如果pCur插入到pParent的左侧，只需给pParent的平衡因子-1即可
2. 如果pCur插入到pParent的右侧，只需给pParent的平衡因子+1即可
此时：pParent的平衡因子可能有三种情况：0，正负1， 正负2
1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功
2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更新成正负1，此时以pParent为根的树的高度增加，需要继续向上更新
3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转处理
这里用图的形式来给大家描述一下大概的过程：
再看一种情况，只需向上更新一次的情况：
2.3 旋转操作
如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：
- 新节点插入较高左子树的左侧---左左：右单旋
- 新节点插入较高右子树的右侧---右右：左单旋
- 新节点插入较高左子树的右侧---左右：先左单旋再右单旋
- 新节点插入较高右子树的左侧---右左：先右单旋再左单旋
2.4 具体实现
基本思路都了解了，那么话不多说，直接开整，这里就只给大家上旋转的代码了，其他部分大家可以先自己尝试写一写，如有问题可以参考http://t.csdnimg.cn/2L1j5这篇文章
void RotateL(Node* parent)
{
Node* subR = parent->_right;//记录根节点的右孩子即旋转节点
Node* subRL = subR->_left;//记录旋转节点的左孩子
Node* parentParent = parent->_parent;//记录根节点的父节点
parent->_right = subRL;//将旋转节点的左孩子给给根节点的右
subR->_left = parent;//将原根节点给给旋转节点的左
//旋转完成，接下来更改各个节点的连接状态
if (subRL)
subRL->_parent = parent;
parent->_parent = subR;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
subR->_parent = parentParent;
if (parentParent->_left == parent)
parentParent->_left = subR;
else
parentParent->_right = subR;
}
subR->_bf = parent->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
parent->_left = subLR;
subL->_right = parent;
parent->_parent = subL;
if (subLR)
subLR->_parent = parent;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
subL->_parent = parentParent;
if (parentParent->_left == parent)
parentParent->_left = subL;
else
parentParent->_right = subL;
}
subL->_bf = parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{
//本身为新加入节点
subL->_bf = subLR->_bf = parent->_bf = 0;
}
else if (bf == -1)
{
//左子树有新加入节点
subL->_bf = subLR->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
//右子树有新加节点
subL->_bf = -1;
subLR->_bf = parent->_bf = 0;
}
else
{
assert(false);
}
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
//本身为新加入节点
subR->_bf = subRL->_bf = parent->_bf = 0;
}
else if (bf == -1)
{
//左子树有新加入节点
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
//右子树有新加节点
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
else
{
assert(false);
}
}
