文章目录
?1.AVL树的概念
之前提到的二叉搜索树效率为logN，但是当插入节点有序的时候效率退化为O(N)，这可就很致命了。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树是具有以下特点的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
?2.AVL树实现思路
🎄结点的定义
因为涉及到了大量的平衡因子调节，所以需要保存父节点的指针，选择用三叉链的结构。
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K,V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0)
{}
AVLTreeNode<K, V>* _left;//该结点的左孩子
AVLTreeNode<K, V>* _right;//该结点的右孩子
AVLTreeNode<K, V>* _parent;//该结点的双亲
pair<K, V> _kv;
int _bf;//该结点的平衡因子
};
🎄AVL树的查找
AVL树的查找跟搜索树一样
1.若为空树，返回空
2.key值比当前结点的key值大就到右边找
3.key值比当前结点的key值大就到左边找
4.key值和当前结点的key值相等或者没找到返回false
Node* Find(const K& key)
{
//根据二叉搜索树的性质，从根节点出发，比根节点大则查找右子树，比根节点小则查找左子树
Node* cur = _root;
while (cur)
{
//比根节点大则查找右子树
if (key > cur->_kv.first)
{
cur = cur->_right;
}
//比根节点小则查找左子树
else if (key < cur->_kv.first)
{
cur = cur->_left;
}
//相同则返回
else
{
return cur;
}
}
//遍历完则说明查找不到，返回false
return nullptr;
}
🎄AVL树的平衡因子
**平衡因子，其实就是左右子树的高度差。AVL树通过控制高度差不超过1，来实现平衡。**当插入一个新的结点它祖先的平衡因子都会收到影响。
平衡因子的更新规则：
1.新增结点在parent的右边，平衡因子++
2.新增结点在parent的左边，平衡因子- -
例如：
右子树插入一个90，根节点平衡因子+1
每更新完一个结点的平衡因子后，都需要进行判断：
1.parent的平衡因子等于1或者-1则继续往上更新
2.parent的平衡因子等于0，则停止更新
3.parent的平衡因子等于2或者-2，说明已经不平衡了需要进行旋转处理
分析：
1.parent更新后的平衡因子为1或-1，则说明在parent的右边或者左边新增了结点，从而影响了parent的父亲结点所以要继续往上更新平衡因子。
2.parent更新后的平衡因子为0，1或-1经过++或- -变成0，说明新增结点在parent高的一侧使得parent的左右子树一样高，不会影响parent的父亲结点，就不用往上更新平衡因子。
3.parent更新后的平衡因子为2或-2，parent的左右子树差的绝对值大于1，已经不满足AVL树，需要旋转处理。
🎄AVL树的旋转(important!!!)
旋转分为四种情景，简单点总结的话就是如果节点呈直线则单旋，折线则双旋，下面一一分析。
📕右单旋
具象图：
具象图情况太多，上面就举一个例子便于理解，下面用抽象图概括：
需要注意的细节：
1.subLR可能为空
2.先把30的右给60的左，在让60整棵树左30的右子树。因为是三叉链实现的，所以还要注意修改动的结点的父亲结点
3.60可能是子树，也有可能是单独的树
右旋的步骤:
- 让不平衡的结点parent的左子树变为其原本左子树subL的右节点subLR
- 让parent变为subL的右子树
- 调整新的父节点subL与祖父节点的关系，并调整旋转后的平衡因子
//右旋
void RotateR(Node* parent)
{
//步骤1 让不平衡的结点parent的左子树变为其原本左子树subL的右节点subLR
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
//如果subLR存在，则让他的父节点指向parent。
if (subLR)
{
subLR->_parent = parent;
}
//步骤2 让parent变为subL的右子树
subL->_right = parent;
//步骤3 调整新的父节点subL与祖父节点的关系，并调整旋转后的平衡因子
Node* ppNode = parent->_parent;//保存原本的祖父节点
parent->_parent = subL;//更新parent的父节点
//两种情况
//如果parent为根节点，则让subL成为新的根节点
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
//如果不是根节点，则改变subL与其祖父节点的指向关系
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
//左旋完成后平衡，平衡因子归零。
subL->_bf = parent->_bf = 0;
}
📕左旋
左旋的思路和右旋一样，只是将顺序翻了过来。
当右边不平衡，并且节点呈直线时（右节点的右边偏重），说明需要左旋处理。
具象图
抽象图
左旋的步骤：
- 让不平衡的结点parent的右子树变为其原本右子树subR的左节点subRL
- 让parent变为subR的左子树
- 调整新的父节点subR与祖父节点的关系，并调整旋转后的平衡因子
//左旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
Node* ppNode = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
subR->_bf = parent->_bf = 0;
}
📕右左双旋
分类讨论
情况1：新增节点在C
情况2：新增节点在b
情况3：本身就是新增节点
右左双旋的步骤：
1.首先因为不平衡那个方向的子树的反方向偏重，呈折现状态，所以需要对其右旋转，让树恢复到直线状态
2.直线状态时就和一开始的单旋思路一样，按照单旋处理
3.调节平衡因子，根据subRL一开始的平衡因子进行调节，有两种情况，为-1时subR结束后为1，为1时parent结束后为-1。
总结上面的情况：需记录subRL的平衡因子，保存subR，subRL。根据subRL的平衡因子在更新其他需要更新的平衡因子
情况一：当subRL的平衡因子=1时，subR,subRL,parent的平衡因子分别是0，0，-1
情况二：当subRL的平衡因子=-1时，subR,subRL,parent的平衡因子分别是1，0，0
情况三：当subRL的平衡因子=0时，subR,subRL,parent的平衡因子的都是0
//右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//这里需要保存subRL的平衡因子，来调节旋转完后的平衡因子
int bf = subRL->_bf;
//先右单旋将折线结构转换为直线结构，也就是前面单旋就可以解决的问题。
RotateR(subR);
//然后再左单旋即可
RotateL(parent);
//根据subRL的bf来调节旋转后的平衡因子
if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
}
📕左右双旋
与右左类似，图片不再细化了，读者可以尝试自己画画。
总结平衡因子的变化：根据subLR的平衡因子在更新其他需要更新的平衡因子
1.当subLR的平衡因子=1时，subL,subLR,parent的平衡因子分别是-1,0.0;
2.当subLR的平衡因子=-1时，subL,subLRL,parent的平衡因子分别是0,0,1;
3.当subLR的平衡因子=0时，subL,subLR,parent的平衡因子的都是0
//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
}
🎄AVL树的插入
插入分为三个步骤
- 按照二叉搜索树的规则找到合适的位置插入
- 更新插入后的平衡因子
- 根据平衡因子来选择是否进行旋转调节。
有了前面旋转的基础，这里直接复用代码就行，具体步骤也写在注释里
bool insert(const pair<K, V>& kv)
{ //树为空，new一个新节点
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = cur;
while (cur)
{
if (cur->_kv.first > kv.first)//插入结点的key值小于当前结点，往左走
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)//插入结点的key值大于当前结点，往右走
{
parent = cur;
cur = cur->_right;
}
else
{
return false;//没有找到，返回false
}
}
//插入节点
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
//注意是三叉链，还要链接上parent
parent->_right = cur;
cur->_parent = parent;
}
else
{
//要链接上parent
parent->_left = cur;
cur->_parent = parent;
}
//控制平衡
//1.更新平衡因子
//2.如果出现不平衡则需要旋转处理
while (parent)
{
//在父亲结点左边插入平衡因子--,右边则++
if (parent->_left == cur)
parent->_bf--;
else
parent->_bf++;
//1.平衡因子=0就不要更新平衡因子了
//2.=1或-1则要继续往上调整
//3.=2或-2则要旋转处理
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)
{
if (cur->_bf == -1)
{
//左边不平衡，并且子节点也是左边偏重，右单旋
RotateR(parent);
}
else
{
//左右双旋
RotateLR(parent);
}
}
else //parent->_bf == 2
{
if (cur->_bf == 1)
{
//如果右边不平衡，并且子节点也是右边偏重，则左单旋
RotateL(parent);
}
else
{
//如果右边不平衡，而子节点是左边偏重，此时需要先转换为上面的状态，先右单旋再左单旋。但是不能直接右单旋再左单旋，还需要根据情况处理平衡因子。
RotateRL(parent);
}
}
break;
}
else
{
//走到这里就不是旋转的问题,你要检查别的问题
assert(false);
}
}
return true;
}
🎄AVL树的删除
AVL树的删除极为复杂，可以不要求掌握，了解即可，但是其实删除的思路和插入类似，分为以下几步。
1.按照二叉搜索树的规则删除
2.更新平衡因子，并且进行旋转来调整（最坏情况下可能会一直调整到根节点）。
这里就直接复用上面平衡因子更新的代码以及之前博客实现的二叉搜索树的删除。
bool erase(const K& key)
{
//删除直接按照二叉搜索树的规则删除，然后再进行平衡因子的更新即可
Node* cur = _root;
Node* parent = cur;
/*
删除有三种情况，一种是删除叶子节点，可以直接删除
第二种情况，如果删除的节点只有一个子树，那么删除这个节点后，就让父节点指向他的这一子树
前两种情况可以合并处理
第三种情况则是左右子树都不为空，此时选择一个来节点来替换他后，再删除，就可以不破坏原有结构
如果要保持原有结构不变化，那么选择的节点必须要和删除节点在中序遍历中是连续的，而满足的只有两个节点，一个是其左子树的最大值，一个是其右子树的最小值。
*/
//删除部分
while (cur)
{
//找到删除的位置
if (key > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
//前两种情况合并处理，如果当前结点只有一个子树，则让父节点指向他的子树
//处理只有右子树时
if (cur->_left == nullptr)
{
//如果当前节点为根节点，则让右子树成为新的根节点
if (cur == _root)
{
_root = cur->_left;
}
else
{
//判断当前节点是他父节点的哪一个子树
if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
}
//处理只有左子树时
else if (cur->_right == nullptr)
{
//如果当前节点为根节点，则让左子树成为新的根节点
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
}
//处理左右子树都不为空时,选取左子树的最右节点或者右子树的最左节点
else
{
//这里我选取的是左子树的最右节点
Node* LeftMax = cur->_left;
Node* LeftMaxParent = cur;
//找到左子树的最右节点
while (LeftMax->_right)
{
LeftMaxParent = LeftMax;
LeftMax = LeftMax->_right;
}
//替换节点
std::swap(cur->_kv, LeftMax->_kv);
//判断当前节点是他父节点的哪一个子树, 因为已经是最右子树了，所以这个节点的右子树为空，但是左子树可能还有数据，所以让父节点指向他的左子树
//并且删除最右节点
if (LeftMax == LeftMaxParent->_left)
{
LeftMaxParent->_left = LeftMax->_left;
}
else
{
LeftMaxParent->_right = LeftMax->_left;
}
delete LeftMax;
}
//删除成功，中断
break;
}
}
//查找不到
if (cur == nullptr)
return false;
//更新平衡因子
while (parent)
{
//更新父节点的平衡因子，注意这里和插入是反过来的，因为是删除
if (cur == parent->_left)
{
parent->_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)
{
//如果右边不平衡，并且子节点也是右边偏重，则左单旋
if (cur->_bf == 1)
{
RotateL(parent);
}
//如果右边不平衡，而子节点是左边偏重，此时需要先转换为上面的状态，先右单旋再左单旋。但是不能直接右单旋再左单旋，还需要根据情况处理平衡因子
else
{
RotateRL(parent);
}
}
else
{
//左边不平衡，并且子节点也是左边偏重，右单旋
if (cur->_bf == -1)
{
RotateR(parent);
}
//同上，左右双旋
else
{
RotateLR(parent);
}
}
//旋转完后恢复平衡，更新结束。
break;
}
}
return true;
}
🎄AVL树的验证
AVL树有两点需要验证：二叉搜索和高度平衡
1.二叉搜索树的特性，可以通过中序遍历来看看是否有序来判断。
2.高度平衡可以通过判断他所有的子树是否两边高度平衡，来判断其是否具有平衡的特性。
中序遍历
void _InOrderTravel(Node* root) const
{
if (root == nullptr)
return;
_InOrderTravel(root->_left);
std::cout << root->_kv.first << ':' << root->_kv.second << std::endl;
_InOrderTravel(root->_right);
}
void InOrderTravel() const
{
_InOrderTravel(_root);
}
int main()
{
int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16,14};
//int arr{ 16, 3, 7, 11, 9, 26, 18, 14, 15 };
AVLTree<int, int> t;
for (auto e : arr)
{
t.insert(make_pair(e,e));
}
t.InOrderTravel();
return 0;
}
到这里验证通过只能说明是搜索树没有问题。我们还要验证树是否平衡。
1.先计算出左右子树的高度
2.再检测每课子树的平衡因子
int countHeight(Node* root) const
{
if (root == nullptr)
return 0;
int leftHeight = countHeight(root->_left);
int rightHeight = countHeight(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool _IsBalance(Node* root) const
{
if (root == nullptr)
return true;
int leftHeight = countHeight(root->_left);
int rightHeight = countHeight(root->_right);
return abs(leftHeight - rightHeight) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
bool IsBalance() const
{
return _IsBalance(_root);
}
这里再推荐一道题，可以顺便去AC了：验证平衡二叉树
🎄AVL树的修改
修改可以直接调用insert，最后直接返回pair对象。
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return make_pair(_root, true);
}
// 找到存储位置，把数据插入进去
Node* parent = _root, * cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(cur, true);
}
}
cur = new Node(kv);
Node* newnode = cur;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
// 控制平衡
// 1、更新平衡因子
// 2、如果出现不平衡，则需要旋转
//while (parent)
while (cur != _root)
{
if (parent->_left == cur)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
// parent所在的子树高度变了，会影响parent->parent
// 继续往上更新
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//parent所在子树已经不平衡，需要旋转处理一下
if (parent->_bf == -2)
{
if (cur->_bf == -1)
{
// 右单旋
RotateR(parent);
}
else // cur->_bf == 1
{
RotateLR(parent);
}
}
else // parent->_bf == 2
{
if (cur->_bf == 1)
{
// 左单旋
RotateL(parent);
}
else // cur->_bf == -1
{
RotateRL(parent);
}
}
break;
}
else
{
// 插入节点之前，树已经不平衡了，需要检查
assert(false);
}
}
return make_pair(newnode, true);
}
?AVL树的性能
- 分析：
- AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度logN
- 但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置
- 总结：
如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但如果需要一个结构经常修改，就不太适合。