【数据结构】AVL树和旋转
本章要分享的内容是AVL树，所有代码会放在最后。
目录
在之前我们接触过二叉树和二叉搜索树
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率便会降低。
1.AVL树的概念
AVL树的要求是一颗树中的左右高度差的绝对值不超过1，包括这颗树中所有的子树。
上图为简单的AVL树，左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。
平衡因子也就是右树减去左树的高度，格局上图中所标识的0、1、-1即为平衡因子。
引入平衡因子的概念意在可以简单的判断这棵树是否为AVL树，树中的平衡因子若都为0、1、-1那即为AVL树。
注意：平衡因子只是一种AVL树的实现方式，并不是必须的。
所以在了解这样的树之后它的时间复杂度为O(logN)，因为AVL树控制了高度差，所以插入的数据基本上都是在最后两层，与最开始我们接触过的完全二叉树相似。
2.AVL树的实现
2.1结点的设计
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv;
int _bf; // balance factor
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};在这里我的代码是将每个结点存放了五个值，分别为左右结点和父亲节点（其都为<key,value>的结构）、pair值、平衡因子。
template<class K,class V>
struct AVLTree
{
typedef AVLtreeNode<K, V> Node;
public:
private:
Node* _root = nullptr;
};将以上AVL树的结点都重定义为Node方便我们后续的使用，并且使用重定义的结点定义根节点。
我们只需在public中添加我们需要对AVL树的操作即可。
2.2插入
AVL的插入与二叉搜索树的插入逻辑大致上相同，但是还是有一点不同
这里的代码只是为了梳理逻辑，并不完全，后续还会涉及到结点旋转的问题。
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)//如果根节点为空，就让根节点成为插入的第一个结点
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;//新开结点parent
Node* cur = _root;//新开结点cur，并初始化为根结点
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);//走到当前位置cur为空
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
return true;
}可以看到逻辑上分为两个部分，一个是cur的结点中有值，一个是cur结点没有值；
这里插入时使用的是三叉链表的结构
?2.3更新平衡因子
AVL树中可以引入平衡因子来实现，并且不能超过1的绝对值，所以我们需要讨论如何更新平衡因子。
新增结点可能会影响祖先
1.如果子树的高度不变，就不会继续向上影响祖先
2.如果子树高度变化，就会继续向上影响祖先
首先新增的结点可能会影响祖先，不会影响到旁支结点。?
如果新插入的结点在如下红色圆圈的位置，那么 值为8的结点的平衡因子要从1更新为0
如果我们没有将结点插入在左树，而是插入在右树（如下图）
此时结点为9的高度发生变化，平衡因子也发生变化（p为parent，c为cur）
9的高度发生变化，它的祖先节点的平衡因子也发生变化
就这样一路更新上去每个结点的平衡因子都会更新。
但是我们发现8这个结点的平衡因子已经出现了问题，它的绝对值超过了1，所以我们需要对这颗子树进行处理。
那我们有如下结论
1.新增结点在左子树，父亲的平衡因子减一（bf--），如下图
?2.新增结点在右子树，亲的平衡因子加一（bf++），如下图
那么如何将平衡因子继续向下更新呢？
有如下判断方法
1.在更新后，父亲的平衡因子等于0，父亲所在的子树高度不变，就不用继续向上更新，插入结束。
ps:再插入节点前，父亲的平衡因子等于 1 或者?-1 ，一边高一边低，新插入的结点填上了低的一部份
2.如果父亲的平衡因子更新之后等于 1?或者? -1，父亲所在的高度变化，必须继续向上更新
ps:插入结点前，父亲的平衡因子两边一样高，插入导致高度变化
代码如下
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 < key)//判断我们定义的k,v结构中所在树中的k是否小于我们所插入的key
{
parent = cur;
cur = cur->_right;//如果key大于树中结点的值就走右边
}
else if (cur->_kv.first > key)
{
parent = cur;
cur = cur->_left;//key小于树中结点的值就走左边
}
else
{
return false;//相等时结束
}
}
//运行至当前位置时则说明cur为空
cur = new Node(kv);
if(parent->_kv.first < key)
{
parent->_right = cur;
cur->_parent = parent;
}
else if (parent->_kv.first > key)
{
parent->_left = cur;
cur->_parent= parent;
}
while (parent)
{
//更新平衡因子
if (cur == parent->_left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;//注意cur和parent都是指针，这里是改变指针的指向
parent = parent->_parent;
}
else if(parent->_bf == 2 || parent->_bf == -2)
{
//旋转调整
}
else
{
assert(false);
}
}
return true;
}3.如果父亲的平衡以你在更新后，等于 2 或者 -2 ，父亲所在的子树违反规则，需要旋转调整处理
可以看到这里的平衡因子出现了2，违反了AVL树的规则，这时就要进行旋转操作
首先我们要明确旋转的目的
1.使树的左右均衡
2.保持搜索树的规则
所以我们可以对以上树进行以下旋转
2.3.1左单旋
此树旋转较为简单，只需要用二叉搜索树的知识来判断谁来做父亲节点
也就是将2的左树（为空），放到了1的右树，同时将1又作为2的左树
如果我们增加一些难度，将树多添加一些结点
我们对其进行旋转后会得到以下结构图
这里的结点13比9大，但是比15小，13更是和添加到9的左树当中
和上面三个结点的树相似，将15的左结点13变成了9的右节点，同时将结点为9的树一并作为了15的左子树。
这样的旋转规律就被称为左单旋。
如下都是左单旋的抽象图。
抽象图就代表了一类问题的解决的大体思想，实际的h有很多情况，一一列举出来显然是非常困难。
以下是左单旋调整的代码
，图为以下代码中结构的命名。
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
}?当如上代码运行之后，结构会更新成下图所示
此时我们还需要处理parent和根结点，完整的代码如下
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
Node* parentPARENT = parent->_parent;
parent->_parent = subR;
if (subR)
subR->_parent = parent;
if (_root = parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentPARENT->_left == parent)
{
parentPARENT->_left = subR;
}
else
{
parentPARENT->_right = subR;
}
subR->_parent = parentPARENT;
}
parent->_bf = subR->_bf = 0;
}上面代码中我们不仅要考虑到根节点_root是否为空的情况，还需要考虑到如何保留并找到根节点，如何对根节点进行旋转和交换，此时我们需要新开一个节点方便对旋转的结点进行操作
?同时，还需要保留三叉链表的思想，以防止我们修改指针的指向。
2.3.2右单旋
可以看到结构图和左单旋只是左右互换，并没有太多本质上的差异，所以代码的逻辑也没有特别困难
代码如下
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
Node* parentPARENT = parent->_parent;
parent->_parent = subR;
if (subR)
subR->_parent = parent;
if (_root = parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentPARENT->_left == parent)
{
parentPARENT->_left = subL;
}
else
{
parentPARENT->_right = subL;
}
subL->_parent = parentPARENT;
}
parent->_bf = subL->_bf = 0;
}?我们旋转的最终目的是要将不平衡的树变成平衡树，同时降低了树的高度
此时我们就可以带入到更新平衡因子的代码中
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 < key)//判断我们定义的k,v结构中所在树中的k是否小于我们所插入的key
{
parent = cur;
cur = cur->_right;//如果key大于树中结点的值就走右边
}
else if (cur->_kv.first > key)
{
parent = cur;
cur = cur->_left;//key小于树中结点的值就走左边
}
else
{
return false;//相等时结束
}
}
//运行至当前位置时则说明cur为空
cur = new Node(kv);
if(parent->_kv.first < key)
{
parent->_right = cur;
cur->_parent = parent;
}
else if (parent->_kv.first > key)
{
parent->_left = cur;
cur->_parent= parent;
}
while (parent)
{
//更新平衡因子
if (cur == parent->_left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;//注意cur和parent都是指针，这里是改变指针的指向
parent = parent->_parent;
}
else if(parent->_bf == 2 || parent->_bf == -2)
{
//旋转调整
if (parent->_bf == 2 && cur->_bf == 1)//左单旋
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
break;
}
else
{
assert(false);
}
}
return true;
}2.3.3.双旋
当我们的插入出现了以下情况时该如何旋转呢？
可以看到我们新插入的结点在在60结点的左树，并且在旋转之后平衡因子显示并不能使这棵树为AVL树，所以左单旋无法解决问题。
所以我们需要对子树b进行拆解，拆解后图示如下
我们拆解后的树的特点使a和d都是高度为h的树（h>0）;
b和c是高度为h-1的AVL树or空树（h>=1）;
同样的我们也需要分情况来讨论分解的情况
1.h==0时，如下图
?2.当h==1时，如下图
?3.当h==2时，如下图
a和d结点可能时x、y、z中的任意一个子树，有3*3=9中可能；
那么插入的位置可以是b和c结点的任意位置，有四个可能插入位置；
合计组合有9*4=36种场景
当然我们上面也说过有无数种变形场景，所以我们在这里只需写出结论
双旋：
1.以90结点为旋转点进行右单旋
2.以30结点为旋转点进行左单旋?
以下图双旋为例
?先进行右单旋
?变成一边高后的树后在进行左单旋
这样平衡因子符合条件。
上述过程是在b结点的树插入，在c结点插入原理相同
同样可以达到AVL树的条件。?
?接下来用代码展示右左双旋的过程
此图是对各个结点的命名和平衡因子的标识
void RotateRL(Node* parent)//右左双旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;//记录平衡因子；
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)//当平衡因子为0时，subRL自己就是新增的结点
{
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (bf == -1)
{
//subL的左子树新增
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1)
{
//subRL的右子树新增
parent->_bf = -1;
subRL->_bf = 0;
subR->_bf = 0;
}
else//此时不符合树的规则
{
assert(false);
}
}如上代码参考上述右左双旋结构图变化。
3.AVL树测试
以下是对以上实现的AVL树的测试代码
int main()
{
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(make_pair(e, e));
}
t.InOrder();
return 0;
}我们先循环遍历插入a数组种的内容，并用先序遍历
插入成功
这只能证明我们的插入没有问题，接下来我们需要测试平衡因子是否也会调整。
以下为判断平衡因子的更细
bool IsBalance()
{
return _IsBalance(_root);
}
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 _IsBalance(Node* root)//
{
if (root == nullptr)//树为空返回空
return true;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
if (rightHeight - leftHeight != root->_bf)//右树高度和左树高度差并不等于bf就抛异常
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
在main函数种调用并输出判平衡函数，观察值为1说明平衡。
我们不妨设置大量的数据再进行测试
?
int main()
{
const int N = 100;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand());
}
AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
}
cout << t.IsBalance() << endl;
}我们设置了100个随机数并插入
可以看到平衡因子异常已经被检测出来了。
我们也可以观察是在插入谁的时候出现了问题，如下图
可以看到结果中我们在插入14604的时候出现了问题?
?
4.全部代码
?4.1.AVL.h
AVL.h中包括结点的设计，插入，左单旋，右单旋，右左双旋，先序遍历，中序边路，树的高度计算和结点的更新
#pragma once
#include<assert.h>
#include<vector>
#include<map>
#include<stdlib.h>
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv;
int _bf; // balance factor
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};
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;
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 (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
while (parent)
{
if (cur == parent->_left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
if (parent->_bf == 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);
}
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);
}
// 1、旋转让这颗子树平衡了
// 2、旋转降低了这颗子树的高度，恢复到跟插入前一样的高度，所以对上一层没有影响，不用继续更新
break;
}
else
{
assert(false);
}
}
return true;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (subRL)
subRL->_parent = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
parent->_bf = subR->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
subL->_bf = parent->_bf = 0;
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
// subRL自己就是新增
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (bf == -1)
{
// subRL的左子树新增
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1)
{
// subRL的右子树新增
parent->_bf = -1;
subRL->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false);
}
}
void RotateLR(Node* parent)
{
//...
RotateL(parent->_left);
RotateR(parent);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
bool IsBalance()
{
return _IsBalance(_root);
}
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 _IsBalance(Node* root)
{
if (root == nullptr)
return true;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
if (rightHeight - leftHeight != root->_bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
private:
Node* _root = nullptr;
};4.2.test.h?
?测试树的插入、节点更新和旋转
#include<iostream>
using namespace std;
#include"AVL.h"
//int main()
//{
// map<string, string> dict;
// dict.insert(make_pair("left", "左边"));
// dict.insert(make_pair("left", "剩余"));
// dict.insert(make_pair("left", "左边"));
//
// for (auto& kv : dict)
// {
// cout << kv.first << ":" << kv.second << endl;
// }
//
//
//
// return 0;
//}
/*int main()
{
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(make_pair(e, e));
}
t.InOrder();
cout << t.IsBalance() << endl;
return 0;
}*/
int main()
{
const int N = 100;
vector<int> v;
v.reserve(N);
//srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand());
cout << v.back() << endl;
}
AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
cout << "Insert:" << e << "->" << t.IsBalance() << endl;
}
cout << t.IsBalance() << endl;
}
?以上是有关AVL树的内容，因本人水平有限，有误之处请指出批评，如果对您有所帮助还请三连支持，感谢您的阅读。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！