那么到底该如何对二叉搜索树进行改造，才能提高我们查找数据的效率呢？
上述两位数学家是这样做的：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
由此我们也就知道了一棵二叉搜索搜索树满足以下两个性质就能成为一棵搜索效率高的AVL树：
●它的左右子树都是AVL树
●左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
注：如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O(logN)，搜索时间复杂度O(logN)。
对于AVL树的节点我们采取三叉链的形式，也就是左右结点及其父亲结点，为了方便后续我们进行树是否平衡的判断以及进行旋转的操作，除此之外我们还要引入平衡因子来帮助我们判断当前子树是否平衡以及不平衡时需要进行何种的旋转，例如：左单旋转，右单旋，左右单旋等。
//AVL树节点的定义——三叉链和平衡因子
template<class T>
struct AVLTreeNode
{
AVLTreeNode(const T& data = T())
: _pLeft(nullptr)
, _pRight(nullptr)
, _pParent(nullptr)
, _data(data)
, _bf(0)
{}
AVLTreeNode<T>* _pLeft;
AVLTreeNode<T>* _pRight;
AVLTreeNode<T>* _pParent;
T _data;
int _bf; // 节点的平衡因子
};在定义完一颗AVL树的节点，那么我们该如何进行节点的插入呢？
对于AVL树来言，它的插入过程可以大致分为两步：
①按照二叉搜索树的方式插入新节点
②调整节点的平衡因子
对于第一个步骤，由于AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树，所以新节点插入的第一步其实是与上一篇文章二叉搜索树的插入是一样的，在此笔者就不对其进行过多描述，有需要的小伙伴可以回顾下这篇文章：
那么第二个步骤就是其与二叉搜索树不同的地方所在了，我们到底要如何去引入这个平衡因子以及去调整呢？在看完上面对AVL树的介绍后我们知道了对于这样的一棵树，从中选取任一节，我们都能够发现其左右子树的高度差不会大于1，也就是当一颗左子树高度为1的时候，它的右子树的高度取值只能为：0，1，2，而不能是大于2的值，这样其与1的差值就会大于1了，也就不满足AVL树的定义了。在清楚这样的底层逻辑后，我们该如何去衡量左右子树高度差不为1呢，这也就是我们为什么要引入平衡因子了。
对于每一个节点来说，无论它是否有左右子树，它都有平衡因子。当这个节点没有任何孩子，也就是左右子树为空的时候，其左右子树的高度差为0，那么这个时候平衡因子的值我们规定为0，即平衡因子的初始值。每当右子树高度加1的时候我们就对平衡因子进行++，反之左子树的高度加1的时候我们就对平衡因子进行--，这样如果平衡因子如果大于1就说明右子树的与左子树的高度差大于1，不满足AVL树的定义；而另一种情况如果平衡因子小于-就说明左子树与右子树的高度差大于1，也不满足AVL树的的定义。这样一来，我们只需要通过判断平衡因子的绝对值是否大于1，就能够判断这棵节点所在的子树是否满足AVL树的定义，从而扩大到整棵树是否满足AVL树的定义。
具体代码如下：
// 在AVL树中插入值为data的节点
bool Insert(const T & data)
{
//插入节点
//空树
if (_pRoot == nullptr)
{
_pRoot = new Node(data);
return true;
}
//树不为空
else
{
//寻找父亲结点
Node* parent = nullptr;
Node* cur = _pRoot;
while (cur)
{
if (cur->_data > data)
{
parent = cur;
cur = cur->_pLeft;
}
else if (cur->_data < data)
{
parent = cur;
cur = cur->_pRight;
}
else return false;
}
//插入新节点
cur = new Node(data);
if (cur->_data > parent->_data)
{
parent->_pRight = cur;
cur->_pParent = parent;
}
else
{
parent->_pLeft = cur;
cur->_pParent = parent;
}
//调整平衡因子
while (parent)
{
while (parent)
{ //更新平衡因子
if (parent->_pLeft == cur) parent->_bf--;
else parent->_bf++;
}
//根据平衡因子的情况判断是否需要旋转
//...
}
return true;
}
}在插入节点之后我们已经对新插入节点的父亲结点进行了平衡因子的调整，可能是++，也可能是--，取决于新节点插入在右子树还是左子树。下面我们就平衡因子的不同情况来进行讨论以及在不同的平衡因子下我们该进行何种的旋转。
首先我们需要明确的一点是在新节点插入后，其父亲节点的平衡因子一定需要调整，在插入之前，parent 的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
1. 如果cur插入到parent的左侧，只需给parent的平衡因子-1即可
2. 如果cur插入到parent的右侧，只需给parent的平衡因子+1即可
在插入后，parent的平衡因子可能有三种情况：0，正负1， 正负2
1. 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整 成0，此时满足AVL树的性质，插入成功
2. 如果parent的平衡因子为正负1，说明插入前parent的平衡因子一定为0，插入后被更 新成正负1，此时以parent为根的树的高度增加，需要继续向上更新
3. 如果parent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转处理
由于新节点的插入就会引起平衡因子的更新，不同的平衡因子也就意味着不同的状态。对于AVL树来言，引起旋转的平衡因子大致分为四种，而这四种也分别对应不同的旋转方法。下面我们就这四种情况进行详细的介绍。
当新节点插入较高子树的的左侧时，就会导致要旋转的子树的根结点pParent平衡因子为2，其左子树cur的平衡因子为1的情况，而面对这种情况，我们就需要采取左单旋转的情况来使这棵子树重新平衡成为一颗AVL树，即cur节点的左子树与父亲节点进行右侧链接，父亲节点与cur节点进行左侧链接，倘若父亲节点存在祖父节点，则还需要将cur节点与祖父节点进行链接，而左侧还是右侧取决于父亲节点与祖父节点间的链接方式
具体旋转图和代码如下：
注：
下图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左子树增加 了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子树增加一层， 即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：
1. 30节点的右孩子可能存在，也可能不存在
2. 60可能是根节点，也可能是子树。如果是根节点，旋转完成后，要更新根节点； 如果是子树，可能是某个节点的左子树，也可能是右子树
具体旋转图和代码如下：
注：下图中cur节点为60，父亲节点为30
// 左单旋转
void RotateL(Node* pParent)
{
Node* grandparent = pParent->_pParent;
Node* cur = pParent->_pRight;
Node* cur_left = cur->_pLeft;
//旋转相关结点
if(cur_left) cur_left->_pParent = pParent; //不为空
pParent->_pRight = cur_left;
cur->_pLeft = pParent;
pParent->_pParent = cur;
//判断根结点是否为父亲节点
if (this->_pRoot == pParent)
{
this->_pRoot = cur;
cur->_pParent = nullptr;
}
//判断父亲节点是祖父节点的左右子树以方便左子树的与祖父节点的链接
else if (grandparent->_pLeft == pParent)
{
grandparent->_pLeft = cur;
cur->_pParent = grandparent;
}
else if (grandparent->_pRight == pParent)
{
grandparent->_pRight = cur;
cur->_pParent = grandparent;
}
//调整平衡因子
cur->_bf = pParent->_bf = 0;
}右单旋转与左单旋转类似， 当新节点插入较高子树的的右侧就会导致要旋转的子树的根结点pParent平衡因子为-2，其左子树cur的平衡因子为-1的情况。
而面对这种情况，我们就需要采取右单旋转的情况来使这棵子树重新平衡成为一颗AVL树，即cur节点的右子树与父亲节点进行左侧链接，父亲节点与cur节点进行右侧链接，倘若父亲节点存在祖父节点，则还需要将cur节点与祖父节点进行链接，而左侧还是右侧取决于父亲节点与祖父节点间的链接方式。
具体旋转图和代码如下：
注：下图中cur节点为30，父亲节点为60
// 右单旋
void RotateR(Node* pParent)
{
Node* grandparent = pParent->_pParent;
Node* cur = pParent->_pLeft;
Node* cur_right = cur->_pRight;
//旋转相关节点
pParent->_pLeft = cur_right;
if(cur_right) cur_right->_pParent = pParent; //不为空
cur->_pRight = pParent;
pParent->_pParent = cur;
//判断根结点是否为父亲节点
if (grandparent == nullptr)
{
this->_pRoot = cur;
cur->_pParent = nullptr;
}
//判断父亲节点是祖父节点的左右子树以方便左子树的与祖父节点的链接
else if (grandparent->_pLeft == pParent)
{
grandparent->_pLeft = cur;
cur->_pParent = grandparent;
}
else if (grandparent->_pRight == pParent)
{
grandparent->_pRight = cur;
cur->_pParent = grandparent;
}
//调整平衡因子
cur->_bf = pParent->_bf = 0;
}上面两种情况都属于属于新插入节点位于较高子树的同侧，也就左子树高插入左侧，右子树高插入右侧，即平衡因子为【2，1】或者【-2，-1】两种情况，我们只需进行单侧旋转即可。但是倘若插入在较高子树的不同侧这时候仅仅通过单次旋转就不能够使其重新成为一颗AVL树，而是会将其转化成另一种情况，即【2，-1】，【-2，1】两种情况的相互转化，即死循环。于是面对四种情况中剩下的这两种情况我们就需要采取新的旋转方式使其平衡，就是通过连续两次不同侧的旋转使其重新成为一颗AVL树，下面我们先针对【-2，1】这一平衡因子的情况进行讲解。
当新节点插入较高左子树的右侧，就会导致要旋转的子树的根结点pParent平衡因子为-2，其左子树cur的平衡因子为1的情况。
而面对这种情况，我们就需要采取左右单旋的情况来使这棵子树重新平衡成为一颗AVL树，即cur节点的右子树与cur节点进行左侧链接，cur节点的右子树与父亲节点进行右侧链接，在链接的同时将其左右子树分别链接给cur节点的右侧和父亲节点的左侧，倘若父亲节点存在祖父节点，则还需要将cur节点的右子树与祖父节点进行链接，而左侧还是右侧取决于父亲节点与祖父节点间的链接方式。
具体的旋转图和代码如下：
注：下图中cur节点为30，父亲节点为90，cur的右子树节点为60
// 左右双旋
void RotateLR(Node* pParent)
{
Node* cur = pParent->_pLeft;
Node* cur_right = cur->_pRight;
int bf = cur_right->_bf;
RotateL(cur);
RotateR(pParent);
//调整平衡因子
if (bf == 0)
{
cur->_bf = pParent->_bf =cur_right->_bf = 0;
}
else if (bf == -1)
{
pParent->_bf = 1;
cur->_bf = cur_right->_bf = 0;
}
else if (bf == 1)
{
cur->_bf = -1;
pParent->_bf = cur_right->_bf = 0;
}
else
{
assert("RotateLR()");
}
}当新节点插入较高右子树的左侧，就会导致要旋转的子树的根结点pParent平衡因子为2，其左子树cur的平衡因子为1的情况。
而面对这种情况，我们就需要采取右左单旋的情况来使这棵子树重新平衡成为一颗AVL树，即cur节点的左子树与cur节点进行右侧链接，cur节点的左子树与父亲节点进行左侧链接，在链接的同时将其左右子树分别链接给父亲节点的右侧和cur节点的左侧，倘若父亲节点存在祖父节点，则还需要将cur节点的右子树与祖父节点进行链接，而左侧还是右侧取决于父亲节点与祖父节点间的链接方式。
具体的旋转图和代码如下：
注：下图中cur节点为90，父亲节点为30，cur的左子树节点为60
// 右左双旋
void RotateRL(Node* pParent)
{
Node* cur = pParent->_pRight;
Node* cur_left = cur->_pLeft;
//提前保存避免旋转后处理为0
int bf = cur_left->_bf;
RotateR(cur);
RotateL(pParent);
//调整平衡因子
if (bf == 0)
{
cur->_bf = pParent->_bf =cur_left->_bf = 0;
}
else if (bf == -1)
{
cur->_bf = 1;
pParent->_bf = cur_left->_bf = 0;
}
else if (bf == 1)
{
pParent->_bf = -1;
cur->_bf = cur_left->_bf = 0;
}
else
{
assert("RotateRL()");
}
}到这里，关于AVL树的四种平衡因子相对应的四种旋转我们都已讲解完毕，给大家总结一下：
1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为cur ♥当cur的平衡因子为1时，执行左单旋
♥当cur的平衡因子为-1时，执行右左双旋
2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为cur ♥当cur的平衡因子为-1时，执行右单旋
♥当cur的平衡因子为1时，执行左右双旋
当我们进行完AVL树节点的插入后，我们也就搭建好了一颗理想的AVL树，但是我们理论归理论，实际上当我们不断地对这棵树插入节点后是否是一颗AVL树，我们还需要对其进行验证，对于一颗AVL树的验证。我们可以分为两步：
1. 验证其为二叉搜索树如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2. 验证其为平衡树每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) 节点的平衡因子是否计算正确
具体代码如下：
// 根据AVL树的概念验证pRoot是否为有效的AVL树
//中序遍历
void _InOrder(Node* pRoot)
{
if (pRoot == nullptr) return;
_InOrder(pRoot->_pLeft);
cout << pRoot->_data << " ";
_InOrder(pRoot->_pRight);
}
//平衡判断
bool _IsAVLTree(Node* pRoot)
{
if (pRoot == nullptr) return true;
//检测平衡因子是否正常
int LTree_bf = _Height(pRoot->_pLeft);
int RTree_bf = _Height(pRoot->_pRight);
if (RTree_bf - LTree_bf != pRoot->_bf)
{
cout << "平衡因子不正常";
return false;
}
//return true;
return abs(RTree_bf - LTree_bf) < 2 && _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
}因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与其删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。 具体实现大家可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。
当我们模拟实现在AVL树后，它的性能到底如何呢，让我们来分析一下。
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这 样可以保证查询时高效的时间复杂度，即logN。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时， 有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
#pragma once
template<class T>
struct AVLTreeNode
{
AVLTreeNode(const T& data = T())
: _pLeft(nullptr)
, _pRight(nullptr)
, _pParent(nullptr)
, _data(data)
, _bf(0)
{}
AVLTreeNode<T>* _pLeft;
AVLTreeNode<T>* _pRight;
AVLTreeNode<T>* _pParent;
T _data;
int _bf; // 节点的平衡因子
};
// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
typedef AVLTreeNode<T> Node;
public:
AVLTree()
: _pRoot(nullptr)
{}
// 在AVL树中插入值为data的节点
bool Insert(const T& data)
{
//插入节点
//空树
if (_pRoot == nullptr)
{
_pRoot = new Node(data);
return true;
}
//树不为空
else
{
//寻找父亲结点
Node* parent = nullptr;
Node* cur = _pRoot;
while (cur)
{
if (cur->_data>data)
{
parent = cur;
cur = cur->_pLeft;
}
else if (cur->_data < data)
{
parent = cur;
cur = cur->_pRight;
}
else return false;
}
//插入新节点
cur = new Node(data);
if (cur->_data > parent->_data)
{
parent->_pRight = cur;
cur->_pParent = parent;
//parent->_bf++;
}
else
{
parent->_pLeft = cur;
cur->_pParent = parent;
// parent->_bf--;
}
//判断是否需要旋转
while (parent)
{ //更新平衡因子
if (parent->_pLeft == cur) parent->_bf--;
else parent->_bf++;
//插入后平衡
if (parent->_bf == 0) break;
//擦入后暂稳态
else if (parent->_bf == 1 || parent->_bf == -1)
{
//继续向上传递平衡因子
cur = parent;
parent = parent->_pParent;
}
//插入后不平衡
else if (parent->_bf == 2 || parent->_bf == -2)
{
//左单旋
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) RotateRL(parent);
//右左单旋
else if (parent->_bf == -2 && cur->_bf == 1) RotateLR(parent);
break;
}
else assert(false);
}
return true;
}
}
// AVL树的验证
bool IsAVLTree()
{
return _IsAVLTree(_pRoot);
}
//AVL树的高度
size_t Height()
{
return _Height(_pRoot);
}
//中序遍历AVL树
void InOrder()
{
_InOrder(_pRoot);
}
private:
// 根据AVL树的概念验证pRoot是否为有效的AVL树
bool _IsAVLTree(Node* pRoot)
{
if (pRoot == nullptr) return true;
//检测平衡因子是否正常
int LTree_bf = _Height(pRoot->_pLeft);
int RTree_bf = _Height(pRoot->_pRight);
if (RTree_bf - LTree_bf != pRoot->_bf)
{
cout << "平衡因子不正常";
return false;
}
//return true;
return abs(RTree_bf - LTree_bf) < 2 && _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
}
void _InOrder(Node* pRoot)
{
if (pRoot == nullptr) return;
_InOrder(pRoot->_pLeft);
cout << pRoot->_data << " ";
_InOrder(pRoot->_pRight);
}
size_t Greater(size_t a, size_t b)
{
return a > b ? a : b;
}
size_t _Height(Node* pRoot)
{
//空树
if (pRoot == nullptr) return 0;
//非空树
return 1 + Greater(_Height(pRoot->_pLeft), _Height(pRoot->_pRight));
}
// 右单旋
void RotateR(Node* pParent)
{
Node* grandparent = pParent->_pParent;
Node* cur = pParent->_pLeft;
Node* cur_right = cur->_pRight;
//旋转相关节点
pParent->_pLeft = cur_right;
if(cur_right) cur_right->_pParent = pParent; //不为空
cur->_pRight = pParent;
pParent->_pParent = cur;
if (grandparent == nullptr)
{
this->_pRoot = cur;
cur->_pParent = nullptr;
}
else if (grandparent->_pLeft == pParent)
{
grandparent->_pLeft = cur;
cur->_pParent = grandparent;
}
else if (grandparent->_pRight == pParent)
{
grandparent->_pRight = cur;
cur->_pParent = grandparent;
}
//调整平衡因子
cur->_bf = pParent->_bf = 0;
}
// 左单旋转
void RotateL(Node* pParent)
{
Node* grandparent = pParent->_pParent;
Node* cur = pParent->_pRight;
Node* cur_left = cur->_pLeft;
//旋转相关结点
if(cur_left) cur_left->_pParent = pParent; //不为空
pParent->_pRight = cur_left;
cur->_pLeft = pParent;
pParent->_pParent = cur;
if (this->_pRoot == pParent)
{
this->_pRoot = cur;
cur->_pParent = nullptr;
}
else if (grandparent->_pLeft == pParent)
{
grandparent->_pLeft = cur;
cur->_pParent = grandparent;
}
else if (grandparent->_pRight == pParent)
{
grandparent->_pRight = cur;
cur->_pParent = grandparent;
}
//调整平衡因子
cur->_bf = pParent->_bf = 0;
}
// 右左双旋
void RotateRL(Node* pParent)
{
Node* cur = pParent->_pRight;
Node* cur_left = cur->_pLeft;
//提前保存避免旋转后处理为0
int bf = cur_left->_bf;
RotateR(cur);
RotateL(pParent);
//调整平衡因子
if (bf == 0)
{
cur->_bf = pParent->_bf =cur_left->_bf = 0;
}
else if (bf == -1)
{
cur->_bf = 1;
pParent->_bf = cur_left->_bf = 0;
}
else if (bf == 1)
{
pParent->_bf = -1;
cur->_bf = cur_left->_bf = 0;
}
else
{
assert("RotateRL()");
}
}
// 左右双旋
void RotateLR(Node* pParent)
{
Node* cur = pParent->_pLeft;
Node* cur_right = cur->_pRight;
int bf = cur_right->_bf;
RotateL(cur);
RotateR(pParent);
//调整平衡因子
if (bf == 0)
{
cur->_bf = pParent->_bf =cur_right->_bf = 0;
}
else if (bf == -1)
{
pParent->_bf = 1;
cur->_bf = cur_right->_bf = 0;
}
else if (bf == 1)
{
cur->_bf = -1;
pParent->_bf = cur_right->_bf = 0;
}
else
{
assert("RotateLR()");
}
}
private:
Node* _pRoot;
};
void text_1()
{
AVLTree<int> Tree;
const int N = 10000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; ++i)
{
v.push_back(i);
}
for (const auto& e : v)
{
Tree.Insert(e);
cout<<e<<":"<<Tree.IsAVLTree() << " ->";
//Tree.InOrder();
cout << endl;
}
}
到此为止，关于AVL树的讲解就告一段落了，至于其他的内容，小伙伴们敬请期待呀！
最后祝大家10月24日程序节快乐呀！！！
关注我 _麦麦_分享更多干货：
大家的「关注❤️ + 点赞👍 + 收藏⭐」就是我创作的最大动力！谢谢大家的支持，我们下期见！
因篇幅问题不能全部显示，请点此查看更多更全内容