【c++篇】：探秘AVL树平衡旋转原理--维持树的高度平衡之道
✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：c++篇–CSDN博客
前言
在之前的文章中，我们已经对二叉搜索树以及容器
map和set有了简单的了解，这几个容器有个
共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中
插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此
map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。而平衡树有AVL树和红黑树，本篇文章将详细讲解AVL树是如何实现平衡。
一.AVL树的性质和概念
AVL树是一种高度平衡的二叉搜索树，其特点在于通过保持树的高度平衡来优化查找，插入和删除的效率。
定义和性质
- 定义：AVL树是由两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明的。它是一种自平衡的二叉搜索树，其中任一节点的两个子树的高度最大差别为1，因此它也被称为平衡二叉搜索树。
- 性质：
- AVL树可以是空树。
- AVL树的左右子树都是AVL树。
- AVL树的左右子树高度之差（简称平衡因子）的绝对值不超过1。
节点定义和平衡因子
在AVL树中，每个节点除了包含键值（key）和值（value）外，还包含一个指向其父节点的指针以及一个平衡因子（balance factor）。平衡因子用于衡量节点的左右子树的高度差，其值可以是-1、0或1。具体地：
- 如果左子树比右子树高一层，平衡因子为-1。
- 如果左右子树一样高，平衡因子为0。
- 如果右子树比左子树高一层，平衡因子为1。
二.模拟实现
基本框架
-
代码实现：
#include<iostream> #include<utility> #include<assert.h> using namespace std; //AVL树节点类的封装 template<class K, class V> class AVLTreeNode { public: //构造函数 AVLTreeNode(const pair<K,V>& kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} //成员变量 pair<K,V> _kv; //键值对 AVLTreeNode* _left; //左子节点指针 AVLTreeNode* _right; //右子节点指针 AVLTreeNode* _parent; //父节点指针 int _bf; //平衡因子 }; //AVL树类的封装 template<class K, class V> class AVLTree { typedef AVLTreeNode<K,V> Node; public: AVLTree() :_root(nullptr) {} //...其他成员函数 private: Node* _root; //根节点 };
AVL树的插入
在AVL树中插入新节点的过程和二叉搜索树中插入结点的过程类似，但需要在插入后检查并调整树的平衡性，使其每个节点的平衡因子都保持在(-1~1)，具体步骤如下：
- 1.按照二叉搜索树的规则插入新节点
- 2.从插入节点的父节点开始，沿着插入路径向上更新祖先节点的平衡因子
- 如果某个节点的平衡因子变为2/-2，说明该节点的子树已经失衡，需要进行续传调整
具体如图所示：
代码实现：
bool insert(const pair<K,V>& kv){
//插入过程
if(_root==nullptr){
_root=new Node(kv);
return true;
}
Node* parent=nullptr;
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);
if(parent->_kv.first<kv.first){
parent->_right=cur;
}
else{
parent->_left=cur;
}
cur->_parent=parent;
//检查平衡因子过程
while(parent){
if(cur==parent->_left){
parent->_bf--;
}
if(cur==parent->_right){
parent->_bf++;
}
if(parent==0){
break;
}
else if(parent->_bf==1||parent->_bf==-1){
cur=parent;
parent=parent->_parent;
}
else if(parent->_bf==2||parent->_bf==-2){
//四种调整情况
//左单旋
if(parent->_bf==2&&cur->_bf==1){
RotateL(parent);
}
//右单旋
if(parent->_bf==-2&&cur->_bf==-1){
RotateR(parent);
}
//右左双旋
if(parent->_bf==2&&cur->_bf==-1){
RotateRL(parent);
}
//左右双旋
if(parent->_bf==-2&&cur->_bf==1){
RotateLR(parent);
}
break;
}
else{
assert(false);
}
}
return true;
}
- 实现原理：
- 插入过程还是和二叉搜索树一样（详细可以看我之前的关于二叉搜索树的文章），如果是空树时，创建根节点，非空树时，找到对应位置插入。注意，这里有一点不同的是插入后要连接插入节点的父节点
- 插入完后就是进行更新平衡因子检查，如果插入节点是父节点的左子节点，父节点的平衡因子就减一，如果是右子节点，父节点的平衡因子就加一。
- 沿着插入路径往上更新平衡因子，当平衡因子为0时，说明左右子树平衡，结束即可；当平衡因子为1/-1时，继续往上更新；当平衡因子时2/-2时，说明左右子树失衡，需要进行旋转调整，而调整有四种情况，分别对应不同的旋转过程
AVL树的旋转
-
1.新插入节点在较高右子树的右侧–右右：左单旋
示例图如下：
-
代码实现：
void RotateL(Node* parent){
Node* cur=parent->_right;
Node* curleft=cur->_left;
Node* ppnode=parent->_parent;
parent->_right=curleft;
if(curleft){
curleft->_parent=parent;
}
cur->_left=parent;
parent->_parent=cur;
if(ppnode){
cur->_parent=ppnode;
if(parent==ppnode->_left){
ppnode->_left=cur;
}
else{
ppnode->_right=cur;
}
}
else{
cur->_parent=nullptr;
_root=cur;
}
cur->_bf=paent->_bf=0;
}
-
实现原理：
- 获取参数节点的右子节点cur，获取参数节点的父节点ppnode，获取节点cur的左子节点curleft
- 将参数节点parent的右子节点指针指向节点curleft，如果节点curleft不为空，父节点指针指向参数节点parent
- 节点cur的左子节点指针指向参数节点parent，参数节点的父结点指针指向节点cur
- 如果父节点ppnode不为空，则交换两个指针的指向，如果为空，说明参数节点就是根节点，旋转后需要将节点cur更新为新的根节点
- 最后就是将节点cur和parent的平衡因子置为0
-
2.新插入节点在较高左子树的左侧–左左：右单旋
示例图如下：
代码实现：
void RotateR(Node* parent){
Node* cur=parent->_left;
Node* curright=cur->_right;
Node* ppnode=parent->_parent;
parent->_left=curright;
if(curright){
curright->_parent=parent;
}
cur->_right=parent;
parent->_parent=cur;
if(ppnode){
if(ppnode->_left==parent){
ppnode->_left=cur;
cur->_parent=ppnode;
}
else{
ppnode->_right=cur;
cur->_parent=ppnode;
}
}
else{
cur->_parent=nullptr;
_root=cur;
}
cur->_bf=parent->_bf=0;
}
-
实现原理：
- 获取参数节点的左子节点cur，获取参数节点的父节点ppnode，获取节点cur的右子节点curright
- 将参数节点parent的左子节点指针指向节点curright，如果节点curright不为空，父节点指针指向参数节点parent
- 节点cur的右子节点指针指向参数节点parent，参数节点的父结点指针指向节点cur
- 如果父节点ppnode不为空，则交换两个指针的指向，如果为空，说明参数节点就是根节点，旋转后需要将节点cur更新为新的根节点
- 最后就是将节点cur和parent的平衡因子置为0
-
3.新插入节点在较高右子树的左侧–右左：右左双旋
示例图如下：
-
代码实现：
void RotateRL(Node* parent){ Node* cur=parent->_right; Node* curleft=cur->_left; int bf=curleft->_bf; RotateR(parent->_right); RotateL(parent); //旋转后平衡因子调整三种情况 //对应a图 if(bf==0){ cur->_bf=0; curleft->_bf=0; parent->_bf=0; } //对应b图 else if(bf==1){ cur->_bf=0; curleft->_bf=0; parent->_bf=-1; } //对应c图 else if(bf==-1){ cur->_bf=1; curleft->_bf=0; parent->_bf=0; } else{ assert(false); } } -
实现原理：
- 右左双旋不同于简单的右单旋，再进行一次右单旋后，还要再进行一次左单旋
- 右左双旋有三种情况，可以根据上图和代码来看
- 当节点curleft的平衡因子是0时，旋转后平衡因子都为0
- 当节点curleft的平衡因子是1时，旋转后parent节点的平衡因子变为-1，其他为0
- 当节点curleft的平衡因子是-1时，旋转后cur节点的平衡因子变为1，其他为0
-
4.新插入节点在较高左子树的左侧–左右：左右双旋
示例图如下：
-
代码实现：
void RotateLR(Node* parent){ Node* cur=parent->_left; Node* curright=cur->_right; int bf=curright->_bf; RotateL(parent->_left); RotateR(parent); //旋转后平衡因子调整三种情况 //对应a图 if(bf==0){ cur->_bf=0; curright->_bf=0; parent->_bf=0; } //对应b图 else if(bf==-1){ cur->_bf=0; curright->_bf=0; parent->_bf=1; } //对应c图 else if(bf==1){ cur->_bf=-1; curright->_bf=0; parent->_bf=0; } else{ assert(false); } } -
实现原理：
- 左右双旋不同于简单的左单旋，再进行一次左单旋后，还要再进行一次右单旋
- 左右双旋有三种情况，可以根据上图和代码来看
- 当节点curright的平衡因子是0时，旋转后平衡因子都为0
- 当节点curright的平衡因子是1时，旋转后cur节点的平衡因子变为-1，其他为0
- 当节点curright的平衡因子是-1时，旋转后parent节点的平衡因子变为1，其他为0
AVL树的平衡检查
-
代码实现：
//获取高度函数 int Height(){ return _Height(_root); } //检查平衡函数 int IsBlance(){ return _IsBlance(_root); } private: //获取高度子函数 int _Height(Node* root){ if(root==nullptr){ return 0; } int leftheight=_Height(root->_left); int rightheight=_Height(root->_right); return leftheight>rightheight ? leftheight+1 : rightheight+1; } //检查平衡子函数 bool _IsBlance(Node* root){ if(root==nullptr){ return true; } int leftheight=_Height(root->_left); int rightheight=_Height(root->_right); return abs(rightheight-leftheight)<2 &&_IsBlance(root->_left) &&_IsBlance(root->_right); } -
实现原理：
- 因为成员变量根节点
_root是私有成员，不能在类外作为参数使用，所以这里通过两个函数来调用 - 通过左右子树的高度，右子树减去左子树的高度的绝对值小于2时，说明当前节点的左右子树平衡，之后递归调用左右子树判断即可
- 因为成员变量根节点
测试
- 测试代码：
#include"AVLTree.h"
//第一组数据测试
void test1(){
int arr[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
AVLTree<int,int> t;
for(auto e : arr){
t.insert(make_pair(e,e));
cout<<"Insert:"<<e<<"->"<<t.IsBlance()<<endl;
}
}
//第二组数据测试
void test2(){
int arr[]={4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
AVLTree<int,int> t;
for(auto e : arr){
t.insert(make_pair(e,e));
cout<<"Insert:"<<e<<"->"<<t.IsBlance()<<endl;
}
}
//随机大量数据(10000000)测试
void test3(){
const int N=10000000;
vector<int> v;
v.reserve(N);
srand(time(0));
for(size_t i=0;i<N;i++){
v.push_back(i);
}
AVLTree<int,int> t;
for(auto e : v){
t.insert(make_pair(e,e));
}
cout<<t.IsBlance()<<endl;
cout<<t.Height()<<endl;
}
int main(){
//test1();
//test2();
test3();
return 0;
}
-
测试结果：
- 测试结果一：
- 测试结果二：
- 测试结果三：
三.完整代码文件
AVLTree.h文件代码：
#include<iostream>
#include<utility>
#include<assert.h>
#include<vector>
using namespace std;
template<class K, class V>
class AVLTreeNode {
public:
//构造函数
AVLTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
//成员变量
pair<K,V> _kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
int _bf;
};
template<class K, class V>
class AVLTree {
typedef AVLTreeNode<K,V> Node;
public:
AVLTree()
:_root(nullptr)
{}
bool insert(const pair<K,V>& kv) {
if(_root==nullptr){
_root=new Node(kv);
return true;
}
Node* parent=nullptr;
Node* cur=_root;
while(cur){
if(cur->_kv.first<kv.first) {
parent=cur;
cur=cur->_right;
}
else if(cur->_kv.first>kv.first) {
parent=cur;
cur=cur->_left;
}
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){
if(cur==parent->_left){ //新增节点在父节点的左子节点时，父节点的平衡因子减减
parent->_bf--;
}
if(cur==parent->_right){ //新增节点在父节点的右子节点时，父节点的平衡因子加加
parent->_bf++;
}
if(parent->_bf==0){ //当父节点的平衡因子为0时，说明父节点的左右子树平衡
break;
}
else if(parent->_bf==1||parent->_bf==-1){ //当父节点的平衡因子为1后者-1时，继续往上
cur=parent;
parent=parent->_parent;
}
else if(parent->_bf==2||parent->_bf==-2){ //当父节点的平衡因子为2后者-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){
RotateRL(parent);
}
else if(parent->_bf==-2&&cur->_bf==1){
RotateLR(parent);
}
break;
}
else{
assert(false);
}
}
return true;
}
int Height(){
return _Height(_root);
}
bool IsBlance(){
return _IsBlance(_root);
}
private:
int _Height(Node* root){
if(root==nullptr){
return 0;
}
int leftheight=_Height(root->_left);
int rightheight=_Height(root->_right);
return leftheight > rightheight ? leftheight+1 : rightheight+1;
}
bool _IsBlance(Node* root){
if(root==nullptr){
return true;
}
int leftheight=_Height(root->_left);
int rightheight=_Height(root->_right);
if(rightheight-leftheight!=root->_bf){
cout<<"blance factor flase:"<<root->_kv.first<<"->"<<root->_bf<<endl;
}
return abs(rightheight-leftheight)<2
&&_IsBlance(root->_left)
&&_IsBlance(root->_right);
}
//左单旋
void RotateL(Node* parent){
Node* cur=parent->_right;
Node* curleft=cur->_left;
Node* ppnode=parent->_parent;
parent->_right=curleft;
if(curleft){
curleft->_parent=parent;
}
cur->_left=parent;
parent->_parent=cur;
if(ppnode){
if(ppnode->_left==parent){
ppnode->_left=cur;
cur->_parent=ppnode;
}
else{
ppnode->_right=cur;
cur->_parent=ppnode;
}
}
else{
cur->_parent=nullptr;
_root=cur;
}
cur->_bf=parent->_bf=0;
}
//右单旋
void RotateR(Node* parent){
Node* cur=parent->_left;
Node* curright=cur->_right;
Node* ppnode=parent->_parent;
parent->_left=curright;
if(curright){
curright->_parent=parent;
}
cur->_right=parent;
parent->_parent=cur;
if(ppnode){
if(ppnode->_left==parent){
ppnode->_left=cur;
cur->_parent=ppnode;
}
else{
ppnode->_right=cur;
cur->_parent=ppnode;
}
}
else{
cur->_parent=nullptr;
_root=cur;
}
cur->_bf=parent->_bf=0;
}
//右左双旋
void RotateRL(Node* parent){
Node* cur=parent->_right;
Node* curleft=cur->_left;
int bf=curleft->_bf;
RotateR(parent->_right);
RotateL(parent);
if(bf==0){
cur->_bf=0;
curleft->_bf=0;
parent->_bf=0;
}
else if(bf==1){
cur->_bf=0;
curleft->_bf=0;
parent->_bf=-1;
}
else if(bf==-1){
cur->_bf=1;
curleft->_bf=0;
parent->_bf=0;
}
else{
assert(false);
}
}
//左右双旋
void RotateLR(Node* parent){
Node* cur=parent->_left;
Node* curright=cur->_right;
int bf=curright->_bf;
RotateL(parent->_left);
RotateR(parent);
if(bf==0){
cur->_bf=0;
curright->_bf=0;
parent->_bf=0;
}
else if(bf==-1){
cur->_bf=0;
curright->_bf=0;
parent->_bf=1;
}
else if(bf==1){
cur->_bf=-1;
curright->_bf=0;
parent->_bf=0;
}
else{
assert(false);
}
}
private:
Node* _root;
};
以上就是关于平衡树之一的AVL树平衡原理讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
原文地址：https://blog.csdn.net/2301_82347435/article/details/144000566
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！