您现在的位置是:首页 >技术交流 >【五一创作】|【C++】AVL树的实现网站首页技术交流
【五一创作】|【C++】AVL树的实现
1.AVL树概念
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查
找元素相当于在顺序表中搜索元素,效率低下,
所以在此基础上提出解决办法:
当向二叉搜索树中插入新节结点时,如果能保证每个节点的左右子树高度之差的绝对值不超过1即可降低树的高度,从而减少平均搜索长度
AVL树又称平衡二叉搜索树
2. AVL树性质
AVL树的性质:
1.它的左右子树都是AVL树
2.左右子树高度之差(平衡因子)的绝对值不超过1(1/0/-1)
平衡因子=右子树高度-左子树高度
3.AVL树的实现
在实现结构与插入功能时,与二叉搜索树有很多相似的地方 :二叉搜索树
所以一部分关于二叉搜索树的地方就不详细说了
与二叉搜索树定义结构不同的是,多了一个父节点parent以及平衡因子bf
insert
insert的实现前半部分与二叉搜索树的insert实现大部分相同
parent的右子树连接新节点为例,出while循环后,需要反向链接父节点,而此时的父节点就为刚才记录cur前一个节点的parent
插入情况分析
1.
若新增节点作为parent的右子树即cur==parent->right
parent的平衡因子+1 即 parent->bf++
若新增节点作为parent的左子树即cur==parent->left
parent的平衡因子 -1 即 parent->bf–
3.
若新增节点作为parent的左子树即cur==parent->left
parent的平衡因子-1 即 parent->bf–
若parent的平衡因子等于1或者-1 即第一种与第二种情况,说明parent所在子树变了,需要继续向上更新爷爷节点
为什么需要继续更新?
说明插入前parent的平衡因子为0,插入前左右高度相等,现在一边高1,高度变了
若parent的平衡因子等于2或者-2 , 说明parent所在子树不平衡,需要以旋转的方式处理子树
若parent的平衡因子等于0, parent所在子树高度不变,就不需要向上更新,插入结束了
为什么插入结束了呢?
插入前parent的平衡因子是-1或者1,插入前一边高一边低,插入节点到矮的那边,高度不变
更新平衡因子
插入新增节点后,更新平衡因子
如果更新之后,平衡因子没有问题(绝对值<=1),说明插入对树的平衡机构没有影响,不需要处理
如果更新之后,平衡出现问题,平衡结构受到影响(平衡因子为2/-2),需要旋转
插入新增节点,会影响部分/整体祖先
旋转处理
旋转的原则:保持继续是搜索树
旋转的目的:左右均衡,降低高度
a/b/c分别代表高度为h的AVL子树
平衡因子=右子树深度-左子树深度
情况1——h=0
当h=0时,60的平衡因子:0-1=-1
30的平衡因子:2-0=2
由于平衡因子出现2,所以需要旋转
情况2——h=1
当h=2时,60的平衡因子:2-1=1,30的平衡因子:3-1=2
由于平衡因子出现2,所以需要旋转
在parent节点左右插入,都会引发平衡因子变为2
情况3——h=2
对于c来说,必定是x形状
假设c为y形状
在左子树新插入一个节点,那这颗子树的平衡因子变为-2,需要旋转,而不会去往上更新到30
若右子树插入一个节点,parent的平衡因子变为0,不需要往上更新到30
对于a和b,必定是x、y、z中的一种形状
假设abc都是x形状,则在c中插入节点,无论插入左边还是右边,都会导致parent的平衡因子为2或者-2
c的高度变化,必定引发旋转
在红框中的四个位置任意一边插入,30的平衡因子都会变为2/-2
虽然分为三种情况,但是旋转的规则是相同
左单旋
以h=1为例
左单旋的旋转方式:
把B变成30的右边,30变成60的左边,60变成整棵树的根
左单旋抽象图
父节点问题
把subR作为30的右子树时,需要更新sub的父节点为parent
把parent作为subR的左子树时,更新parent的父节点为subR
有可能当前旋转的是整棵树或者整棵树的一部分
设置一个ppnode,用于存放parent的父节点
若旋转一部分时,跟ppnode相连接,同时也要判断连接到左子树还是右子树
若旋转整棵树时,父节点置NULL,subR作为新的根
右单旋
在a处新增节点,使其高度变为h+1,造成旋转
右单旋的旋转方式:
b作为60的左边,60作为30的右边,30变成整棵树的根
右单旋h与左单旋一样,都有h为1、2、3的三种情况,只不过右单旋的插入节点在a处,其他的条件都是相同的
右单旋跟左单旋思想相同,
只不过把b作为60的左子树,再把60作为30的右子树
同样考虑父节点问题以及旋转整棵树或者部分子树旋转问题
在insert中判断左右单旋的条件
当parent的平衡因子为2并且cur的平衡因子为1时,为左单旋
当parent的平衡因子为-2并且cur的平衡因子为-1时,为右单旋
双旋转
抽象图
当h=0时,60作为新增节点
当h==1时,60的左右子树新增都会引用旋转
假设在左子树处新增节点
若h==2时
a/d是x/y/z中的任意一种
b/c的孩子位置的任意一点插入节点,都会引发旋转
左右双旋
当h==2时, 假设在b的右子树插入节点
将30进行左旋:30是parent的左子树
将b作为30的右子树,将30作为60的左子树,将60作为90的左子树
将60进行右旋:60作为整棵树新的根
将60的右子树作为90的左子树,将90作为60的右子树
假设在c的右子树插入新增节点
新增节点插入在b和c节点,各个位置的平衡因子是不一样的
当h=0时,左右双旋后,平衡因子与上述两个也是不同的
当subLR即60节点处的平衡因子为-1时,说明在b处插入新增节点,
双旋后 subl的平衡因子为0,subLR的平衡因子为0,parent的平衡因子为1
当subLR即60节点处的平衡因子为1时,说明在c处插入新增节点,
双旋后 subl的平衡因子为-1,subLR的平衡因子为0,parent的平衡因子为0
当subLR即60节点处的平衡因子为0时,说明在60即为新增节点,
双旋后 subl的平衡因子为0,subLR的平衡因子为0,parent的平衡因子为0
整体代码
#include<iostream>
using namespace std;
template<class K, class V>
class AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv;//当前节点值
int _bf;//平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_kv(kv),
_bf()
{
}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;//用于记录cur的前一个节点
Node* 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 false;
}
}
cur = new Node(kv);
//再次判断parent当前节点值与插入值大小
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
//cur的上一个节点即为 刚才的记录cur前一个节点的parent
cur->_parent = parent;
//更新平衡因子
while (parent)
{
//若插入节点在parent的右子树
if (cur == parent->_right)
{
parent->_bf++;
}
//若插入节点在parent的左子树
else
{
parent->_bf--;
}
if (parent->_bf == 1 || parent->_bf == -1)
{
//继续向上更新
parent = parent->_parent;
cur = cur->_parent;
}
//平衡因子为0,不需要向上更新
else if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//旋转
//1.让这颗子树平衡 2.降低子树高度
if ( parent->_bf == 2&&cur->_bf == 1 )//左单旋
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)//右单旋
{
RotateR(parent);
}
else if(parent->_bf==-2&&cur->bf==-1)//双旋
{
RotateLR(parent);
}
//旋转后整颗树已经平衡了,就不需要在继续了
break;
}
}
return true;
}
private:
void RotateL(Node* parent)//左单旋
{
Node* subR = parent->_right;
Node* subRL = subR->left;
parent->_right = subRL;
if (subRL != nullptr)
{
subRL->_parent = parent;
}
Node* ppnode = parent->_parent;//记录parent的前一个节点
subR->left = parent;
parent->_parent = subR;
if (ppnode == nullptr)//说明parent是根即代表整棵树
{
_root = subR;//subR作为新的根
_root->_parent = nullptr;//subR的父节点指向原来的parent,所以要置nullptr
}
else//说明旋转的是一部分,所以要跟ppnode相连接
{
if (ppnode->_left == parent)//若连接在左子树上
{
ppnode->_left = subR;
}
else//若连接在右子树上
{
ppnode->_right = subR;
}
subR->_parent = ppnode;//将subR父节点置为ppnode
}
parent->_bf = subR->_bf = 0;//平衡因子都为0
}
void RoateR(Node* parent)//右单旋
{
Node* subL = parent->_left;
subLR = subL->_right;
parent->_left = subLR;
if (subLR != nullptr)
{
subLR->_parent = parent;
}
Node* ppnode = parnet->_parent;//记录parent的父节点
subL->_right = parent;
parent->_parent = subL;
if (ppnode == nullptr)//若旋转整棵树
{
_root = subL;
_root->_parent = nullptr;
}
else//若旋转整棵树的部分子树
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;//使subL的父节点为ppnode
}
parent->_bf = subL->_bf = 0;
}
void RotateLR(Node* parent)//左右双旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;//记录平衡因子,在后续单旋会置为0
//先对parent的左子树进行左单旋
RotateL(parent->_left);
//再对当前根进行右单旋
RotateR(parent);
if (bf == -1)//h==2时,在b处插入节点
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)//h==2时,在c处插入节点
{
subL ->_bf = -1;
subLR ->_bf= 0;
parent->_bf = 0;
}
else if (bf == 0)//当h==0时,60作为新增节点
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}
}
private:
Node* _root = nullptr;
};