C++：AVL树深度剖析
今天我们开始学习AVL树🌲🌲🌲
<(￣︶￣)↗[GO!] <(￣︶￣)↗[GO!] <(￣︶￣)↗[GO!]
一、 AVL的概念
-
定义与特性：AVL树是最早发明的自平衡二叉查找树，是一棵空树或具备以下特性的二叉搜索树：其左右子树均为AVL树，且左右子树高度差的绝对值不超过1。因此，AVL树是一棵高度平衡的二叉搜索树，通过控制高度差实现平衡。
-
命名由来：AVL树得名于其发明者G. M. Adelson-Velsky和E. M. Landis，他们是两位前苏联科学家，于1962年在论文《An Algorithm for the Organization of Information》中提出了这一概念。
- 平衡因子的引入：在AVL树中，每个结点都有一个平衡因子（Balance Factor），定义为右子树高度减去左子树高度。其取值范围为-1、0、1。虽然AVL树并不强制要求平衡因子，但平衡因子便于观察和维护树的平衡状态，如同风向标的作用。
- 高度差要求的原因：AVL树的高度差要求不超过1，而非严格为0，因为在某些情况下（例如树包含2个或4个节点时），高度差为0无法实现，而高度差为1是最佳平衡状态。
- 效率与分布：AVL树的节点数量和分布接近完全二叉树，其高度可以被控制在 (\log_2 n) 内，因此插入、删除、查找、修改的效率也在 (O(\log_2 n)) 范围内，比普通二叉搜索树有显著提升。
二、AVL树的实现
1. AVL树结构定义
#pragma once
#include<iostream>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv; // 数据的存储
AVLTreeNode<K, V>* _left; // 左孩子
AVLTreeNode<K, V>* _right; // 右孩子
AVLTreeNode<K, V>* _parent; // 父结点
AVLTreeNode(const pair<K, V>& kv)
: _kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode Node;
public:
private:
Node* _root = nullptr;
};
2. 插入
1）插入遍历逻辑控制
首先，第一部分，与set，map的插入是一样的，小于往右走，大于往左走。
bool insert(const pair<K, V>& kv)
{
// 树为空，直接插入然后返回
if (_root = nullptr)
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
// 小于往左走
if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first) // 大于往右走
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(kv);
// 链接
if (cur->_kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
// 通过平衡因子控制平衡
return true;
}
2）插入什么时候需要控制平衡？
接下来就是控制平衡的逻辑
接下来，一张图，带你搞明白这里所有的逻辑！！！
控制平衡逻辑总结：
- 新增在
左，parent平衡因子减减 - 新增在
右，parent平衡因子加加 - 更新后parent平衡因子 ==
0，说明parent所在的子树的高度不变，不会再影响祖先，不用再继续沿着到 root 的路径往上更新 - 更新后parent平衡因子 ==
1 or -1，说明parent所在的子树的高度变化，会再影响祖先，需要继续沿着到root的路径往上更新 - 更新后parent平衡因子 ==
2 or -2，说明parent所在的子树的高度变化且不平衡，对parent所在子树进行旋转，让他平衡 - 更新到
根节点会停止，也就是parent == nullptr
我们有如下这几种情况：
控制代码如下：
// 通过平衡因子控制平衡
while (parent) // 如果parent为空，就停止
{
if (cur == parent->_left)
{
parent->_bf--; // 如果新加入的结点在左侧，父亲平衡因子减1
}
else
{
parent->_bf++; // 如果新加入的结点在右侧，父亲平衡因子加1
}
if (parent->_bf == 0)
{
break; // 父亲平衡因子为0，更新结束
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
// 继续向上更新
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
// 子树不平衡了，需要进行旋转调整
}
else
{
assert(false);
}
}
3）旋转逻辑
本篇文章我们先来看这样的一种情况，剩下的情况我们下次进行解析：
比如我们要进行左单旋，旋转如下这种情况：
旋转的时候需要注意的问题 !
- 保持他是搜索树
- 变成平衡树且降低这个子树的高度
核心操作:
parent->right = cur->left
cur->left = parent
// 左单旋
void Rotatel(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
// 重新链接
parent->_right = curleft;
if (curleft) // 如果curleft存在
{
curleft->_parent = parent;
}
cur->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = cur;
if (ppnode == nullptr)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left = parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
cur->_parent = ppnode;
}
// 更改平衡因子
parent->_bf = cur->_bf = 0;
}
总结
到这里我们AVL第一部分就结束啦！！！
小小总结一下~🥰🥰🥰
AVL树是一种自平衡的二叉搜索树，以其发明者G. M. Adelson-Velsky和E. M. Landis命名。它通过严格控制左右子树的高度差（绝对值不超过1）保持平衡，从而显著提升增删查改操作的效率。每个节点的平衡因子帮助判断树的平衡状态，其范围为-1、0、1，便于观察与维护。虽然严格的高度平衡（差为0）在某些情况下不可实现，但AVL树的高度接近完全二叉树，因此效率可以稳定在 (O(log n))。这种高度平衡的设计，使AVL树成为效率优于普通二叉搜索树的重要数据结构。
原文地址：https://blog.csdn.net/Jdxxwu/article/details/143885150
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！