目录
原理
平衡因子
AVL树的插入insert
1. 新节点插入较高左子树的左侧---左左：右单旋
2.新节点插入较高右子树的右侧---右右：左单旋
新节点插入较高左子树的右侧---左右：先左单旋再右单旋
新节点插入较高右子树的左侧---右左：先右单旋再左单旋编辑
原理
AVL 树是一种平衡搜索二叉树，得名于其发明者的名字（ Adelson-Velskii 以及 Landis）。（可见名字长的好处，命名都能多占一个字母出来）。在搜索树的前提下平衡搜索二叉树还定义如下：
- 左右子树的高度差小于等于 1。
- 其每一个子树均为平衡二叉树。
我们以SGI版本AVL树
先来查看树中每个结点内容。
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode* _left;//左子树
AVLTreeNode* _right;//右子树
AVLTreeNode* _parent;//父节点
pair<K, V> _kv;//数据存储内容
int _bf;//平衡因子
AVLTreeNode(pair<K, V>kv=pair<K, V>())//默认赋值构造
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
,_bf(0)
{}
};左子树与右子树指针我们不做过多介绍。
我们存储AVL树是一种存储key_value数据的树，所以我们使用pair库中类型存储数据。
让我们看看平衡因子是什么：
平衡因子
某个结点的右子树的高度减去左子树的高度得到的差值。
平衡因子在[-1,1]之间都是属于平衡的平衡搜索二叉树，每个结点都需要符合这个要求
在插入的过程中我们会破坏平衡，这个时候就需要对树结点进行转至操作。
AVL树的插入insert
和普通搜索二叉树一样，先要寻找插入的位置。
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
}
else
{
Node* parent = nullptr;//保存上级指针，我们链接都是cur走到空指针创建结点给cur
//但是这个新的结点需要被链接到树中，我们不可以对
//nullptr进行访问上级的数据，所以我们必须留一个parent
//用来链接新的结点。
Node* cur = _root;
while (cur)
{
parent = cur;
if (cur->_kv.first > kv.first)
{
cur = cur->_left;//新数据小于当前数据，向cur的左边走
}
else if (cur->_kv.first < kv.first)
{
cur = cur->_right;//新数据大于当前数据，向cur的右边走
}
else
{
return false;//数据相同退出，并返回false
}
}
cur = new Node(kv);//cur到了nullptr，创建新的结点。
//新结点链接到树
if (parent->_kv.first <cur->_kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;//处理新结点的_parent插入结点后我们需要修改平衡因子，确保插入数据后我们的树依旧是AVL树。
更新平衡因子规则:
- 新增在右，parent->bf+ +;新增在左，parent->bf--;
- 更新后，parent->bf == 1 or -1，说明parent插入前的平衡因子是0，说明左右子树高度相等，插入后有一边高，parent高度变了，该节点插入稍稍改变平衡，需要继续往上更新平衡因子。
- 重新后，parent->bf == 0说parent插入前的平衡因子是1 or -1，说明左右子树一边高一边低，插入后两边一样高，插入填上了矮了那边，parent所在子树高度不变，不需要继续往上更新
- 更新后，parent->bf == 2 or -2，说明parent插入前的平衡因子是1 or -1，已经平衡临界值，插入变成2 or -2，打破平衡，parent所在子树需要旋转处理
- 更新后，parent->bf > 2 r< -2的值，不可能，如果存在，则说明插入前就不是AVL树，需要去检查之前操作的问题，不需要再去考虑现在代码的问题了。
while (parent)
{
if (parent->_right == cur)//根结点(praent)的右子树(cur)插入了一个结点当前根结点平衡因子++
{
++parent->_bf;
}
else /*if() 可以不写这个*///根结点(praent)的左子树(cur)插入了一个结点当前根结点平衡因子--
{
--parent->_bf;
}
if (parent->_bf == 0)//修改更新平衡因子后，查看当前平衡因子，为0代表根补齐了该根的低子树
//parent所在子树高度不变，不需要继续往上更新
{
break;
}
else if (abs(parent->_bf) == 1)//parent原本为0的平衡因子被改变，高度变高了，parent左右被
//该节点插入稍稍改变平衡，需要继续往上更新平衡因子。
{
cur = parent;
parent = parent->_parent;
}
else if (abs(parent->_bf) == 2)//说明parent插入前的平衡因子是1 or -1，已经平衡临界值，插
//入变成2 or -2，打破平衡，parent所在子树需要旋转处理
{
//平衡被破坏。
}
else
{
std::cout << "AVL fail\n";
assert(false);
}
} 这既是转至：
但是不平衡的情况有无数种。
我们向大佬学习，得出4个旋转大规律：
1. 新节点插入较高左子树的左侧---左左：右单旋
h为子树高度。
当cur->bf==-1&&parent==-2是发生右单旋。
左左的意思是插入数据在parent的左子树的左子树上。
右单旋：以60结点为中心，向右旋转AVL树，允许h=0；
观察图像，我们发现就是改变链接关系，
这里有2个小细节点，
- b允许为空，所以b的parent操作前需要判断b是否为nullptr
- 如果60就是整棵AVL树的根就需要改变root指向30，并且将30的parent置空
在旋转结束以后将cur与parent结点的bf置为0
完整代码：
void RotateR(Node* parent)
{
Node* subL = parent->_right;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* pparent = parent->_parent;
parent->_parent = subL;
subL->_right = parent;
if (_root == parent)
{
_root = subL;
subL->_parent == nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->_parent = pparent;
}
subL->_bf = 0;
parent->_bf = 0;
}2.新节点插入较高右子树的右侧---右右：左单旋
原理与右单旋一样。
查看代码
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
Node* pparent = parent->_parent;
parent->_parent = subR;
subR->_left = parent;
if (_root == parent)
{
_root = subR;
subR->_parent == nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
subR->_bf = 0;
parent->_bf = 0;
}新节点插入较高左子树的右侧---左右：先左单旋再右单旋
什么意思呢？就是插入到了parent->left->right子树上
如果这样的情况只用右单旋。会发生什么呢？
该破坏平衡依旧破坏平衡，用左旋就是I变2一样的。
所以这时候我们需要左右旋一起用。
我们将30结点的右子树再一次拆分->40根结点+左右子树。
我们需要先以30结点左旋该子树。
在根据60结点做右旋旋转，我们把40的左子树看成一个整体
然后重新定义40、60、30的平衡因子。
这里我们定义平衡因子又有讲究，我们要观察插入后旋转前40结点的平衡因子。
三种情况：
旋转前40->bf==1时，在旋转完毕后30->bf=-1、60->bf=0、40->bf=0；
旋转前40->bf==-1时，在旋转完毕后30->bf=0、60->bf=1、40->bf=0；
还有一种特殊的情况40->bf==0;30->bf=0、60->bf=0、40->bf=0；
左右旋代码代码：
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
subLR->_bf = 0;
if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
}
else if (bf==-1)
{
parent->_bf = 1;
subL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
}
else
{
assert(false);
}
}新节点插入较高右子树的左侧---右左：先右单旋再左单旋
重新赋值bf与左右：先左单旋再右单旋规则一样
旋转前40->bf==-1时，在旋转完毕后30->bf=0、30->bf=1、40->bf=0；
旋转前40->bf==1时，在旋转完毕后30->bf=-1、30->bf=0、40->bf=0；
旋转前40->bf==0时，在旋转完毕后30->bf=-1、30->bf=0、40->bf=0
右左旋代码：
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL=subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
subRL->_bf = 0;
if (bf == 1)
{
parent = -1;
subR = 0;
}
else if(bf==-1)
{
parent = 0;
subR = 1;
}
else if (bf == 0)
{
parent = 0;
subR = 0;
}
else
{
assert(0);
}
}AVLinsert完整代码：文章来源：https://www.toymoban.com/news/detail-491502.html
template<class K, class V>
struct AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
}
else
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (cur->_kv.first > kv.first)
{
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first <cur->_kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
while (parent)
{
if (parent->_right == cur)
{
++parent->_bf;
}
else
{
--parent->_bf;
}
if (parent->_bf == 0)
{
break;
}
else if (abs(parent->_bf) == 1)
{
cur = parent;
parent = parent->_parent;
}
else if (abs(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)
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
break;
}
else
{
std::cout << "AVL fail\n";
assert(false);
}
}
return true;
}
}
private:
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
subLR->_bf = 0;
if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
}
else if (bf==-1)
{
parent->_bf = 1;
subL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
}
else
{
printf("bf is fail!!\n");
assert(false);
}
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL=subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
subRL->_bf = 0;
if (bf == 1)
{
parent = -1;
subR = 0;
}
else if(bf==-1)
{
parent = 0;
subR = 1;
}
else if (bf == 0)
{
parent = 0;
subR = 0;
}
else
{
printf("bf is fail!!\n");
assert(false);
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
Node* pparent = parent->_parent;
parent->_parent = subR;
subR->_left = parent;
if (_root == parent)
{
_root = subR;
subR->_parent == nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
subR->_bf = 0;
parent->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_right;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* pparent = parent->_parent;
parent->_parent = subL;
subL->_right = parent;
if (_root == parent)
{
_root = subL;
subL->_parent == nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->_parent = pparent;
}
subL->_bf = 0;
parent->_bf = 0;
}
Node* _root;
};
}谢谢！！文章来源地址https://www.toymoban.com/news/detail-491502.html
到了这里，关于AVL树原理以及插入代码讲解（插入操作画图~细节）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
