数据结构-AVL树（图解+全面分析平衡二叉树）
K _key;int _bf;,_key(key),_bf(0){}之所以使用三叉链结构，是因为AVL树的核心是通过平衡因子（BF）调整树的平衡性。当插入或删除节点时，需要沿着路径向上回溯到根节点，逐层更新祖先节点的平衡因子。通过_parent指针可以直接访问父节点，代码更简洁高效AVL树的旋转（左旋、右旋、双旋）需要调整父子节点的指向关系，涉及多个节点的指针修改。通过_parent指针，可以直接
一.AVL树的概念
二叉搜索树最然可以缩短查找效率，但如果数据有序或接近有序的话，二叉搜索树就会退化为单支树，查找元素相当于在顺序表中搜索元素一样，效率低下。因此，两位俄罗斯的数学家 G.M. Adelson-Velsky 和 E.M. Landis 发明的一种解决上述问题的方法：当二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1，就需要对树中的结点进行调整，就是降低树的高度，从而减少平均搜索长度。
AVL树的特征：
- 整棵树的每个结点的左右分支都是一颗AVL树
- 整棵树的所有结点的左右子树的高度之差（平衡因子balance factor）的绝对值不超过1(-1,0,1)
当一颗二叉搜索树高度平衡时，他就是AVL树，如果共有n个结点，它的高度就可以保持在log2N，搜索的时间复杂度就是O(log2N)。
二.AVL树的定义：
template<class K>
struct AVLTreeNode
{
AVLTreeNode<K>* _parent;
AVLTreeNode<K>* _left;
AVLTreeNode<K>* _right;
K _key;
int _bf;
AVLTreeNode(const K& key)
:_parent(nullptr)
,_left(nullptr)
,_right(nullptr)
,_key(key)
,_bf(0)
{}
};之所以使用三叉链结构，是因为
- AVL树的核心是通过平衡因子（BF）调整树的平衡性。当插入或删除节点时，需要沿着路径向上回溯到根节点，逐层更新祖先节点的平衡因子。通过_parent指针可以直接访问父节点，代码更简洁高效
- AVL树的旋转（左旋、右旋、双旋）需要调整父子节点的指向关系，涉及多个节点的指针修改。通过
_parent指针，可以直接修改父节点对子节点的引用，无需从根节点重新定位父节点，减少指针操作的复杂度。
三.AVL树的插入
AVL树就是在二叉搜索树得基础上引入平衡因子，因此AVL树也可以看成二叉搜索树。因此，AVL树的插入过程可以分为两步：
- 按照二叉搜索树的方式插入新结点
- 插入结点的同时，调节平衡因子，保证平衡因子的绝对值小于2（也就是左右子树的高度差不超过1）
当一个新节点插入时，AVL树可能会遭到破坏，此时就需要更新平衡因子，之后监测平衡因子的值，判断新插入的结点是否破坏了AVL树的平衡性，从而选择是否需要旋转。
- 如果更新完以后，平衡没有出现问题（|bf| < 2)，平衡结构没有影响，不需要处理，继续插入即可
- 如果更新完后，平衡出现问题（|bf| >= 2)，平衡受到影响，需要处理(旋转)
插入新的结点，会影响祖先的平衡因子
if (parent->_right == cur)
{
parent->_bf++;
}
else if(parent->_left == cur)
{
parent->_bf--;
}更新完结点后，是否需要继续往上更新，取决于parent所在的子树的高度变化，变了继续更新，不变则不再更新。
- parent->_bf == 1 || parent->_bf == -1 更新结束后父结点是这样的值，证明在更新前左右子树的高度相同，现在新增一个结点，说明高度一边高一边低，这时就需要向上更新。
- parent->_bf == 0 更新结束后父结点是这样的值，证明更新前左右子树一边高一边低，这时插入的结点弥补了低的那一边，这样树的高度没有发生变化，这样就不需要往上继续更新。
- parent->_bf == 2 || parent->_bf == -2 更新结束后父结点是这样的值，就需要对这棵子树进行旋转处理
while (parent)
{
//新增结点后，对父结点的平衡因子进行更新。
if (parent->_right == cur)
{
parent->_bf++;
}
else if (parent->_left == cur)
{
parent->_bf--;
}
if (parent->_bf == 1 || parent->_bf == -1)
{
//继续往上更新
parent = parent->_parent;
cur = cur->_parent;
}
else if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//旋转处理
}
else
{
assert(false);
}
}AVL树的旋转
如果在一棵树原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据结点插入的位置不同，AVL树的旋转分为四种：（红色方块代表新增结点，h代表子树的高度）
-
新结点插入较高的右子树的右侧：进行左单旋
将对于一颗树所有左单旋的情况用抽象图（树中的子树除外）表示为：
当子树高度为0时(h = 0)
当子树高度为1时(h = 1)
当子树的高度为2时(h = 2)
对于h这颗子树来讲，h=2的时候总共有三种情况
这样根据简单运算一下，总共可能的情况就会有3*3*3 = 27种，但是这里是需要左旋，这就表示c必须是图3这种情况，而a和b可以是上面三种图像中的任意一种。所以总共有3*3*1=9种，
这时候就有人好奇了c为什么就不能是图1和图2呢，我们来试一试就知道了：
用上图2就会出现这两种情况，图a的情况不会发生旋转，平衡因子都小于2，而图b明显可以看到这种左旋就成为了这颗树的子树的左旋，而我们现在讨论的是这一整棵树的左旋。所以要进行整棵树的左旋，c必须是上面图3那种情况，否则就是不旋转或者就是进入到子树进行旋转。
因此，只要新增的结点是4个红色结点的其中之一，就可以对整棵树进行左旋。举其中一例：
可以明显看到，插入后新结点69导致以30为根的二叉树不平衡了，要想让30平衡，只能将30的右子树的高度减少一层，左子树增加一层，就是将右子树往上提，这样30就转下来了，因为30比60小，只能放在60的左子树，如果60有左子树，左子树的根一定大于30，小于60，只能放在30的右子树，旋转完成之后，更新平衡因子。
在旋转的过程中，还需要考虑：
- 60的左子树可能存在，也可能不存在(存在需要进行维护它的结点指针，比如旋转后更新60左子树的父结点)
- 30可能是根节点，也可能是子树，如果是根节点，旋转完成之后，就要更新根节点；如果是子树，则可能是某一个结点的左子树，也有可能是右子树。，就需要将其与祖先相连
左旋的实现：
void RatateL(Node* parent)
{
//subR是parent的右孩子
Node* subR = parent->_right;
//subRL是subR的左孩子
Node* subRL = subR->_left;
//旋转完成之后，60的左孩子做30的右孩子
parent->_right = subRL;
//如果60的左孩子存在，就要更新它的父节点，让它的父结点指向30
if (subRL)
{
subRL->_parent = parent;
}
//记录30的父结点，因为30也可能是子树
Node* ppnode = parent->_parent;
//将30连接到60的左子树
subR->_left = parent;
//更新30的父结点
parent->_parent = subR;
//如果30是根节点，将60作为新的根节点
if (ppnode == nullptr)
{
subR->_parent = nullptr;
_root = subR;
}
else
{
//如果30是子树，可能是左子树，也可能是右子树
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
//更新平衡因子
parent->_bf = subR->_bf = 0;
}
-
新节点插入较高的左子树的左侧：进行右单旋
当h = 0时
当h = 1时
当h = 2时
同样a位置只能是图3，而b和c可以是图中任意一种，这样就满足了右旋的特征，所有可能的情况有：
为什么a只能是图3，和左旋一样
要么就是不旋转，要么就是成为了分支的右旋
上面所有的情况和这幅图一样，只要是插入的是图中4个结点中的一个，都会造成右旋，举例：
在旋转的过程中，同样需要考虑30的右子树存在与否
还有就是60可能是根节点，也可能是左子树，也可能是右子树
右旋的实现：
void RatateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* ppnode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (ppnode == nullptr)
{
subL->_parent = nullptr;
_root = subL;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
parent->_bf = subL->_bf = 0;
}-
新节点插入较高左子树的右侧：先进行左旋，在进行右旋
当h>=1时
将双旋变成单旋后再旋转，就是先对30进行左单旋，然后再对90进行右单旋，旋转完成之后再考虑平衡因子的更新
当h<1时
当h = 1时
当h = 2时 所有可能的情况：
同样，上面所有情况和下面这幅图一样的4个红色节点位置，只要在这4个结点其中之一插入，就可以触发左右旋转。
实例：
到这，就有好奇的人问了，右旋的parent的平衡因子和这里左右旋的平衡因子都是-2，我要是偏偏就想直接右旋，会发生什么？
现在试试左右选直接右旋会发生什么？
可以看到直接右旋的话，依旧没有效果，平衡因子大于1，所以不可以直接右旋，必须先对30左旋，再对90右旋，这样才能达到平衡的。
左右旋的实现
void RatateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
RatateL(subL);
RatateR(parent);
if (subLR->_bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (subLR->_bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (subLR->_bf == 0)
{
parent->_bf = subL->_bf = subLR->_bf = 0;
}
else
{
assert(false);
}
}左右旋的实现并不难，只要会了左旋和右旋，左右旋就可以了，左右旋唯一的难点是平衡因子的控制，更新完成之后如何控制平衡因子，是一大问题？------
仔细观察图中可以发现我们可以通过判断subL的右子树（记为subLR）的平衡因子进行判断，用通俗的话来讲左右旋就是，将subLR的左孩子给了subL，将subLR的右孩子给了parent，然后subLR做subL和parent的父结点，因此：
- 当subLR的平衡因子为0时，证明subLR是新增结点，可以明显看到，旋转之后parent，subL，subLR三者的平衡因子都是0。
- 当subLR的平衡因子为1时，证明新增结点在subLR的右边， 这样给了parent，parent就平衡了，而subL就会左边高，他的平衡因子就是-1，parent和subLR就平衡了，平衡因子为0.
- 当subLR的平衡因子为-1时，证明新增结点在subLR的左边， 这样给了subL，subL就平衡了，而parent就会右边高，他的平衡因子就是1，subL和subLR就平衡了，平衡因子为0.
-
新结点插入右子树的左侧：先进行右旋，在进行左旋
当h>=1时
也是将双旋变为单旋后在旋转，就是对90进行右旋，再对30进行左旋，旋转完成之后再进行平衡因子的更新。
当h < 0时
当h = 1时
当h = 2 时，所有可能的情况：
同样，上面所有情况与下面这幅图相同，只要插入这4个红色结点的其中之一 ，就会造成右左旋
实例：
如果直接左旋就会出现：
依旧无法解决问题，所以只能先对60进行右旋，在对30进行左旋，这样才能达到平衡。
右左旋的实现
void RatateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
RatateR(subR);
RatateL(parent);
if (subRL->_bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (subRL->_bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (subRL->_bf == 0)
{
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else
{
assert(false);
}
}平衡因子的判断
仔细观察图中可以发现我们可以通过判断subR的左子树（记为subRL）的平衡因子进行判断，用通俗的话来讲左右旋就是，将subRL的右孩子给了subR，将subRL的左孩子给了parent，然后subRL做subR和parent的父结点，因此：
- 当subRL的平衡因子为0时，证明subRL是新增结点，可以明显看到，旋转之后parent，subR，subRL三者的平衡因子都是0。
- 当subRL的平衡因子为-1时，证明新增结点在subRL的左边， 这样给了parent，parent就平衡了，而subR就会右边高，他的平衡因子就是1，parent和subRL就平衡了，平衡因子为0.
- 当subRL的平衡因子为1时，证明新增结点在subRL的右边， 这样给了subR，subR就平衡了，而parent就会左边高，他的平衡因子就是-1，subR和subRL就平衡了，平衡因子为0.
总结所有的情况
这就是4种旋转所有的情况，上面介绍的右左旋转和左右旋转，是为了让大家看清楚是如何旋转的，属于微观角度，现在这幅图就属于宏观情况了，所有新增结点（红色方块）上方的h=2时，都必须是图3那种情况，不然就会成为子树的旋转问题或者不旋转，这就是针对一颗树所有的旋转方式。接下来进行验证我们的成果的时刻。
四.AVL树的验证
像我第一次学习AVL树时，看到有序就觉得大功告成了，AVL树实现成功了，但是转念一想，真的是这样吗？不对呀，二叉搜索树中序遍历一下也是有序的，所以，我得进行进一步的验证。
AVL树是在二叉搜索树的基础上加入了平衡性的限制，所以单单进行中序遍历等到一个有序的序列，只能证明它时二叉搜索树，不能证明他是AVL树，所以就要进一步进行验证：每一个平衡因子的绝对值不能超过1，这样才能算AVL树。所以通过实现一个Is_balance函数，进行对每一个结点进行检测，看看是否左右子树的高度差为1.
int _Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int left = _Height(root->_left);
int right = _Height(root->_right);
return left > right ? left + 1 : right + 1;
}
bool Is_balance(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
return abs(leftH - rightH) < 2 && Is_balance(root->_left) && Is_balance(root->_right);
}五.AVL树的性能
AVL树是一颗绝对平衡的二叉搜索树，其每一个节点的左右子树的高度差的绝对值不超过1，这样就能保证时间复杂度为O(log2N)，但是插入时需要维护绝对平衡，旋转的次数也比较多，所以绝对平衡虽然查询很高效，但是在插入的时候也就比较痛苦了，这样插入的效率就比较低了。因此，如果需要一种查询高效，有序且是不轻易改变数据的数据结构时，AVL树就可以首选。
AVL树的完整实现代码：
#include<iostream>
#include<assert.h>
using namespace std;
template<class K>
struct AVLTreeNode
{
AVLTreeNode<K>* _parent;
AVLTreeNode<K>* _left;
AVLTreeNode<K>* _right;
K _key;
int _bf;
AVLTreeNode(const K& key)
:_parent(nullptr)
,_left(nullptr)
,_right(nullptr)
,_key(key)
,_bf(0)
{}
};
template<class K>
class AVLTree
{
typedef AVLTreeNode<K> Node;
public:
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
while (parent)
{
if (parent->_right == cur)
{
parent->_bf++;
}
else if(parent->_left == cur)
{
parent->_bf--;
}
if (parent->_bf == 1 || parent->_bf == -1)
{
parent = parent->_parent;
cur = cur->_parent;
}
else if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
if (parent->_bf == 2 && cur->_bf == 1)
{
RatateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RatateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RatateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
RatateLR(parent);
}
break;
}
else
{
assert(false);
}
}
return true;
}
void Inorder()
{
_Inorder(_root);
cout << endl;
}
bool IsBlance()
{
return Is_balance(_root);
}
private:
void RatateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
Node* ppnode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (ppnode == nullptr)
{
subR->_parent = nullptr;
_root = subR;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
parent->_bf = subR->_bf = 0;
}
void RatateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* ppnode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (ppnode == nullptr)
{
subL->_parent = nullptr;
_root = subL;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
parent->_bf = subL->_bf = 0;
}
void RatateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
RatateR(subR);
RatateL(parent);
if (subRL->_bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (subRL->_bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (subRL->_bf == 0)
{
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else
{
assert(false);
}
}
void RatateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
RatateL(subL);
RatateR(parent);
if (subLR->_bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (subLR->_bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (subLR->_bf == 0)
{
parent->_bf = subL->_bf = subLR->_bf = 0;
}
else
{
assert(false);
}
}
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_key << " ";
_Inorder(root->_right);
}
int _Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int left = _Height(root->_left);
int right = _Height(root->_right);
return left > right ? left + 1 : right + 1;
}
bool Is_balance(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
return abs(leftH - rightH) < 2 && Is_balance(root->_left) && Is_balance(root->_right);
}
private:
Node* _root = nullptr;
};
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
21
0- 0
已为社区贡献1条内容
所有评论(0)