当前位置:网站首页>AvL树的实现
AvL树的实现
2022-07-06 10:41:00 【m0_62406299】
一,AvL树的概念:
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当
于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年
发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之
差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:
它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在 ,搜索时
间复杂度O(logn )
二,AVL树节点的定义
template<class T>
struct AVLTreeNode
{
AVLTreeNode(const T& data)
: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
, _data(data), _bf(0)
{}
AVLTreeNode<T>* _pLeft; // 该节点的左孩子
AVLTreeNode<T>* _pRight; // 该节点的右孩子
AVLTreeNode<T>* _pParent; // 该节点的双亲
T _data;
int _bf; // 该节点的平衡因子
};
三,Avl树节点的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么AVL树的插入
过程可以分为两步:
1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子
bool Insert(const T& data)
{
// 1. 先按照二叉搜索树的规则将节点插入到AVL树中
// ...
// 2. 新节点插入后,AVL树的平衡性可能会遭到破坏,此时就需要更新平衡因子,并检测是否破坏了
AVL树
// 的平衡性
/*
pCur插入后,pParent的平衡因子一定需要调整,在插入之前,pParent
的平衡因子分为三种情况:-1,0, 1, 分以下两种情况:
1. 如果pCur插入到pParent的左侧,只需给pParent的平衡因子-1即可
2. 如果pCur插入到pParent的右侧,只需给pParent的平衡因子+1即可
此时:pParent的平衡因子可能有三种情况:0,正负1, 正负2
1. 如果pParent的平衡因子为0,说明插入之前pParent的平衡因子为正负1,插入后被调整成0,此
时满足
AVL树的性质,插入成功
2. 如果pParent的平衡因子为正负1,说明插入前pParent的平衡因子一定为0,插入后被更新成正负
1,此
时以pParent为根的树的高度增加,需要继续向上更新
3. 如果pParent的平衡因子为正负2,则pParent的平衡因子违反平衡树的性质,需要对其进行旋转
处理
*/
while (pParent)
{
// 更新双亲的平衡因子
if (pCur == pParent->_pLeft)
pParent->_bf--;
else
pParent->_bf++;
// 更新后检测双亲的平衡因子
if (0 == pParent->_bf)
break;
else if (1 == pParent->_bf || -1 == pParent->_bf)
{
// 插入前双亲的平衡因子是0,插入后双亲的平衡因为为1 或者 -1 ,说明以双亲为根的
二叉树
// 的高度增加了一层,因此需要继续向上调整
pCur = pParent;
pParent = pCur->_pParent;
}
else
{
// 双亲的平衡因子为正负2,违反了AVL树的平衡性,需要对以pParent
// 为根的树进行旋转处理
if(2 == pParent->_bf)
{
// ...
}
else
{
//.......
}
}
}
return true;
}
四,AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡
化。根据节点插入位置的不同,AVL树的旋转分为四种:
1. 新节点插入较高左子树的左侧---左左:右单旋
2.新节点插入较高右子树的右侧————右右:左单旋
3. 新节点插入较高左子树的右侧---左右:先左单旋再右单旋
将双旋变成单旋后再旋转,即:先对30进行左单旋,然后再对90进行右单旋,旋转完成后再考虑平衡因子的更新
4. 新节点插入较高右子树的左侧---右左:先右单旋再左单旋
参考右左双旋。
总结:
假如以pParent为根的子树不平衡,即pParent的平衡因子为2或者-2,分以下情况考虑
1. pParent的平衡因子为2,说明pParent的右子树高,设pParent的右子树的根为pSubR
当pSubR的平衡因子为1时,执行左单旋
当pSubR的平衡因子为-1时,执行右左双旋
2. pParent的平衡因子为-2,说明pParent的左子树高,设pParent的左子树的根为pSubL
当pSubL的平衡因子为-1是,执行右单旋
当pSubL的平衡因子为1时,执行左右双旋
旋转完成后,原pParent为根的子树个高度降低,已经平衡,不需要再向上更新。
边栏推荐
- 测试123
- 文档编辑之markdown语法(typora)
- Ms-tct: INRIA & SBU proposed a multi-scale time transformer for motion detection. The effect is SOTA! Open source! (CVPR2022)...
- Penetration test information collection - basic enterprise information
- Reprint: defect detection technology of industrial components based on deep learning
- 监控界的最强王者,没有之一!
- F200 - UAV equipped with domestic open source flight control system based on Model Design
- 44 colleges and universities were selected! Publicity of distributed intelligent computing project list
- SQL injection Foundation
- Use cpolar to build a business website (1)
猜你喜欢
传输层 拥塞控制-慢开始和拥塞避免 快重传 快恢复
F200 - UAV equipped with domestic open source flight control system based on Model Design
Compilation Principle -- C language implementation of prediction table
【中山大学】考研初试复试资料分享
Jerry is the custom background specified by the currently used dial enable [chapter]
UDP protocol: simple because of good nature, it is inevitable to encounter "city can play"
Recursive way
On time and parameter selection of asemi rectifier bridge db207
递归的方式
FMT open source self driving instrument | FMT middleware: a high real-time distributed log module Mlog
随机推荐
Penetration test information collection - WAF identification
2022暑期项目实训(二)
Markdown syntax for document editing (typera)
A method of sequentially loading Unity Resources
Test 1234
Recommend easy-to-use backstage management scaffolding, everyone open source
UDP protocol: simple because of good nature, it is inevitable to encounter "city can play"
使用cpolar建立一个商业网站(1)
Windows connects redis installed on Linux
小程序在产业互联网中的作用
SQL injection - access injection, access offset injection
node の SQLite
复现Thinkphp 2.x 任意代码执行漏洞
Self supervised heterogeneous graph neural network with CO comparative learning
SQL injection Foundation
atcoder它A Mountaineer
Shangsilicon Valley JUC high concurrency programming learning notes (3) multi thread lock
STM32+ESP8266+MQTT协议连接OneNet物联网平台
Tree-LSTM的一些理解以及DGL代码实现
Distill knowledge from the interaction model! China University of science and Technology & meituan proposed virt, which combines the efficiency of the two tower model and the performance of the intera