文章目录
AVL 树详解AVL树的概念平衡因子
AVL树基本操作构建AVL树AVL插入操作左单旋右单旋先右旋再左旋先左旋再右旋
总结
AVL树的性能
AVL 树详解
AVL树的概念
平衡二叉树 又名 平衡二叉搜索（排序）树，简称 AVL树（Balanced Binary Tree） （BBT）。
AVL树名字的由来： 两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。 为了纪念他们，将 平衡二叉树 称为 AVL树。
AVL树本质上是二叉搜搜树，但是它又具有以下特点：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，左右两个子树也都是一棵平衡二叉树。
平衡因子
这里介绍一个概念：平衡因子，平衡因子在AVL树中是一个极其重要的概念。
平衡因子（Balance Factor，简写为bf） 一个节点的平衡因子大小计算方式： 结点的平衡因子 = 左子树的高度 - 右子树的高度 。
在 AVL树中，所有节点的平衡因子都必须满足： -1<=bf<=1，即当前节点的左右两个子树的高度差的绝对值不超过1。
两张图理解平衡因子： 由AVL树的定义可知，上图符合AVL（平衡二叉树的定义），所有节点的平衡因子的绝对值都不大于2.
再来看一张图： 由AVL树的定义可知，上图不符合AVL树的定义，因为节点值为1的点平衡因子不符合要求，所以上图不是AVL树。
AVL树的作用： 对于一般的二叉搜索树，其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度同时也由此而决定。但在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。因此，AVL树严格操纵树两端的平衡性，使其在对数据进行操纵时的效率最大化。
AVL树基本操作
构建AVL树
构建AVL树的基本节点 AVL树的基本节点需要包含其左孩子的指针、右孩子指针、双亲指针、记录平衡因子的bf变量以及节点中存储的数据类型。 值得一提的是，AVL树中的基本节点中的数据都是以键值对的形式进行存储的。
AVL树基本节点的定义：
template
class AVLTreeNode
{
public:
AVLTreeNode
AVLTreeNode
AVLTreeNode
pair
short bf;
AVLTreeNode(const pair
:left(nullptr), right(nullptr), parent(nullptr), kv(_kv), bf(0)
{
}
};
注意：AVL树与二叉搜索树不同的是，AVL树的节点还多了一个指向双亲的指针 parent，用于在插入时调节平衡因子等地方使用使用 AVL树类的定义：
template
class AVLTree
{
typedef AVLTreeNode
AVLTreeNode
public:
AVLTree():root(nullptr){}
AVL插入操作
为了保持AVL树的平衡，插入操作可能需要进行旋转。这里分为4中情况调整，本文将逐一分析
左单旋
parent 的右子树的右子树增加节点(如下图)，需要进行左单旋。 如图：在 c 处增加一个节点，那么此时 parent 节点处的平衡因子为 2 ，需要进行调整，将 subR 节点的左孩子作为 parent 节点的右孩子，在将 parent 作为subR的左孩子。即完成了一次左单旋。
注意：这里的 h >= 0 ，也就是说 a、b、c 三处的子树高度可以是0(子树为空)到无穷；
旋转完后需要在修改相应节点的平衡因子。
代码如下：
void RotateL(Node* parent) //左旋
{
Node* subR = parent->right, * subRL = subR->left;
parent->right = subRL;
if(subRL) //可能不存在，需要判断
subRL->parent = parent;
subR->left = parent;
if (root == parent)
{
subR->parent = nullptr;
root = subR;
}
else
{
Node* P_parent = parent->parent;
if (P_parent->left == parent)
P_parent->left = subR;
else
P_parent->right = subR;
subR->parent = P_parent;
}
parent->parent = subR;
//修改相应的平衡因子
parent->bf = subR->bf = 0;
}
右单旋
parent 的左子树左子树增加节点(如下图)，需要进行右单旋。 如图：在 a 处增加一个节点，那么此时 parent 节点处的平衡因子为 -2 ，需要进行调整，将 subL节点的右孩子作为 parent 节点的左孩子，再将 parent 作为subL的右孩子。即完成了一次右单旋。
注意：这里的 h >= 0 ，也就是说 a、b、c 三处的子树高度可以是0(子树为空)到无穷；
旋转完后需要在修改相应节点的平衡因子。
代码如下：
void RotateL(Node* parent) //左旋
{
Node* subR = parent->right, * subRL = subR->left;
parent->right = subRL;
if(subRL) //可能不存在，需要判断
subRL->parent = parent;
subR->left = parent;
if (root == parent)
{
subR->parent = nullptr;
root = subR;
}
else
{
Node* P_parent = parent->parent;
if (P_parent->left == parent)
P_parent->left = subR;
else
P_parent->right = subR;
subR->parent = P_parent;
}
parent->parent = subR;
//修改相应的平衡因子
parent->bf = subR->bf = 0;
}
先右旋再左旋
subRL 的右子树增加节点(如下图)，需要进行右单旋。 如图：在 c 处增加一个节点，那么此时 parent 节点处的平衡因子为 2 ，需要进行调整，将 subRL节点的右孩子作为 subR 节点的左孩子，subR作为subRL的右孩子，parent的右孩子修改为subRL,这样对于subR节点就完成了一次右旋，再将 subRL的左孩子作为parent的右孩子，parent作为subRL的左孩子，即完成了一次右左单旋。 注意：这里的 h >= 0 ，也就是说 a、b、c 三处的子树高度可以是0(子树为空)到无穷；
具体图示如下图：
根据最后调整后的树，修改parent，subR，subRL的平衡因子。 当一开始插入的位置是b时，上述旋转操作不变，只有在最后修改平衡因子时有所不同，所以在进行两次旋转前，需要先记录subRL的平衡因子，根据其subRL平衡因子再修改调整后的树的平衡因子。
代码如下：
void RotateRL(Node* parent)
{
Node* subR = parent->right, * subRL = subR->left;
short _bf = subRL->bf;
RotateR(parent->right);
RotateL(parent);
if (_bf == 0)
{ //subRL 自己就是新增节点,此时parent节点下的子树只有parent，subR，subRL这三个节点
subR->bf = parent->bf = subRL->bf = 0;
}
else if (_bf == 1) //subRL右子树新增节点
{
subR->bf = subRL->bf = 0;
parent->bf = -1;
}
else if (_bf == -1)
{
subR->bf = 1;
subRL->bf = parent->bf = 0;
}
else
{
assert(false);
}
}
先左旋再右旋
subLR 的右子树增加节点(如下图)，需要进行左单旋。 如图：在 c 处增加一个节点，那么此时 parent 节点处的平衡因子为 -2 ，需要进行调整，将 subLR节点的左孩子作为 subL 节点的右孩子，subL作为subLR的左孩子，parent的左孩子修改为subLR,这样对于subLR节点就完成了一次右旋，再将 subLR的右孩子作为parent的左孩子，parent作为subLR的右孩子，即完成了一次左右单旋。 注意：这里的 h >= 0 ，也就是说 a、b、c 三处的子树高度可以是0(子树为空)到无穷；
具体图示如下图：
根据最后调整后的树，修改parent，subR，subRL的平衡因子。 当一开始插入的位置是b时，上述旋转操作不变，只有在最后修改平衡因子时有所不同，所以在进行两次旋转前，需要先记录subLR的平衡因子，根据其subLR平衡因子再修改调整后的树的平衡因子。
总结
假如以 parent 为根的子树不平衡，即 parent 的平衡因子为2或者-2，分以下情况考虑
parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR
当subR的平衡因子为1时，执行左单旋当subR的平衡因子为-1时，执行右左双旋 parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL
当subL的平衡因子为-1是，执行右单旋当subL的平衡因子为1时，执行左右双旋
旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新。
AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这 样可以保证查询时高效的时间复杂度，即
l
o
g
2
(
N
)
log_2 (N)
log2(N)。但是如果要对AVL树做一些结构修改的操 作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时， 有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数 据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
代码总览：
#include
#include
#include
using namespace std;
template
class AVLTreeNode
{
public:
AVLTreeNode
AVLTreeNode
AVLTreeNode
pair
short bf;
AVLTreeNode(const pair
:left(nullptr), right(nullptr), parent(nullptr), kv(_kv), bf(0)
{
}
};
template
class AVLTree
{
typedef AVLTreeNode
AVLTreeNode
public:
AVLTree():root(nullptr){}
~AVLTree() { Destory(root); }
bool Insert(const pair
{
if (!root)
{
root = new Node(_kv);
return true;
}
Node* cur = root, * parent = 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 0;
}
//找到待插入位置
cur = new Node(_kv);
cur->parent = parent;
if (parent->kv.first < _kv.first)
parent->right = cur;
else
parent->left = cur;
while (parent)
{
//修改平衡因子,循环向上遍历修改
if (parent->left == cur)
parent->bf--;
else
parent->bf++;
if (parent->bf == 0)
break;
else if (abs(parent->bf) == 1)
{
cur = parent;
parent = parent->parent;
}
else if (parent->bf == 2)
{
if (cur->bf == 1)
RotateL(parent);
else if (cur->bf == -1)
RotateRL(parent);
break;
}
else if (parent->bf == -2)
{
if (cur->bf == 1)
RotateLR(parent);
else if (cur->bf == -1)
RotateR(parent);
break;
}
else
{
assert(false);
}
}
return 1;
}
void RotateL(Node* parent) //左旋
{
Node* subR = parent->right, * subRL = subR->left;
parent->right = subRL;
if(subRL) //可能不存在，需要判断
subRL->parent = parent;
subR->left = parent;
if (root == parent)
{
subR->parent = nullptr;
root = subR;
}
else
{
Node* P_parent = parent->parent;
if (P_parent->left == parent)
P_parent->left = subR;
else
P_parent->right = subR;
subR->parent = P_parent;
}
parent->parent = subR;
parent->bf = subR->bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->left, * subLR = subL->right;
parent->left = subLR;
if (subLR) //可能不存在，需要判断
subLR->parent = parent;
subL->right = parent;
if (root == parent)
{
subL->parent = nullptr;
root = subL;
}
else
{
Node* P_parent = parent->parent;
if (P_parent->left == parent)
P_parent->left = subL;
else
P_parent->right = subL;
subL->parent = P_parent;
}
parent->parent = subL;
parent->bf = subL->bf = 0;
}
void RotateRL(Node* parent)
{
Node* subR = parent->right, * subRL = subR->left;
short _bf = subRL->bf;
RotateR(parent->right);
RotateL(parent);
if (_bf == 0)
{ //subRL 自己就是新增节点,此时parent节点下的子树只有parent，subR，subRL这三个节点
subR->bf = parent->bf = subRL->bf = 0;
}
else if (_bf == 1) //subRL右子树新增节点
{
subR->bf = subRL->bf = 0;
parent->bf = -1;
}
else if (_bf == -1)
{
subR->bf = 1;
subRL->bf = parent->bf = 0;
}
else
{
assert(false);
}
}
void RotateLR(Node* parent)
{
Node* subL = parent->left, * subLR = subL->right;
short _bf = subLR->bf;
RotateL(parent->left);
RotateR(parent);
if (_bf == 0)
{ //subRL 自己就是新增节点,此时parent节点下的子树只有parent，subR，subRL这三个节点
subL->bf = parent->bf = subLR->bf = 0;
}
else if (_bf == 1) //subRL右子树新增节点
{
subL->bf = -1;
subLR->bf = parent->bf = 0;
}
else if (_bf == -1)
{
subL->bf = subLR->bf = 0;
parent->bf = 1;
}
else
{
assert(false);
}
}
void _InOrder(Node* root)
{
if (!root)
return;
_InOrder(root->left);
cout << root->kv.first << " " << root->kv.second << endl;
_InOrder(root->right);
}
void Inorder()
{
_InOrder(root);
}
int _Height(Node* root)
{
if (!root) return 0;
int left = _Height(root->left);
int right = _Height(root->right);
return (left > right ? left : right) + 1;
}
const string str = "平衡因子异常";
bool _Is_Balance(Node* root)
{
if (!root) return 1;
int left_height = _Height(root->left);
int right_height = _Height(root->right);
/*try
{*/
if (right_height - left_height != root->bf)
{
cerr << str << endl;
}
/*}*/
/*catch (string e)
{
cerr << str << endl;
assert(false);
}*/
return abs(right_height - left_height) < 2 && _Is_Balance(root->left) && _Is_Balance(root->right);
}
void Is_Balance()
{
_Is_Balance(root);
}
void Destory(Node* root)
{
if (!root) return;
Destory(root->left);
Destory(root->right);
delete root;
}
};
int main()
{
const int N = 100000,NN=1000000;
srand(time(0));
int a;
AVLTree
for (int i = 0; i < N; i++)
{
a = rand()%NN;
AVL.Insert(make_pair(a,a));
}
AVL.Inorder();
AVL.Is_Balance();
}