1、什么是AVL树？
??AVL树可以是一棵空树
??AVL树也可以是一棵具有如下性质的二叉搜索树：
????①它的左右子树都是一棵AVL树
????②左右子树高度之差（平衡因子）的绝对值不能超过1
如果一棵二叉搜索树是高度平衡的，那么他就是AVL树。
如果他有n个结点，其高度可以保持在O(log2n),搜索时时间复杂度也就是O(log2n)
2、AVL树部分模块模拟实现
2.1 AVL树结点的定义：
AVL树本质上讲，它是一棵二叉搜索树，只不过加上了平衡因子这一限制条件。
也就是说，在插入一个新节点时，我们不仅要考虑结点的插入位置，还需要考虑插入该节点后对于树中其他结点来说，平衡因子是否需要更新。
其中，插入节点的父节点，它的平衡因子一定需要改变。这就要求我们需要能够快速定位到插入节点的父节点。因此，我们对于AVL树结点的结构应定义为孩子双亲表示法
🆗，下面给出结点的基本结构：
template<class T>
struct AVLTreeNode
{
typedef AVLTreeNode<T> Node;
Node* _left;//左孩子
Node* _right;//右孩子
Node* _parent;//双亲
T _value;
int _bf;//结点的平衡因子
AVLTreeNode(const T& value)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_value(value)
,_bf(0)
{}
}
2.2 AVL树的插入
AVL树的插入可以分为两大步骤：
①按照二叉搜索树的方式插入新节点
??第一步不是本文的重点，不了解的童鞋移步至二叉搜索树
②调整结点的平衡因子
1、现在我们先给出实现第一部分的核心代码：
if (nullptr == _root)
{
//这是一棵空树，直接插入结点即可
_root = new Node(value);
return true;
}
//1、按照二叉搜索树的方式查找结点的插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_value == value)
{
return false;
}
else if (cur->_value > value)
{
parent = cur;
cur = cur->_left;
}
else
{
parent = cur;
cur = cur->_right;
}
}
Node* newNode = new Node(value);
if (value > parent->_value)
{
parent->_right = newNode;
}
else
{
parent->_left = newNode;
}
newNode->_parent = parent;
2、更新双亲的平衡因子
分析：
??首先，新节点插入之后，其双亲结点的平衡因子一定需要跟新，因为，插入一个结点，则该节点一定会影响其双亲的左右子树高度。因此，我们首先将双亲结点的平衡因子进行更新；
??对parent的平衡因子更新完毕后，parent的平衡因子可能的取值是：
0 、正负1、正负2。我们下面就这三种大情况分别讨论：
情况1：parent的平衡因子为0
??该情况说明插入之前parent的平衡因子为正负1，插入之后被调整成为0，此时满足AVL树的性质，插入成功！
情况2：parent的平衡因子为正负1
??该情况说明插入之前parent的平衡因子一定是0（也就是说以parent为u根的二叉树左右子树高度是一样的）,
??插入后被更新为正负1，此时以parent为根的树高度增加了，势必会影响到parent上面结点的平衡因子，因此需要继续向上跟新。
情况3：parent的平衡因子为正负2
?该种情况较为复杂。首先，我们可以知道此时parent的平衡因子违反了AVL树的特性，因此需要对齐进行旋转处理。至于如何旋转，我们分以下几种场景进行讨论：
??场景一：新节点插入在较高左子树的左侧----->右单旋
具体场景如下图所示：
具体操作见代码：
void RotateRight(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
subL->_right = parent;
if (subLR)
{
subLR->_parent = parent;
}
//更新subL和parent的双亲
Node* pparent = parent->_parent;
parent->_parent = subL;
subL->_parent = pparent;
//处理pparent
if (nullptr == pparent)
{
_root == subL;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
}
//跟新subL和parent的平衡因子
subL->_bf = parent->_bf = 0;
}
??场景二：新节点插入在较高右子树的右侧----->左单旋
具体操作见代码：
void RotateLeft(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
//更新parent && subR的双亲
Node* pparent = parent->_parent;
parent->_parent = subR;
subR->_parent = pparent;
//处理pparent
if (nullptr == pparent)
{
_root = subR;
}
else
{
if (pparent->_left == parent)
{
pparent->_left == subR;
}
else
{
pparent->_right = subR;
}
}
//跟新subR && parent的平衡因子
subR->_bf = parent->_bf = 0;
}
??场景三：新节点插入在较高左子树的右侧----->左右双旋
具体代码：
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateLeft(parent->_left);
RotateRight(parent);
if (1 == bf)
{
subL->_bf = -1;
}
else if (-1 == bf)
{
parent->_bf = 1;
}
}
??场景四：新节点插入在较高右子树的左侧----->右左双旋
此场景类比场景三，这里直接给出代码：
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateRight(parent->_right);
RotateLeft(parent);
if (1 == bf)
parent->_bf = -1;
else if (-1 == bf)
subR->_bf = 1;
}
2.3 AVL的验证
AVL树是在二叉搜索树的基础上增加了平衡因子，因此我们可以从两方面进行验证：
??1、验证是否是一棵二叉搜索树
思路：查看中序遍历结果，若有序，则为二叉搜索树
??2、验证它是否是一棵平衡树
思路：每个节点的高度差不超过1
int GetHigh(Node* root)
{
if (nullptr == root)
return 0;
int leftHigh = GetHigh(root->_left);
int rightHigh = GetHigh(root->_right);
return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;
}
bool _IsAVLTree(Node* root)
{
if (nullptr == root)
{
return true;
}
int leftHigh = GetHigh(root->_left);
int rightHigh = GetHigh(root->_right);
if (rightHigh - leftHigh != root->_bf || abs(root->_bf) > 1)
{
cout << "Node:" << root->_value << endl;
cout << rightHigh - leftHigh << " " << root->_bf << endl;
return false;
}
// 根的左子树 和 根的右子树
return _IsAVLTree(root->_left) &&
_IsAVLTree(root->_right);
}
以上就是AVL树插入模块的模拟实现与验证。具体源码请参考AVL模拟
