AVL树
AVL树
普通的二叉搜索树的退化
在使用二叉搜索树时，只规定了左子树的值小于根节点的值，右子树的值大于根节点的值，并没有对树的形状做出要求。
在树较为平衡（左右子树高度相差较小）时，如下图所示：
我们在二叉搜索树上进行的增加、删除、查找的操作的时间复杂度平均为。
但是在树比较倾斜时，在二叉搜索树上的操作的时间复杂度也会随之增加，树越倾斜，退化也就越严重，时间复杂度也就越高。
一种极端情况下，当所有的节点（除叶节点外）都只有一个子树或子节点时，该树结构会退化为链表，相应的时间复杂度也会退化为。
为了解决这个问题，平衡树也就应运而生。其中最早的平衡树便是本文的重点——AVL树。
什么是AVL树
AVL树是最早被发明的自平衡二叉搜索树。它的名字不是自平衡二叉搜索树的缩写，而是来源于它的发明者G. M. Adelson-Velsky和Evgenii Landis。
AVL树在二叉搜索树的性质上增加了一条——任一节点的两个子树高度差最大为1。因此，AVL树在执行增加、删除、查找操作的时间复杂度在平均、最坏情况下均为。不会出现二叉搜索树中退化的情况。
平衡因子
AVL树中使用这个参数来判定当前节点是否是平衡的。平衡因子由当前节点的左子树高度减去右子树高度得到。
所以当一个节点的平衡因子大于1或小于-1时，则可以判定当前节点不平衡，需要进行调整。
另外，AVL树中也可以不保存节点的平衡因子，而保存树的高度，在需要时计算得到。
旋转
旋转是一种改变树的平衡性的操作，几乎所有的平衡树都是通过旋转操作来调整树的结构，使树保持平衡状态。
旋转分为两类：
- 左旋转
- 右旋转
左旋转
总共3步：
- 将根节点的右子节点设置为右子节点的左子节点。
- 将右子节点的左子节点设置为根节点。
- 将右子节点设置为根节点。
相应的代码为：
AVLTreeNode* RotateL(AVLTreeNode* root) {
AVLTreeNode* temp = root->right;
root->right = temp->left;
temp->left = root;
return temp;
}
旋转前后对比：
从图中可以看出，左旋转之后，相比于原来的树，左子树高度增加了1，右子树高度减少了1。
右旋转
类似于左旋转，也为三步：
- 将根节点的左子节点设置为左子节点的右子节点。
- 将左子节点的右子节点设置为根节点。
- 将左子节点设置为根节点。
相应的代码为：
AVLTreeNode* RotateR(AVLTreeNode* root) {
AVLTreeNode* temp = root->left;
root->left = temp->right;
temp->right = root;
return temp;
}
旋转前后对比：
从图中可以看出，右旋转之后，相比于原来的树，右子树高度增加了1，左子树高度减少了1。
AVL树中不平衡情况及对应旋转操作
在操作AVL树过程中，总共会遇到4种不平衡的情况：LL、RR、LR、RL。
LL情况——右旋转
LL情况是指根节点的左子节点的左子树高度比右子树高度大2的情况。即：
图中A节点为根节点。
进行一次右旋转即可使树重新平衡。
RR情况——左旋转
RR情况是指根节点的右子节点的右子树高度比左子树高度大2的情况。即：
图中A节点为根节点。
进行一次左旋转即可使树重新平衡。
LR情况——先左旋转，再右旋转
LR情况是指根节点的左子节点的右子树比左子树高度大2的情况。即：
图中A节点为根节点。
此时需进行两次旋转：
- 先以左子节点（
B）为根进行一次左旋转。（将情况转化为LL情况） - 再以
A节点为根进行一次右旋转。
RL情况——先右旋转，再左旋转
RL情况是指根节点的右子节点的左子树比右子树高度大2的情况。即：
图中A节点为根节点。
此时需进行两次旋转：
- 先以右子节点（
B）为根进行一次右旋转。（将情况转化为RR情况） - 再以
A节点为根进行一次左旋转。
AVL树的操作
在AVL树上操作主要有三种：增加、删除、查找。
三种操作与二叉搜索树上对应的三种操作基本相同，只是增加、删除操作有可能会引起树的不平衡，需要进行额外调整。
为便于说明，此处先对AVL树结构进行说明：
class AVLTree {
private:
class AVLTreeNode {
public:
int val; /// 当前节点所存的数值
int height; /// 当前节点的高度
AVLTreeNode* left; /// 左子树
AVLTreeNode* right; /// 右子树
// 得到root节点的高度
static int Height(AVLTreeNode* root);
AVLTreeNode(int val = 0);
~AVLTreeNode();
};
// 内部树结构
AVLTreeNode* root;
// 计算root节点的高度
void CalcHeight(AVLTreeNode* root);
// 取得以root为根的树上的最大值节点
AVLTreeNode* FindMax(AVLTreeNode* root);
// 取得以root为根的树上的最小值节点
AVLTreeNode* FindMin(AVLTreeNode* root);
// LL情况，以root为根进行右旋转
AVLTreeNode* RotateLL(AVLTreeNode* root);
// LR情况，先以root节点左儿子为根进行左旋转，再以root为根进行右旋转
AVLTreeNode* RotateLR(AVLTreeNode* root);
// RR情况，以root为根进行左旋转
AVLTreeNode* RotateRR(AVLTreeNode* root);
// RL情况，先以root节点右儿子为根进行右旋转，再以root为根进行左旋转
AVLTreeNode* RotateRL(AVLTreeNode* root);
// 向AVL树内插入值为val的一个节点，返回插入该节点后，整个树的根节点
// result返回插入结果，成功插入则返回1，如果该值已经存在则返回0
AVLTreeNode* Insert(AVLTreeNode* root, int val, int& result);
// 在AVL树中删除值为val的节点，如果不存在则跳过，返回删除该节点后，整个树的根节点
// result返回删除结果，成功删除则返回1，如果该值不存在则返回0
AVLTreeNode* Remove(AVLTreeNode* root, int val, int& result);
// 在AVLTree销毁时，递归释放整颗树
void DeleteRoot(AVLTreeNode* root);
// 中序遍历整颗树
void Print(AVLTreeNode* root);
public:
AVLTree();
~AVLTree();
// 向AVL树内插入值为val的一个节点，若成功插入则返回1，若已存在些节点则返回0
int Insert(int val);
// 在AVL树中删除值为val的节点，若成功删除则返回1，若该节点不存在则返回0
int Remove(int val);
// 在AVL树中查找值为val的节点，该节点存在则返回1，否则返回0
int Find(int val);
// 中序遍历整颗树
void Print();
};
其中两个辅助函数具体实现为：
int AVLTree::AVLTreeNode::Height(AVLTreeNode* root) {
// 返回当前节点的高度，若为空则返回-1
return root ? root->height : -1;
}
void AVLTree::CalcHeight(AVLTreeNode* root) {
// 当前节点的高度为左、右子树最高者高度 + 1
root->height = std::max(AVLTree::AVLTreeNode::Height(root->left),
AVLTree::AVLTreeNode::Height(root->right)) +
1;
}
插入
主要分4步：
- 寻找到插入的位置。（如果值已经存在则插入失败）
- 创建节点并插入。
- 如果插入操作引起了不平衡，进行调整。
- 回溯时计算出沿插入路径上所有节点的新高度。
插入操作函数为：
AVLTree::AVLTreeNode* AVLTree::Insert(AVLTreeNode* root, int val, int& result) {
result = 0;
// 如果当前节点为空，则返回一个新建的节点
if (!root) {
root = new AVLTreeNode(val);
result = 1;
return root;
}
// 当前节点值比要插入的值大，则应向左子树进行插入
if (root->val > val) {
// 向左子树插入值为val的节点
root->left = Insert(root->left, val, result);
// 如果在向左子树插入节点后，引起了树的不平衡（即左子树比右子树高2个单位），则需进行旋转调整
// 因为是向左子树插入，所以左子树的高度必定大于等于右子树的高度
if (AVLTreeNode::Height(root->left) -
AVLTreeNode::Height(root->right) ==
2) {
// 如果是插入的左子节点的左子树，则对应LL情况，只需进行右单旋转即可
if (val < root->left->val) root = RotateLL(root);
// 否则为LR情况，需进行两次旋转
else
root = RotateLR(root);
}
}
// 当前节点值比要插入的值小，则应向右子树进行插入
else if (val > root->val) {
// 向左子树插入值为val的节点
root->right = Insert(root->right, val, result);
// 如果在向右子树插入节点后，引起了树的不平衡（即右子树比左子树高2个单位），则需进行旋转调整
// 因为是向右子树插入，所以右子树的高度必定大于等于左子树的高度
if (AVLTreeNode::Height(root->right) -
AVLTreeNode::Height(root->left) ==
2) {
// 如果是插入的右子树的右子树，则对应RR情况，只需进行左单旋转即可
if (val > root->right->val) root = RotateRR(root);
// 否则为RL情况，需进行两次旋转
else
root = RotateRL(root);
}
}
// 回溯时计算出沿插入路径上所有节点的新高度
CalcHeight(root);
return root;
}
由于高度是通过回溯进行更新的，所以当插入完成后，以root为根的左右子树的高度均以更新完成，只需要用左右子树新的高度差即可判断出是否不平衡。
如果不平衡，通过插入值val与root节点值的相对大小即可判断出相应的不平衡的类型。进行对应的操作即可。
删除
与插入类似，也分为4步：
- 寻找到要删除的节点的位置。（如果值不存在则删除失败）
- 如果对应节点只有一个子节点，直接删除；若有两个子节点，则需找出对应的替代节点之后，再进行删除。
- 如果删除操作引起了不平衡，进行调整。
- 回溯时计算出沿删除路径上所有节点的新高度。
具体实现如下：
AVLTree::AVLTreeNode* AVLTree::Remove(AVLTreeNode* root, int val, int& result) {
result = 0;
if (!root) {
return nullptr;
}
// 待删除节点位于右子树
if (root->val < val) {
// 在右子树中删除节点
root->right = Remove(root->right, val, result);
// 如果删除后引起了树的不平衡（即左子树的高度与右子树的高度差为2），则需要进行旋转调整
if (AVLTreeNode::Height(root->left) -
AVLTreeNode::Height(root->right) ==
2) {
// 如果右儿子的左子树的高度小于右儿子的右子树的高度，
// 则删除的节点位于右儿子的左子树上，不平衡情况对应RR，
// 进行左旋转即可
if (AVLTreeNode::Height(root->right->left) <
AVLTreeNode::Height(root->right->right))
root = RotateRR(root);
// 否则删除的节点位于右儿子的右子树上，不平衡情况对应RL，
// 需进行两次旋转
else
root = RotateRL(root);
}
}
// 待删除节点位于左子树
else if (root->val > val) {
// 在左子树中删除节点
root->left = Remove(root->left, val, result);
// 如果删除后引起了树的不平衡（即右子树的高度与左子树的高度差为2），则需要进行旋转调整
if (AVLTreeNode::Height(root->right) -
AVLTreeNode::Height(root->left) ==
2) {
// 如果左儿子的右子树的高度小于左儿子的左子树的高度，
// 则删除的节点位于左儿子的右子树上，不平衡情况对应LL，
// 进行右旋转即可
if (AVLTreeNode::Height(root->left->right) <
AVLTreeNode::Height(root->left->left))
root = RotateLL(root);
// 否则删除的节点位于左儿子的左子树上，不平衡情况对应LR，
// 需进行两次旋转
else
root = RotateLR(root);
}
}
// 否则应当删除当前节点
else {
result = 1;
int t;
// 当前节点有两个子节点，则从中选取高度大的一个子树进行替代，避免引起树的不平衡
if (root->left && root->right) {
// 左子树高度大于右子树时，选取左子树中最大值替代当前节点，并删除原最大值节点
if (AVLTreeNode::Height(root->left) >
AVLTreeNode::Height(root->right)) {
AVLTreeNode* temp = FindMax(root->left);
root->val = temp->val;
root->left = Remove(root->left, temp->val, t);
}
// 否则，选取右子树中最小值替代当前节点，并删除原最小值节点
else {
AVLTreeNode* temp = FindMin(root->right);
root->val = temp->val;
root->right = Remove(root->right, temp->val, t);
}
}
// 如果当前节点只有一个子节点或没有子节点，直接删除即可
else {
AVLTreeNode* temp = root;
root = root->left ? root->left : root->right;
delete temp;
}
}
// 如果返回节点不为空时，回溯地计算出删除路径上所有节点的新高度
if (root) CalcHeight(root);
return root;
}
其中两个辅助函数实现如下：
AVLTree::AVLTreeNode* AVLTree::FindMax(AVLTreeNode* root) {
if (!root) return nullptr;
AVLTreeNode* temp = root;
while (temp->right) temp = temp->right;
return temp;
}
AVLTree::AVLTreeNode* AVLTree::FindMin(AVLTreeNode* root) {
if (!root) return nullptr;
AVLTreeNode* temp = root;
while (temp->left) temp = temp->left;
return temp;
}
与插入类似，通过高度差判断是否不平衡，通过相对值大小判断具体不平衡类型。
查找
与二叉搜索树查找相同，不再赘述。
相同值的处理
上述结构仅支持序列中没有相同值的情况，如果存在一组有相同值的序列，并且想将相同的值都存储下来，则需要对此结构进行一些修改。
一种办法是在AVLTreeNode结构中添加一个indexs属性用于存储对应值在原序列中的位置，如果插入时值相同，则向indexs中添加对应的位置编号。
附注
文中完整代码请参考：https://github.com/anscor/BlogCode/tree/master/AVLTree
另附两个数据结构的可视化网站，在进行较为抽象的数据结构与算法学习时，可以用于直观地检验自己编写代码的正确性：