目录
AVL树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
因此，两位俄罗斯的数学家G.M.Adelson - Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1 / 0 / 1) -- 注：之所以保持 1 是因为：左右高度差没办法保证能一直相等(例如只有两个结点呢？)
注：这里的 平衡因子 并不是必须的，这只是它的一种实现方式。
如果一棵二叉搜索树是高度平衡的，它就是AVL树。
如果它有n个结点，其高度可保持在O(logN)，搜索时间复杂度O(logN)。
AVL树节点的定义
template<class T>
struct AVLTreeNode
{
AVLTreeNode(const T& data)
: _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树的插入过程可以分为两步：
1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子 (插入一个结点，只会影响到它的祖先的平衡因子)
- a、如果插入在双亲的左边，双亲平衡因子--
- b、如果插入在双亲的右边，双亲的平衡因子++
当经过a、b两步情况过后，此时又可以分为接下来的三种情况
- c、双亲的平衡因子 == 0，此时双亲所在的子树高度不变，就不再需要继续往上更新平衡因子了，本次插入就算结束了。
- d、双亲的平衡因子 == 1 or -1，此时双亲所在的子树高度变了，即需要继续往上更新平衡因子(按照 a、b 的规则继续更新)，直到到达 c 的情况/出现 e 的情况。
- e、双亲的平衡因子 == 2 or -2，此时双亲所在的子树已经不平衡了，需要旋转处理。
以上就是 AVL树的插入 的主要流程。
AVL树的旋转（难点）
如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。
根据节点插入位置的不同，AVL树的旋转分为四种：
1. 新节点插入较高左子树的左侧---左左：右单旋
2. 新节点插入较高右子树的右侧---右右：左单旋
3. 新节点插入较高左子树的右侧---左右：先左单旋再右单旋
4. 新节点插入较高右子树的左侧---右左：先右单旋再左单旋
注：旋转首先要保证一件事，就是旋转完后这棵树还是符合搜索二叉树的规则的树！！
总结：
假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者 - 2，分以下情况考虑：
1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
- a、当pSubR的平衡因子为 1 时，执行左单旋
- b、当pSubR的平衡因子为 -1 时，执行右左双旋
2. pParent的平衡因子为 -2，说明pParent的左子树高，设pParent的左子树的根为pSubL
- a、当pSubL的平衡因子为 -1 时，执行右单旋
- b、当pSubL的平衡因子为 1 时，执行左右双旋
旋转完成后，原pParent为根的子树个高度降低，已经平衡(新的pParent的平衡因子为0)，不需要再向上更新。
补充：如果是单纯的单旋，旋转完之后参与旋转的两个根结点的平衡因子都会变成0。如果是双旋，旋转完之后参与旋转的三个根结点的平衡因子会受一开始新节点插入的位置影响。
AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
1.验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。
2.验证其为平衡树
每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)，节点的平衡因子是否计算正确。
AVL树的删除(本文不做具体的模拟实现)
因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，最差情况下一直要调整到根节点的位置。
具体实现可参考《算法导论》(基本都是伪代码，不一定好看懂) 或《数据结构 - 用面向对象方法与C++描述》殷人昆版。
注：删除调整平衡因子的判断条件和插入不同，删除是当平衡因子为 0 时，就继续往上更新，为 1 或 -1 才停止，为 2 或 -2 就要旋转。
主要逻辑：
- 先按搜索树的规则进行删除
- 再进行平衡因子的更新(出现不平衡旋转一下)
AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log(N)。但是如果要对AVL树做一些结构修改的操作时，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
AVL树的模拟实现
AVLTree.h：
#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
template <class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V> *_left;
AVLTreeNode<K, V> *_right;
AVLTreeNode<K, V> *_parent; // 注意：AVL树 这里还需要多一个 _parent，方便往上更新 平衡因子 // 没有 _parent 会很麻烦
std::pair<K, V> _kv;
int _bf; // balance factor
AVLTreeNode(const std::pair<K, V> &kv)
: _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0)
{
}
};
template <class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool insert(const std::pair<K, V> &kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node *parent = nullptr;
Node *cur = _root;
while (cur)
{
parent = cur;
if ((cur->_kv).first < kv.first)
{
cur = cur->_right;
}
else if ((cur->_kv).first > kv.first)
{
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if ((parent->_kv).first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent; // AVL树的 插入这里要比 普通搜索二叉树 的插入多一步
// 到这里，上面的代码仅仅只是完成了插入一个结点的工作
// 接下来，开始更新平衡因子 _bf
while (parent) // 可能存在一直更新都没触发下面的两个break的情况，根据分析一直更新下去，最后 parent 是变成 nullptr。
{
// 向左插入，--_bf
if (cur == parent->_left)
{
--parent->_bf;
}
// 向右插入，++_bf
else
{
++parent->_bf;
}
if (parent->_bf == 0) // 调整好了
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1) // 继续往上更新
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) // 当前子树出问题了，需要旋转调整一下平衡
{
if (parent->_bf == -2 && cur->_bf == -1) // 右单旋
{
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == 1) // 左单旋
{
RotateL(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;
}
void RotateR(Node *parent) // 右单旋 // 这里的 parent 的 _bf == -2
{
// 要抬高左边，降低右边
Node *subL = parent->_left; // 这里的 subL 的 _bf 为 -1
Node *subLR = subL->_right; // subL 的右子树 要给给 parent，当 parent 的左子树
// subL的值 < subLR的值 < parent的值
// 处理一个节点的同时也要记得处理它的父亲
parent->_left = subLR; // 将 subL 的右子树给给 parent
if (subLR) // 这边要注意 subLR 可能是 nullptr
subLR->_parent = parent;
subL->_right = parent; // 提高左边
subL->_parent = parent->_parent; // 要注意，要先把 parent 的 parent 给给 subL
if (parent->_parent) // 还要注意改 parent 的 parent // 因为 parent 可能就是根，那么 parent 的 parent 就是 nullptr，所以这里要 if 判断一下
{
if (parent->_parent->_left == parent)
{
parent->_parent->_left = subL;
}
else
{
parent->_parent->_right = subL;
}
}
else // 如果原本的 parent 是根的话，就更新一下根
{
_root = subL;
}
parent->_parent = subL; // 降低右边
// 根据图分析，旋转完之后，subL的_bf 和 parent的_bf 都为 0
// 所以，更新一下两者的_bf
parent->_bf = subL->_bf = 0;
}
void RotateL(Node *parent) // 左单旋 // 这里的 parent 的 _bf == 2
{
// 要抬高右边，降低左边
Node *subR = parent->_right; // 这里的 subR 的 _bf 为 1
Node *subRL = subR->_left; // subR 的左子树 要给给 parent，当 parent 的右子树
// parent的值 < subRL的值 < subR的值
// 处理一个节点的同时也要记得处理它的父亲
parent->_right = subRL; // 将 subR 的右子树给给 parent
if (subRL) // 这边要注意 subRL 可能是 nullptr
subRL->_parent = parent;
subR->_left = parent; // 提高右边
subR->_parent = parent->_parent; // 要注意，要先把 parent 的 parent 给给 subR
if (parent->_parent) // 还要注意改 parent 的 parent // 因为 parent 可能就是根，那么 parent 的 parent 就是 nullptr，所以这里要 if 判断一下
{
if (parent->_parent->_left == parent)
{
parent->_parent->_left = subR;
}
else
{
parent->_parent->_right = subR;
}
}
else // 如果原本的 parent 是根的话，就更新一下根
{
_root = subR;
}
parent->_parent = subR; // 降低右边
// 根据图分析，旋转完之后，subR的_bf 和 parent的_bf 都为 0
// 所以，更新一下两者的_bf
parent->_bf = subR->_bf = 0;
}
// 注：双旋的难点在于对节点的平衡因子的调节
void RotateRL(Node *parent) // 右左双旋(就是对 左单旋和右单旋 的封装) // 这里的 parent 的 _bf == 2
{
// 因为单旋会导致这几个结点的平衡因子都直接变为0，这可能和实际分析的最终结果不符，需要一些特殊处理
Node *subR = parent->_right; // 这里的 subR 的 _bf 为 -1
Node *subRL = subR->_left;
int bf = subRL->_bf;
// 先对 parent->_right 进行右单旋，然后这颗子树就变为了单纯的右边高
RotateR(parent->_right);
// 再对 parent 自己本身进行左单旋即可
RotateL(parent);
// 调整为正确的平衡因子(虽然上面的旋转函数对平衡因子的改变有一部分是正确的，但我们下面还是最好全都给它更新一下，做到万无一失)
subRL->_bf = 0; // subRL 去做新的根了，根据分析，不管什么情况新的根的_bf都为0。
if (bf == -1) // 代表一开始在 subRL 的左边插入
{
subR->_bf = 1; // subRL 的右子树(h-1)给了 subR 做左子树
parent->_bf = 0; // subRL 的左子树(h)给了 parent 做右子树
}
else if (bf == 1) // 代表一开始在 subRL 的右边插入
{
subR->_bf = 0; // subRL 的右子树(h)给了 subR 做左子树
parent->_bf = -1; // subRL 的左子树(h-1)给了 parent 做右子树
}
else if (bf == 0) // 代表 subRL 自己就是新增的结点
{
subR->_bf = 0;
parent->_bf = 0;
}
else // 理论不应该还有其他的情况
{
assert(false);
}
}
void RotateLR(Node *parent) // 左右双旋(就是对 左单旋和右单旋 的封装) // 这里的 parent 的 _bf == -2
{
// 因为单旋会导致这几个结点的平衡因子都直接变为0，这可能和实际分析的最终结果不符，需要一些特殊处理
Node *subL = parent->_left; // 这里的 subL 的 _bf 为 1
Node *subLR = subL->_right;
int bf = subLR->_bf;
// 先对 parent->_left 进行左单旋，然后这颗子树就变为了单纯的左边高
RotateL(parent->_left);
// 再对 parent 自己本身进行右单旋即可
RotateR(parent);
// 调整为正确的平衡因子(虽然上面的旋转函数对平衡因子的改变有一部分是正确的，但我们下面还是最好全都给它更新一下，做到万无一失)
subLR->_bf = 0; // subLR 去做新的根了，根据分析，不管什么情况新的根的_bf都为0。
if (bf == -1) // 代表一开始在 subLR 的左边插入
{
subL->_bf = 0; // subLR 的左子树(h)给了 subL 做右子树
parent->_bf = 1; // subLR 的右子树(h-1)给了 parent 做左子树
}
else if (bf == 1) // 代表一开始在 subLR 的右边插入
{
subL->_bf = -1; // subLR 的左子树(h-1)给了 subL 做右子树
parent->_bf = 0; // subLR 的右子树(h)给了 parent 做左子树
}
else if (bf == 0) // 代表 subLR 自己就是新增的结点
{
subL->_bf = 0;
parent->_bf = 0;
}
else // 理论不应该还有其他的情况
{
assert(false);
}
}
Node *Find(const std::pair<K, V> &kv)
{
Node *cur = _root;
while (cur)
{
if ((cur->_kv).first < kv.first)
{
cur = cur->_right;
}
else if ((cur->_kv).first > kv.first)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
void InOrder()
{
_InOrder(_root);
std::cout << std::endl;
}
bool IsBalance() // 下面的遍历打印，只能证明这是一颗搜索二叉树，并不能说明它是否平衡
{
return _IsBalance(_root);
}
int Height() // 返回树的高度
{
return _Height(_root);
}
int Size() // 计算树的大小
{
return _Size(_root);
}
private:
bool _IsBalance(Node *root) // 我们要做的事就是不断的去看每个结点的平衡因子就好(直接前序遍历就行)
{
if (root == nullptr)
return true;
if (root->_bf <= -2 || 2 <= root->_bf) // 这也算剪枝
return false;
bool left = _IsBalance_k(root->_left);
if (left == false)
return false; // 剪枝
bool right = _IsBalance_k(root->_right);
if (right == false)
return false; // 剪枝
return left && right;
}
int _Size(Node *root)
{
return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
}
int _Height(Node *root)
{
if (root == nullptr)
return 0;
return std::max(_Height(root->_left), _Height(root->_right)) + 1;
}
void _InOrder(Node *root /* = _root */) // 注意：这里不能给缺省值 _root，因为 _root 需要this指针调用，但是this指针本身就是形参，这样写玩不了。
{
if (root == nullptr)
return;
_InOrder(root->_left); // 左
std::cout << (root->_kv).first << ":" << (root->_kv).second << std::endl; // 根
_InOrder(root->_right); // 右
}
private:
Node *_root = nullptr;
};
void TestAVL_Insert_Balance1()
{
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
int a1[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
int a2[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
AVLTree<int, int> t;
for (auto &x : a2)
{
t.insert({x, x});
std::cout << x << "->" << t.IsBalance() << std::endl;
}
t.InOrder(); // 这里有个问题，没法给 InOrder() 这个函数传参，因为 _root 是私有函数，你在这里调不动。
// 那么该怎么解决呢？
// 给个缺省值吗？ 这是不行的，给不了
// 那该怎么办？
// 三种方法：1、把这个测试函数定义成友元。(这个方法很不好，就一个测试函数又不是要经常用，定义成友元有点太没边界感了)
// 2、学Java，弄一个 Get() 函数，把 _root 拿出来。
// 3、看上面的操作。(封装一下，套一层)
std::cout << t.IsBalance() << std::endl;
}
// 补充：对于这种比较复杂的程序，如果哪里出了bug，有个好方法就是在某些关键的步骤或循环里加个打印，这种方式比较容易知道哪里出错了。
void TestAVL_Insert_Balance2()
{
const int N = 100000000; // 注：32位环境下，这里插入 1亿 个节点会失败，因为空间不够，new 爆了
srand((unsigned int)time(nullptr));
std::vector<int> v(N);
AVLTree<int, int> t;
for (int i = 0; i < N; ++i)
{
v[i] = rand() + i;
}
for (auto x : v)
{
t.insert({x, x});
}
std::cout << "t.Height():" << t.Height() << std::endl;
std::cout << "t.Size():" << t.Size() << std::endl;
std::cout << "t.IsBalance():" << t.IsBalance() << std::endl;
size_t begin = clock();
for (auto x : v)
{
t.Find({ x,x });
}
size_t end = clock();
std::cout << "t.Find():" << end - begin << std::endl;
}
// 注：程序主要时间消耗在于插入时的 new 节点。