当前位置: 首页 > news >正文

AVL树如何维持平衡

1.AVL树的特性

二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查 找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。

一棵AVL树是空树,或者是具有以下性质的二叉搜索树

-它的左右子树都是AVL树

-左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

用右子树减左子树高度表示左右子树高度之差(平衡因子),下图用蓝色表示节点的平衡因子,如图为一棵AVL树

 因为要控制平衡因子,AVL树节点相比于普通二叉树节点增加了:平衡因子、父节点指针(便于找到父节点控制平衡因子),模拟AVL树节点的定义如下

template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& val): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _val(val), _bf(0){}AVLTreeNode<T>* _pLeft;// 该节点的左孩子AVLTreeNode<T>* _pRight; // 该节点的右孩子AVLTreeNode<T>* _pParent; // 该节点的双亲T _val; // 该节点储存的数据  int _bf; // 该节点的平衡因子
};

 

2.AVL插入时如何维持平衡

AVL树插入时首先要遵循二叉搜索树的规则,找到对应插入位置,注意节点_pParent的链接

2.1找到插入位置插入并链接 

Node* newnode = new Node(x);
Node* cur = _root;
Node* parent = nullptr;if (_root == nullptr)
{_root = newnode;return true;
}
//使用cur找到插入位置
while (cur)
{if (cur->_val == x){return false;}else if (cur->_val < x){parent = cur;cur = cur->_pRight;}else if (cur->_val > x){parent = cur;cur = cur->_pLeft;}
}//链接节点
if (x < parent->_val)
{parent->_pLeft = newnode;
}
else
{parent->_pRight = newnode;
}
newnode->_pParent = parent;
cur = newnode;

 在插入前,这棵树就是一块AVL树遵循AVL树的规则,在插入后可能会破坏规则,就要继续向祖先更新、查看平衡因子。

2.2更新平衡因子

在插入后parent节点平衡因子存在3种情况,有的情况发现此子树的高度不变就不必向上继续更新

若parent的平衡因子,用一个循环实现向上更新

更新后平衡因子存在以下几种情况

1.平衡因子 == 0

说明parent插入前不平衡,插入在短的那边,插入后平衡了,插入后高度不变不需要往上更新

2.平衡因子 == 1或-1

说明parent插入前平衡,插入后不左右子树高度差改变的,那parent所在树高度更新,需继续往上更新

3.parent的平衡因子 == 2或-2

说明parent插入前平衡因子 == 1 或 -1,插入在长的那边了,加剧了parent的不平衡,此时已经违反规则,需要旋转处理调整

while (parent)
{//使用循环向上更新//更新平衡因子if (cur == parent->_pLeft){parent->_bf--;}else if (cur == parent->_pRight){parent->_bf++;}//继续向上更新//若已经更新到根,停止if (parent == nullptr){break;}//1.若此时parent已经平衡(==0),说明插入节点使子树平衡,并没有增加子树高度,不用往上更新if (parent->_bf == 0){break;}//2.若此时parent为弱平衡(_bf == -1/1),说明插入节点使原本平衡的树高度更新,需继续往上更新else if (parent->_bf == -1 || parent->_bf == 1){}//3.若此时parent已经失衡(_bf == -2/2),说明插入节点使原本弱平衡的树加剧失衡,需要旋转处理、调整else if (parent->_bf == -2 || parent->_bf == 2){//单独的一边高(subLL、subRR高),单旋if (parent->_bf == -2 && parent->_pLeft->_bf == -1){RotatoR(parent);}else if (parent->_bf == 2 && parent->_pRight->_bf == 1){RotatoL(parent);}//subRL、subLR高,双旋。例:先将subR子树旋转为subRR高的情况,再使用单次左旋else if (parent->_bf == -2 && parent->_pLeft->_bf == 1){RotatoLR(parent); }else if (parent->_bf == 2 && parent->_pRight->_bf == -1){RotatoRL(parent);}//旋转后这棵子树高度并没有增加,不向上继续更新break;}else{assert(false);}//迭代,继续向上更新cur = parent;parent = parent->_pParent;}

旋转最后得到的结果:

1.遵循搜索树的规则

2.控制平衡,降低高度

而旋转时分为以下几种情况

2.3旋转调整

2.1.1.subRR/subLL长的时候树的旋转调整

如图,若插入在subRR处,parent节点的平衡因子违反了规则,需要调整此子树使之符合规则。

若插入在subLL处,与插入在subRR处类似

下图中a、b、c为抽象的树,h为抽象的树的高度,h = 0时表示空

思想:将parent及其左子树链接到subR的左边使parent子树高度与subRL一样高

具体操作为将parent链接到subR的左边,将subRL链接到parent的右边

代码实现如下,记得要更新平衡因子

	//单次左旋,适用于subRR长的情况//思想:将原来根放到subR的左边使parent子树高度与subRL一样高void RotatoL(Node* parent){Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;Node* parentParent = parent->_pParent;//先链接节点if (subRL != nullptr)subRL->_pParent = parent;parent->_pRight = subRL;parent->_pParent = subR;subR->_pLeft = parent;subR->_pParent = parentParent;if (parentParent == nullptr){//若parentParent为空则原Parent为整个树的根_root = subR;}else{if (subR->_val < parentParent->_val){parentParent->_pLeft = subR;}else if (subR->_val > parentParent->_val){parentParent->_pRight = subR;}}//再更新平衡因子parent->_bf = subR->_bf = 0;}

 

2.1.2.subRL/subLR长的时候的调整

如图,插入节点后subRL长,此时无法像上面那样使用左旋使subRR与subRL链接到parent右边树一样高

若插入在subLR处,调整方法类似

图1.subRL长时的插入

这时我们可以想办法旋转使subRR变长,我们将subRL再具体细分,h为抽象树的高度,h == 0 时表示40为新插入节点

这时我们可以先调整 subR为根的子树使用一次旋转使得subR所在子树较长,变为subRR长的情况可以单次旋转调整,最后再单次右旋

整体旋转方法如下图

记得更新平衡因子,若初始为b长,parent最后平衡因子为0,subR最后平衡因子为1;若初始为c长parent最后平衡因子为-1,subR最后平衡因子为0;若subRL为新插入节点,则h == 0则a、b、c、d都为空,parent和subR最后平衡因子都为0

 代码如下

//先右旋再左旋,适用于subRL高的情况
//思想:先将subR子树旋转为subRR高的情况,再使用单次左旋
void RotatoRL(Node* parent)
{Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;//可能subRLL长或subRLR长,通过记录subRL原来的bf调整最后bfint bf = subRL->_bf;//两次旋转,旋转后平衡因子有误RotatoR(subR);RotatoL(parent);//再更新平衡因子subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;}else{subR->_bf = 0;parent->_bf = 0;}
}

3.插入的整体代码

 

bool Insert(T& x)
{Node* newnode = new Node(x);Node* cur = _root;Node* parent = nullptr;if (_root == nullptr){_root = newnode;return true;}//使用cur找到插入位置while (cur){if (cur->_val == x){return false;}else if (cur->_val < x){parent = cur;cur = cur->_pRight;}else if (cur->_val > x){parent = cur;cur = cur->_pLeft;}}//链接节点if (x < parent->_val){parent->_pLeft = newnode;}else{parent->_pRight = newnode;}newnode->_pParent = parent;cur = newnode;while (parent){//使用循环向上更新//更新平衡因子if (cur == parent->_pLeft){parent->_bf--;}else if (cur == parent->_pRight){parent->_bf++;}//继续向上更新//若已经更新到根,停止if (parent == nullptr){break;}//1.若此时parent已经平衡(==0),说明插入节点使子树平衡,并没有增加子树高度,不用往上更新if (parent->_bf == 0){break;}//2.若此时parent为弱平衡(_bf == -1/1),说明插入节点使原本平衡的树高度更新,需继续往上更新else if (parent->_bf == -1 || parent->_bf == 1){}//3.若此时parent已经失衡(_bf == -2/2),说明插入节点使原本弱平衡的树加剧失衡,需要旋转处理、调整else if (parent->_bf == -2 || parent->_bf == 2){//单独的一边高(subLL、subRR高),单旋if (parent->_bf == -2 && parent->_pLeft->_bf == -1){RotatoR(parent);}else if (parent->_bf == 2 && parent->_pRight->_bf == 1){RotatoL(parent);}//subRL、subLR高,双旋。例:先将subR子树旋转为subRR高的情况,再使用单次左旋else if (parent->_bf == -2 && parent->_pLeft->_bf == 1){RotatoLR(parent); }else if (parent->_bf == 2 && parent->_pRight->_bf == -1){RotatoRL(parent);}//旋转后这棵子树高度并没有增加,不向上继续更新break;}else{assert(false);}//迭代,继续向上更新cur = parent;parent = parent->_pParent;}return true;
}//单次左旋,适用于subRR长的情况
//思想:将原来根放到subR的左边使parent子树高度与subRL一样高
void RotatoL(Node* parent)
{Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;Node* parentParent = parent->_pParent;//先链接节点if (subRL != nullptr)subRL->_pParent = parent;parent->_pRight = subRL;parent->_pParent = subR;subR->_pLeft = parent;subR->_pParent = parentParent;if (parentParent == nullptr){//若parentParent为空则原Parent为整个树的根_root = subR;}else{if (subR->_val < parentParent->_val){parentParent->_pLeft = subR;}else if (subR->_val > parentParent->_val){parentParent->_pRight = subR;}}//再更新平衡因子parent->_bf = subR->_bf = 0;}//单次右旋,与左旋思想类似
void RotatoR(Node* parent)
{Node* subL = parent->_pLeft;Node* subLR = subL->_pRight;Node* parentParent = parent->_pParent;if (subLR != nullptr)subLR->_pParent = parent;parent->_pLeft = subLR;parent->_pParent = subL;subL->_pRight = parent;subL->_pParent = parentParent;if (parentParent == nullptr){_root = subL;}else{if (parent == parentParent->_pLeft){parentParent->_pLeft = subL;}else if (parent == parentParent->_pRight){parentParent->_pRight = subL;}}//再更新平衡因子parent->_bf = subL->_bf = 0;
}//先右旋再左旋,适用于subRL高的情况
//思想:先将subR子树旋转为subRR高的情况,再使用单次左旋
void RotatoRL(Node* parent)
{Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;//可能subRLL长或subRLR长,通过记录subRL原来的bf调整最后bfint bf = subRL->_bf;//两次旋转,旋转后平衡因子有误RotatoR(subR);RotatoL(parent);//再更新平衡因子subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;}else{subR->_bf = 0;parent->_bf = 0;}
}//先左旋再右旋
void RotatoLR(Node* parent)
{Node* subL = parent->_pLeft;Node* subLR = subL->_pRight;int bf = subLR->_bf;//两次旋转,旋转后平衡因子有误RotatoL(subL);RotatoR(parent);//再更新平衡因子subLR->_bf = 0;if (bf == 1){subL->_bf = -1;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;parent->_bf = 1;}else{subL->_bf = 0;parent->_bf = 0;}
}

 在实现后可以中序遍历整棵树,检查是否为二叉搜索树。并且检查其平衡因子是否符合规则,确定其为平衡树。

//获取高度
int Height()
{return _Height(_root);
}
//判断是否为平衡树
bool IsBalanceTree()
{return _IsBalanceTree(_root);
}//判断是否为平衡树
bool _IsBalanceTree(Node* root)
{// 空树也是AVL树if (root == nullptr){return true;}int leftTreeHeight = _Height(root->_pLeft);int rightTreeHeight = _Height(root->_pRight);int diff = rightTreeHeight - leftTreeHeight;//验证root是不是平衡树if (root->_bf == diff && diff >= -1 && diff <= 1){//验证其左右子树是不是平衡树return _IsBalanceTree(root->_pLeft) && _IsBalanceTree(root->_pRight);}else{return false;}}	//获取高度
int _Height(Node* root)
{if (root == nullptr){return 0;}int leftTreeHeight = _Height(root->_pLeft);int rightTreeHeight = _Height(root->_pRight);return (leftTreeHeight > rightTreeHeight) ? leftTreeHeight + 1 : rightTreeHeight + 1;
}


http://www.mrgr.cn/news/47493.html

相关文章:

  • 51单片机的无线通信智能车库门【proteus仿真+程序+报告+原理图+演示视频】
  • k8s网络通信
  • 【网络安全 | Java代码审计】华夏ERP(jshERP)v2.3
  • 5个免费ppt模板网站推荐!轻松搞定职场ppt制作!
  • HTML5+Css3(背景属性background)
  • 【firefox】火狐浏览器、火狐浏览器驱动、selenium版本号对应关系
  • rocky9 samba共享
  • MinIO分片上传超大文件(纯服务端)
  • 哪种隔音方式最好?小户型如何隔音?
  • Java 快速排序
  • 基于SpringBoot+Vue+Uniapp微信小程序的电子竞技信息交流平台设计与实现
  • 《花100块做个摸鱼小网站! 》第七篇—谁访问了我们的网站?
  • Biomamba求职| 国奖+4篇一作SCI
  • 路径跟踪之导航向量场——二维导航向量场
  • 239. 滑动窗口最大值
  • 喜讯!迈威通信TSN产品通过“时间敏感网络(TSN)产业链名录计划”评测,各项指标名列前茅
  • Java之方法
  • 【浏览器】如何正确使用Microsoft Edge
  • 攻防世界(CTF)~Reverse-easyRE1
  • Spark练习json文件-统计问答数据