【C++】学习笔记——AVL树
十六、AVL树
1. AVL树的概念
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:
当向二叉搜索树中插入新结点后,如果能保证 每个结点的左右子树高度之差的绝对值不超过1 (需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
上面这两个二叉树都不是AVL树。
AVL树的左右子树都是AVL树,左右子树高度之差(简称平衡因子) 的绝对值不超过1。平衡因子 = 右子树高度 - 左子树高度。
这才是AVL树。AVL树是一个高度平衡二叉搜索树。
2. AVL树节点的定义
// AVLTree 节点
template<class K, class V>
struct AVLTreeNode
{
// 指向左孩子的指针
AVLTreeNode* _left;
// 指向右孩子的指针
AVLTreeNode* _right;
// 指向父节点的指针
AVLTreeNode* _parent;
// 平衡因子
int _bf;
// 存储的Key-Value结构数据
std::pair<K, V> _kv;
// 节点的构造函数
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
,_kv(kv)
{}
};
3. AVL树的插入
由于AVL树一颗二叉搜索树,所以我们插入的时候需要根据二叉搜索树的插入方式插入新节点(比父节点小就往左走,比父节点大就往右走,直到找到空节点插入该新节点), 但是!相比于二叉搜索树,AVL树还有一套自己的规则,他要保证高度需要平衡,所以当我们插入新节点的时候,必须要判断插入后的节点是否会破坏AVL树的平衡。如何判断AVL树是否平衡?保证平衡因子只在 -1 0 1 三个数就行了。
假设我们要插入的新节点在 6号 节点的左侧。由于新节点插入的位置一定是一个 空树 ,所以 新节点的插入导致该侧树的高度 + 1 ,则需要更新一下父节点的平衡因子。
新节点插入在父节点的左侧 —> 父节点的平衡因子 - 1
新节点插入在父节点的右侧 —> 父节点的平衡因子 + 1
重点来了!插入新节点后,难道它就只影响父节点的平衡因子吗? 它影响的是包含它的所有树! 即它的祖先节点。我们不能只仅仅修正父节点的平衡因子。我们还需要逐渐向上修正,直到不需要修正为止。
平衡因子的修正有3种情况:
①修正后变成 0 。不管是从-1变成0还是从1变成0,只要是0,说明左右子树高度相等,并且整体树的高度并没有增加,如果以该节点为根节点的树高度并没有增加,那么对于该节点父节点的平衡因子就没有修正的必要。
①修正后变成 1 或 -1 。同理,父节点肯定是从0变过来的,树的高度发生了变化,则父节点的父节点就仍需要修正平衡因子。
①修正后变成 -2 或 2 。由于平衡因子只能是 -1 ,0 ,1 。所以说明此时的树已经不是AVL树了,我们需要对树进行调整来使其恢复成AVL树。调整方法为 旋转 。
插入操作代码:
bool Insert(const std::pair<K, V>& kv)
{
// 空树则创建根节点
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
// 找到新节点应该插入的位置
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 (kv.first < parent->_kv.first)
parent->_left = cur;
else
parent->_right = cur;
// 新节点指向父节点
cur->_parent = parent;
// 修正祖先的平衡因子
while (parent)
{
// 在树的左子树里插入了新节点 父节点平衡因子减1
if (cur == parent->_left)
--parent->_bf;
// 在树的右子树里插入了新节点 父节点平衡因子加1
else
++parent->_bf;
// 判断修正后的平衡因子是否符合要求
if (parent->_bf == 0) break;
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
// 该树已经不满足AVL树的性质
else if (parent->_bf == 2 || parent->_bf == -2)
{
// 旋转操作
break;
}
// 其他异常情况
else assert(false);
}
// 插入成功
return true;
}
注意,旋转后满足条件,需要退出循环。
4. AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点,可能会造成不平衡,此时必须调整树的结构,使之平衡化。根据节点插入位置的不同,AVL树的旋转分为四种:
①左子树高度较高,新节点插入在左子树的左侧 — 左左:使用右单旋。
其中 a,b,c 为子树,h为树的高度。我们需要 将左子树的右子树修改成 60 节点的左孩子,再把 60 节点修改为 30 节点的右孩子, 30 节点则替代原本的 60 节点的位置。如此修正后,AVL树重新平衡,并且 30 节点和 60 节点的平衡因子都会变成 0。
一定要注意的是 :这里的 h 可能为0!必须要判断 b 子树存不存在!
右单旋代码:
// 左左 --- 右单旋
void RotateR(Node* parent)
{
// 父节点的左孩子
Node* subL = parent->_left;
// 父节点的左孩子的右孩子
Node* subLR = subL->_right;
// 父节点的父节点
Node* ppnode = parent->_parent;
// 修改父节点的指向
parent->_left = subLR;
parent->_parent = subL;
// 修改父节点的左孩子的指向
subL->_right = parent;
subL->_parent = ppnode;
// 如果父节点的左孩子的右孩子存在,则修改其指向
if (subLR)
subLR->_parent = parent;
// 修改父节点的父节点的指向
if (parent == _root)
_root = subL;
else if (parent == ppnode->_left)
ppnode->_left = subL;
else
ppnode->_right = subL;
// 修正后父节点和父节点的左孩子的平衡因子都会变成 0
parent->_bf = 0;
subL->_bf = 0;
}
②右子树高度较高,新节点插入在右子树的右侧 — 右右:使用左单旋。
与 右单旋 同理,只是左右方向相反。
左单旋代码:
// 右右 --- 左单旋
void RotateL(Node* parent)
{
// 父节点的右孩子
Node* subR = parent->_right;
// 父节点的右孩子的左孩子
Node* subRL = subR->_left;
// 父节点的父节点
Node* ppnode = parent->_parent;
// 修改父节点的指向
parent->_right = subRL;
parent->_parent = subR;
// 修改父节点的右孩子的指向
subR->_left = parent;
subR->_parent = ppnode;
// 如果父节点的右孩子的左孩子存在,则修改其指向
if (subRL)
subRL->_parent = parent;
// 修改父节点的父节点的指向
if (parent == _root)
_root = subR;
else if (parent == ppnode->_left)
ppnode->_left = subR;
else
ppnode->_right = subR;
// 修正后父节点和父节点的右孩子的平衡因子都会变成 0
parent->_bf = 0;
subR->_bf = 0;
}
①左子树高度较高,新节点插入在左子树的右侧 — 左右:先左单旋再右单旋。
对于左单旋和右单旋,我们已经差不多能够理解了,但是在这种情况下,单纯使用左右单旋已经无法恢复平衡了,但是我们可以使用 双旋 ,先旋转一次使其符合单旋情况。
使用两次旋转就能使其恢复AVL树的性质,所以说我们只需要调用两次单旋函数就可以了吗?非也,虽然树的结构对了,但是我们并没有修正平衡因子。我们可以观察得到:60 节点最终成为了这颗子树的根节点,60 节点的左孩子成为了 30 节点的右孩子, 60 节点的右孩子成为了 90 节点的左孩子。
如果 60 节点的平衡因子在没旋转前是 0,则说明 60 节点就是最新插入的节点。那么 a,b,c,d子树都不存在 所以 30 节点、 60 节点、 90 节点的平衡因子都是 0。
如果 60 节点的平衡因子在没旋转前是 -1,则说明新节点插入到了 60 节点的左子树中。所以最后 c 子树将会比 d 子树高度小1,所以 30 节点和 60 节点的平衡因子都是 0, 90 节点的平衡因子是 1。
如果 60 节点的平衡因子在没旋转前是 1,由上可知, 30 节点的平衡因子是 -1,60 节点和 90 节点的平衡因子都是 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 == 0)
{
parent->_bf = 0;
subL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_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 == 0)
{
parent->_bf = 0;
subR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
}
}
5. AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分两步:① 验证其为二叉搜索树。如果中序遍历可得到一个有序的序列,就说明为二叉搜索树。②验证其为平衡树。每个节点子树高度差的绝对值不超过1,判断节点的平衡因子是否计算正确。
中序遍历:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
std::cout << root->_kv.first << "[" << root->_kv.second << "]" << std::endl;
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
}
判断树是否平衡&&计算平衡因子是否异常:
bool _IsBalance(Node* root, int& height)
{
if (root == nullptr)
{
height = 0;
return true;
}
int HeightLeft = 0, HeightRight = 0;
// 左右子树有一个不满足就返回false
if (!_IsBalance(root->_left, HeightLeft) || !_IsBalance(root->_right, HeightRight))
return false;
// 高度不平衡
if (std::abs(HeightLeft - HeightRight) > 1)
{
std::cout << root->_kv.first << "该树不平衡" << std::endl;
return false;
}
// 平衡因子计算错误
if (HeightRight - HeightLeft != root->_bf)
{
std::cout << root->_kv.first << "平衡因子异常" << std::endl;
return false;
}
// 返回该子树的高度
height = std::max(HeightLeft, HeightRight) + 1;
return true;
}
bool IsBalance()
{
int height = 0;
return _IsBalance(_root, height);
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
return std::max(Height(root->_left), Height(root->_right)) + 1;
}
int Height()
{
return _Height(_root);
}
6. 完整代码+测试
AVLTree.h:
#pragma once
#include <utility>
#include <cassert>
#include <iostream>
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
// 平衡因子
int _bf;
std::pair<K, V> _kv;
AVLTreeNode(const std::pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
, _kv(kv)
{}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const std::pair<K, V>& kv)
{
// 空树则创建根节点
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
// 找到新节点应该插入的位置
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 (kv.first < parent->_kv.first)
parent->_left = cur;
else
parent->_right = cur;
// 新节点指向父节点
cur->_parent = parent;
// 修正祖先的平衡因子
while (parent)
{
// 在树的左子树里插入了新节点 父节点平衡因子减1
if (cur == parent->_left)
--parent->_bf;
// 在树的右子树里插入了新节点 父节点平衡因子加1
else
++parent->_bf;
// 判断修正后的平衡因子是否符合要求
if (parent->_bf == 0) break;
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
// 该树已经不满足AVL树的性质
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 assert(false);
}
// 插入成功
return true;
}
// 左左 --- 右单旋
void RotateR(Node* parent)
{
// 父节点的左孩子
Node* subL = parent->_left;
// 父节点的左孩子的右孩子
Node* subLR = subL->_right;
// 父节点的父节点
Node* ppnode = parent->_parent;
// 修改父节点的指向
parent->_left = subLR;
parent->_parent = subL;
// 修改父节点的左孩子的指向
subL->_right = parent;
subL->_parent = ppnode;
// 如果父节点的左孩子的右孩子存在,则修改其指向
if (subLR)
subLR->_parent = parent;
// 修改父节点的父节点的指向
if (parent == _root)
_root = subL;
else if (parent == ppnode->_left)
ppnode->_left = subL;
else
ppnode->_right = subL;
// 修正后父节点和父节点的左孩子的平衡因子都会变成 0
parent->_bf = 0;
subL->_bf = 0;
}
// 右右 --- 左单旋
void RotateL(Node* parent)
{
// 父节点的右孩子
Node* subR = parent->_right;
// 父节点的右孩子的左孩子
Node* subRL = subR->_left;
// 父节点的父节点
Node* ppnode = parent->_parent;
// 修改父节点的指向
parent->_right = subRL;
parent->_parent = subR;
// 修改父节点的右孩子的指向
subR->_left = parent;
subR->_parent = ppnode;
// 如果父节点的右孩子的左孩子存在,则修改其指向
if (subRL)
subRL->_parent = parent;
// 修改父节点的父节点的指向
if (parent == _root)
_root = subR;
else if (parent == ppnode->_left)
ppnode->_left = subR;
else
ppnode->_right = subR;
// 修正后父节点和父节点的右孩子的平衡因子都会变成 0
parent->_bf = 0;
subR->_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 == 0)
{
parent->_bf = 0;
subL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_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 == 0)
{
parent->_bf = 0;
subR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
std::cout << root->_kv.first << "[" << root->_kv.second << "]" << std::endl;
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
}
bool _IsBalance(Node* root, int& height)
{
if (root == nullptr)
{
height = 0;
return true;
}
int HeightLeft = 0, HeightRight = 0;
if (!_IsBalance(root->_left, HeightLeft) || !_IsBalance(root->_right, HeightRight))
return false;
if (std::abs(HeightLeft - HeightRight) > 1)
{
std::cout << root->_kv.first << "该树不平衡" << std::endl;
return false;
}
if (HeightRight - HeightLeft != root->_bf)
{
std::cout << root->_kv.first << "平衡因子异常" << std::endl;
return false;
}
height = std::max(HeightLeft, HeightRight) + 1;
return true;
}
bool IsBalance()
{
int height = 0;
return _IsBalance(_root, height);
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
return std::max(Height(root->_left), Height(root->_right)) + 1;
}
int Height()
{
return _Height(_root);
}
private:
Node* _root = nullptr;
};
void TestAVLTree1()
{
int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
AVLTree<int, int> t;
for (auto e : a)
{
t.Insert(std::make_pair(e, e));
}
t.InOrder();
std::cout << t.IsBalance() << std::endl;
}
test.cpp:
#include "AVLTree.h"
#include <iostream>
using namespace std;
int main()
{
TestAVLTree1();
return 0;
}
运行结果:
7. AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度,即 l o g 2 ( N ) log_2 (N) log2(N)。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。
未完待续
原文地址:https://blog.csdn.net/m0_69828905/article/details/140464509
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!