前两篇文章: 【C++】从零开始构建二叉搜索树 【C++】初探 map 与 set 我们学习了二叉搜索树:二叉搜索树虽可以缩短查找的效率,如果数据有序或接近有序二叉搜索树将退化为单支树,这样二叉搜索树效率退化为O(n),不够高效!所以就有了改进版的二叉搜索树->AVL树(平衡二叉搜索树)
在1962年,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
map与set 的底层实现也是AVL树或红黑树!
一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:
如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在
,搜索时间复杂度 O(
)
通过每次插入删除的调整保证二叉树始终保持一个近乎完美的完全二叉树,规避了极端情况下二叉搜索树退化为单枝树的情况
接下来我们就来研究如何实现AVL树!!!
首先AVL树是在二叉搜索树的基础上进行改进,AVL树节点中加入了:
_bf
:左右子树的高度差 right子树高度 - left子树高度
,即左子树插入节点时_bf--
,右子树插入节点时_bf++
!_parent
:指向父节点的指针,为了可以回溯更新父节点的平衡因子。template<class K, class V>
struct AVLtreeNode
{
typedef AVLtreeNode<K, V> Node;
//三叉树结构
Node* _parent;
Node* _left;
Node* _right;
//键值对
pair<K, V> _kv;
//平衡因子
int _bf;
AVLtreeNode(pair<K, V> kv)
:_parent(nullptr)
,_right(nullptr)
,_left(nullptr)
/*
* 提示:该行代码过长,系统自动注释不进行高亮。一键复制会移除系统注释
* ,_kv(kv)
*/
,_bf(0)
{
}
};
注意构造函数的初始化列表,不要出现野指针!!!
先不管平衡因子这个变量,AVL树的插入比二叉搜索树略微复杂一点,需要多处理一步父指针:
bool Insert(pair<K, V> kv)
{
Node* node = new Node(kv);
//如果为空直接赋值
if (_root == nullptr)
{
_root = node;
return true;
}
//反之寻找插入位置(按照 key 比较大小)
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
parent = cur;
if (cur->_kv.first > kv.first)
{
cur = cur->_left;
}
else if(cur->_kv.first < kv.first)
{
cur = cur->_right;
}
else
{
//二叉搜索树默认不重复数据
return false;
}
}
//按照大小插入节点
if (kv.first > parent->_kv.first)
{
parent->_right = node;
}
else
{
parent->_left = node;
}
//记得要处理父指针!!!
node->_parent = parent;
cur = node;
//更新平衡因子
//...
}
}
结下来就是处理平衡因子:左子树插入节点时_bf--
,右子树插入节点时_bf++
这里思考一下,平衡因子的处理要到什么情况才停下来???
当我们插入一个新节点时,有两种情况:
父节点的平衡因子经过更新后可以得到三种情况:
根据上述是分类我们可以写出处理平衡因子的的代码!
首先可能要向上一直处理,所以干脆写一个while循环,在内部在进行分类:如果需要继续处理爷爷节点,就继续循环,不需要处理就跳出循环!
//...
//处理平衡因子
//更新平衡因子
while (parent != nullptr)
{
if (cur == parent->_left)
{
//左子树增加 父节点平衡因子--
parent->_bf--;
}
else
{
//右子树增加 父节点平衡因子++
parent->_bf++;
}
//为零直接退出
if (parent->_bf == 0)
{
break;
}
//为 1 或 -1 继续向上进行
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_parent;
}
//旋转来哩!!!
else if (parent->_bf == 2 || parent->_bf == -2)
{
//分类旋转
//旋转之后二叉树平衡!
break;
}
//特殊情况处理 因为未来不知道会出什么bug ,在这里截断一下
else
{
cout << "错误!!!" << endl;
assert(false);
}
}
parent的平衡因子是 ∓2的情况的特殊处理就是旋转!!!下面我们来看如何进行旋转!!!
旋转是AVL树的精髓所在!!
首先选择有四种:右单旋 ,左单旋,左右双旋,右左双旋
我们依次来介绍:
我们先来看什么情况需要使用右单旋:
这是最简单的情况,简单的向右旋转,使其满足AVL树的性质!
再来看一般情况,并来具体分析一下:
-1
,subL的平衡因子是0
!-1
, parent的平衡因子变为-2
_parent
指针void RotateR(Node* parent)
{
Node* subL = parent->_left; //左子节点
Node* subLR = subL->_right; //左节点的右节点
Node* ppNode = parent->_parent;//爷爷节点
subL->_right = parent;
parent->_parent = subL;
parent->_left = subLR;
if (subLR != nullptr)
subLR->_parent = parent;
//处理爷爷节点
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
//保证爷爷节点的指向正确
if (parent == ppNode->_left)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
//处理平衡因子 因为已经平衡了 所以都为 0
parent->_bf = 0;
subL->_bf = 0;
}
旋转完parent满足AVL树的性质!
左单旋与右单旋类似!!!
1
,subL的平衡因子是0 !1
, parent的平衡因子变为2
具体实现基本就是右单旋的框架,更改一下变量,不在单独写!
我们来看一种情况:
这种情况既不能通过右单旋解决,也不能通过左单旋解决!!! 这时候就需要继续左右双旋:先进行一次做单旋,在进行一次右单旋。
具体怎么操作,我们来看:
-1
,subL的平衡因子是0
!1
, parent的平衡因子变为-2
注意,根据图分析,插入的位置会影响subL和 parent的平衡因子,需要根据subLR分类讨论:
-1
1
//左右双旋
void RotateLR(Node* parent)
{
//先记录相关信息
Node* subL = parent->_left;
Node* subLR = subL->_right;
//需要通过subLR来确定平衡因子
int bf = subLR->_bf;
//进行旋转
//左单旋 subL
RotateL(subL);
//右单旋 parent
RotateR(parent);
//平衡因子需要调整!!!
//在subLR的左子树插入
if (bf == -1)
{
//右单旋 parent 会将subLR的右子树给parent的左边 ,parent左边比右边低
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
//在subLR的右子树插入
else if (bf == 1)
{
parent->_bf = 0;
//左单旋 subL 会将subLR的左子树给subL的右边 ,subL左边比右边高
subL->_bf = -1;
subLR->_bf = 0;
}
//如果subLR自身是插入的节点
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
//出错了
assert(false);
}
}
这样就好了
来看图:
具体实现与左右双旋类似,先进行一次右单旋,再进行一次左单旋!
细节不在多说,根据图自行书写即可!
我们完成了旋转,就可以补全插入操作的空缺,按情况分好类即可:
//插入节点
bool Insert(pair<K, V> kv)
{
Node* node = new Node(kv);
//如果为空直接赋值
if (_root == nullptr)
{
_root = node;
return true;
}
//反之寻找插入位置(按照 key 比较大小)
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
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 = node;
if (kv.first > parent->_kv.first)
{
parent->_right = node;
}
else
{
parent->_left = node;
}
node->_parent = parent;
cur = node;
//更新平衡因子
while (parent != nullptr)
{
if (cur == parent->_left)
{
//左子树增加 父节点平衡因子--
parent->_bf--;
}
else
{
//右子树增加 父节点平衡因子++
parent->_bf++;
}
//为零直接退出
if (parent->_bf == 0)
{
break;
}
//为 1 或 -1 继续向上进行
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_parent;
}
//旋转来哩
else if (parent->_bf == 2 || parent->_bf == -2)
{
//分类旋转
if (parent->_bf == -2 && cur->_bf == -1)
{
//右单旋
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == 1)
{
//左单旋
RotateL(parent);
}
//需要双旋的情况
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
//旋转之后二叉树平衡!
break;
}
//特殊情况处理
else
{
cout << "错误!!!" << endl;
assert(false);
}
}
}
}
在这里一定一定做好测试工作!!! 一定一定保证插入没有问题了在向下进行其他函数的书写,不然出错了就会让人崩溃的!!!
寻找与二叉搜索树一样:
//寻找节点
bool Find(K key)
{
Node* cur = _root;
while (cur != nullptr)
{
if (key == cur->_kv.first)
{
return true;
}
else if (key < cur->_kv.first)
{
cur = cur->_left;
}
else
{
cur = cur->_right;
}
}
return false;
}
删除节点的方法是在二叉搜索树的基础上加入了平衡因子与父节点指针,我们依旧可以按照被删除节点的状况来分类讨论:
⚠️⚠️⚠️下面的过程很重要⚠️⚠️⚠️:
2 * 3 = 6
需要旋转时父树有两个子树,都需要讨论 。子树节点平衡因子有 3 种 -1 1 0
。我们不需要思考这些情况是删除哪里的节点得到的,只需要对每种情况进行处理就可以!!!平衡因子情况 | 如何选择 | 为什么 |
---|---|---|
parent为 -2 parent->_left为 -1 | 此时进行右单旋 | 现在是左边高,因此需要向右旋转 |
parent为 -2 parent->_left为 1 | 此时进行左右双旋 | 此时左边高,并且子树的平衡,所以只需要向右旋转 |
parent为 -2 parent->_left为 0 | 此时进行右单旋 | 此时是删除了parent右边的节点,导致其不平衡(左高右低),所以向右旋转 |
parent为 2 parent->_right为 1 | 此时进行左单旋 | 现在是右边高,因此需要向左旋转 |
parent为 2 parent->_right为 -1 | 此时进行右左双旋 | 因为子树左边高,父树右边高,先对子树进行右旋使其偏差一致,可以进行左旋来修正 |
parent为 2 parent->_right为 0 | 此时进行左单旋 | 此时右边高,并且子树的平衡,所以只需要向左旋转 |
来看代码:
//删除节点
bool Erase(K key)
{
Node* cur = _root;
Node* parent = nullptr;
//记录需要删除的节点
Node* DelParentPos = nullptr;
Node* DelPos = nullptr;
//寻找替换值
//寻找需要被删除的节点
while (cur != nullptr)
{
if (key > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
//现在找到了需要被删除的节点
//
//删除需要涉及平衡因子的改变
//父指针的修正
// 根据需要删除节点的状态分出以下4种状态:
//a.要删除的结点无孩子结点
//b.要删除的结点只有左孩子结点
//c.要删除的结点只有右孩子结点
//d.要删除的结点有左、右孩子结点
//平衡因子的修正比较复杂 所以不能直接删除的情况要进行虚拟删除
if (cur->_left == nullptr || cur->_right == nullptr)
{
if (cur->_left == nullptr)
{
//如果删除的的是根节点,单独处理
if (cur == _root)
{
_root = cur->_right;
if(cur->_right)
cur->_right->_parent = nullptr;
delete cur;
}
//只要有祖先节点就要进行平衡因子的处理!!! 先虚拟删除
else
{
DelParentPos = parent; //标记实际删除结点的父结点
DelPos = cur; //标记实际删除的结点
}
}
else
{
//如果删除的的是根节点,单独处理
if (cur == _root)
{
_root = cur->_left;
cur->_left->_parent = nullptr;
delete cur;
}
else
{
DelParentPos = parent; //标记实际删除结点的父结点
DelPos = cur; //标记实际删除的结点
}
}
break;
}
//d.要删除的结点有左、右孩子结点
//替换法 + 虚拟删除
else
{
Node* rightMin = nullptr;
Node* rightMinParent = cur;
//寻找右子树最小值
rightMin = cur->_right;
rightMinParent = cur;
while (rightMin->_left != nullptr)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
//找到可以替换的节点
//交换键值对
swap(cur->_kv, rightMin->_kv);
//把要删除的节点记录下来,模拟删除
DelParentPos = rightMinParent;
DelPos = rightMin;
break;
}
}
}
//没有找到的情况
if (DelParentPos == nullptr) return false;
parent = DelParentPos;
cur = DelPos;
//然后更新平衡因子
while (cur != _root)
{
if (cur == parent->_left)
{
parent->_bf++;
}
else
{
parent->_bf--;
}
//根据不同结果来处理
// 为0说明该子树的高度改变 高度变低了 继续向上处理
if (parent->_bf == 0)
{
cur = parent;
parent = cur->_parent;
}
//为正负 1 说明该子树的高度没有改变
else if (parent->_bf == 1 || parent->_bf == -1)
{
break;
}
//出现 正负 2 说明需要进行旋转修正!
else if (parent->_bf == 2 || parent->_bf == -2)
{
//分类讨论
if (parent->_left->_bf == -1 && parent->_bf == -2)
{
//注意要及时更新parent根节点,不然无法顺利向上推进
//cur 节点经过旋转 指向依然正确,是parnet的子树
Node* tmp = parent->_left;
RotateR(parent);
parent = tmp;
}
else if (parent->_left->_bf == 1 && parent->_bf == -2)
{
Node* tmp = parent->_left->_right;
RotateLR(parent);
parent = tmp;
}
else if (parent->_left->_bf == 0 && parent->_bf == -2)
{
Node* tmp = parent->_left;
RotateR(parent);
parent = tmp;
parent->_bf = 1;
parent->_right->_bf = -1;
//此时 parent 的平衡因子为 1 说明该树删除后高度没有改变,所以不在需要向上更新
break;
}
else if (parent->_right->_bf == -1 && parent->_bf == 2)
{
Node* tmp = parent->_right->_left;
RotateRL(parent);
parent = tmp;
}
else if (parent->_right->_bf == 1 && parent->_bf == 2)
{
Node* tmp = parent->_right;
RotateL(parent);
parent = tmp;
}
else if (parent->_right->_bf == 0 && parent->_bf == 2)
{
Node* tmp = parent->_right;
RotateL(parent);
parent = tmp;
parent->_bf = -1;
parent->_left->_bf = 1;
//此时 parent 的平衡因子为 -1 说明该树删除后高度没有改变,所以不在需要向上更新
break;
}
//旋转的本质是将树的高度变低,所以parent树的高度一定会发生改变!
//parent树的高度变化,会影响其父结点的平衡因子,需要继续往上更新平衡因子!
cur = parent;
parent = cur->_parent;
}
else
{
cout << "旋转出现错误!" << endl;
assert(false);
}
}
//处理完平衡因子,现在可以开始删除节点了
if (DelPos->_left == nullptr)
{
if (DelPos == DelParentPos->_left)
{
DelParentPos->_left = DelPos->_right;
if (DelPos->_right)
DelPos->_right->_parent = DelParentPos;
}
if (DelPos == DelParentPos->_right)
{
DelParentPos->_right = DelPos->_right;
if (DelPos->_right)
DelPos->_right->_parent = DelParentPos;
}
}
else//右为空
{
if (DelPos == DelParentPos->_left)
{
DelParentPos->_left = DelPos->_left;
if (DelPos->_left)
DelPos->_left->_parent = DelParentPos;
}
if (DelPos == DelParentPos->_right)
{
DelParentPos->_right = DelPos->_left;
if (DelPos->_left)
DelPos->_left->_parent = DelParentPos;
}
}
delete DelPos;//删除!!!
return true;
}
这一部分值得细细琢磨! 通过借鉴他人的 =代码,我调试了半天才完全排除错误…
我们写了这么多的代码,现在来测试一下,来看看是否满足AVL树!!!
验证AVL树就要来检查每个节点的平衡因子是否满足条件!平衡因子的本质是左右子树的高度差,所以我们可以通过检查每颗子树的高度差来看看是否满足条件: 检查过程需要遍历当前节点的左右子树来获得对应高度,所以我们需要再写一个求高度的函数,都是通过递归来实现,我这里使用的事前序,效率比后序稍差,但写起来简单。
bool IsBalance()
{
return _IsBalance(_root);
}
int Height()
{
return _Height(_root);
}
bool _IsBalance(Node* root)
{
//按照高度进行检查
if (root == nullptr) return true;
if (abs(_Height(root->_left) - _Height(root->_right) ) >= 2) return false;
return _IsBalance(root->_left) && _IsBalance(root->_right);
}
int _Height(Node* root)
{
if (root == nullptr) return 0;
return max(_Height(root->_left) + 1, _Height(root->_right) + 1);
}
现在: 我们写个测试代码测试一下:
void AVLTreeTest3()
{
const int N = 10000000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand() + i);
}
size_t begin2 = clock();
AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
//验证过程中是否平衡
//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
}
cout << t.IsBalance() << endl;
size_t end2 = clock();
cout << "Insert:" << end2 - begin2 << endl;
cout << t.IsBalance() << endl;
cout << "Height:" << t.Height() << endl;
cout << "Size:" << t.Size() << endl;
}
来看效果:
我们实际插入了六百万的节点,测试出来其是AVL树,左右平衡!!! 完美!!!!
都说AVL树的性能很NB ,现在我们就来看看到底有多厉害! 我们之间提供 1亿 的数据量,来看看其插入,查找和删除的效率怎么样:
void AVLTreeTest6()
{
const int N = 100000000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand() + i);
}
size_t begin2 = clock();
AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
}
cout << t.IsBalance() << endl;
size_t end2 = clock();
cout << "Insert:" << end2 - begin2 << endl;
cout << "Height:" << t.Height() << endl;
cout << "Size:" << t.Size() << endl;
size_t begin1 = clock();
// 确定在的值
for (auto e : v)
{
t.Find(e);
}
// 随机值
//for (size_t i = 0; i < N; i++)
//{
// t.Find((rand() + i));
//}
size_t end1 = clock();
cout << "Find:" << end1 - begin1 << endl;
size_t begin3 = clock();
for (auto e : v)
{
t.Erase(e);
}
size_t end3 = clock();
cout << "Erase:" << end3 - begin3 << endl;
}
来看用时:
其中一共有六千万的节点,插入共用时 44 s,依次删除所有节点用时 18s,搜索只用了不到1ms!!!
所以AVL树的优缺点很明显:
下面是对AVL树性能的分析:
AVL树在频繁进行插入和删除操作的场景中可能不是最佳选择。在这些情况下,红黑树等其他自平衡二叉搜索树可能是更好的选择,因为它们对平衡的要求不那么严格,从而在插入和删除操作时可能需要更少的旋转操作。
如果数据结构是静态的,即一旦创建就不会频繁修改,AVL树是一个很好的选择,因为它可以提供高效的查询操作。但是,如果数据结构需要频繁地修改,那么可能需要考虑使用其他数据结构,如红黑树、B树或跳表等,这些数据结构在动态操作方面可能更加高效。
应用场景: