【C++、数据结构】AVL树模拟实现-创新互联

文章目录
  • 📖 前言
  • 1. AVL树的概念
      • 1.1 二叉搜索树的缺点:
      • 1.2 AVL树的引入:
      • 1.2 AVL树的性质:
  • 2. AVL树的模拟实现
      • 2.1 AVL树结点的定义:
      • 2.2 AVL树的插入:(重点)
        • 2.2.1 插入结点后平衡因子的变化
        • 2.2.2 插入结点后对其他结点衡因子的影响
        • 2.2.3 在不同位置插入情况分析处理
      • 2.3 AVL树的旋转操作:(重点)
        • 2.3.1 左单旋
        • 2.3.2 右单旋
        • 2.3.3 左右双旋
        • 2.3.4 右左双旋
  • 3. 验证AVL树
      • 3.1 严格验证AVL树:

创新互联建站服务项目包括麦积网站建设、麦积网站制作、麦积网页制作以及麦积网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,麦积网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到麦积省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!📖 前言
  • 上一章节我们学习了二叉搜索树,并且模拟实现了二叉搜索树的实现。
  • 在学习完之后我们知道二叉搜索树查找的时间复杂度是〇(N),这里并不是〇(logN) 具体的原因就是要搜索的二叉树并不是非常的平衡。
  • 并不是所有要查找的二叉树都是满二叉树或者是完全二叉树,有可能是单边树的情况,平均下来的时间复杂度就是〇(N)。

前情回顾:二叉搜索树 👉传送门

本章我们将学习AVL树,来解决上一章节二叉搜索树的查找时二叉树不平衡的问题,搬好小板凳准备开讲啦~~~ 🙋 🙋 🙋 🙋 🙋


1. AVL树的概念 1.1 二叉搜索树的缺点:
  • 二叉搜索树虽可以减少查找的效率,但如果数据有序或接近有序时二叉搜索树将退化为单边树
  • 这时查找元素相当于在顺序表中搜索元素,效率低下
  • 而且如果二叉树查找是用递归实现的话,那么这种情况查找很有可能会导致栈溢出(爆栈)!!!
1.2 AVL树的引入:

两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis(AVL树就是以这两位科学家的名字命名的)

在1962年发明了一种解决上述问题的方法:

当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。

1.2 AVL树的性质:

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

  • 它的左右子树都是AVL树
  • 任何一颗子树左右子树高度之差(简称平衡因子)的绝对值不超过 1(-1 / 0 / 1)

在这里插入图片描述

平衡不是相等,与满二叉树和完全二叉树比较一下:(节点外数字代表平衡因子)

  • 满二叉树: 保证每个子树高度差是0
  • 完全二叉树: 最后一层缺一些结点
  • AVL树: 最后两层缺一些结点

AVL树又叫高度平衡二叉搜索树。

如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在 〇(logN)搜索时间复杂度 〇(logN)。


2. AVL树的模拟实现 2.1 AVL树结点的定义:
  • 直接实现key_value的结构 – 三叉链的形式(带父节点)

具体代码如下:

templatestruct AVLTreeNode
{pair_kv;
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	int _bf;
	
	AVLTreeNode(const pair& kv)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};
  • 平衡因子 —— bakance factor
  • 右子树 – 左子树的高度差

AVL树并没有规定必须要设计平衡因子,只是一个实现的选择,方便控制平衡。

2.2 AVL树的插入:(重点)
  • 这里的插入思路和二叉搜索树中插入的思路一致,找到合适的位置之后再链接

这里链接是比较容易的,但是链接之后对各个结点中的平衡因子的调整则是比较费劲的。

2.2.1 插入结点后平衡因子的变化

1. 首先我们来一段简单的逻辑 —— 只考虑父子之间关系:

  • 当一个结点的左或者右链接了一个结点,该结点为链接结点的父节点
  • 当该父节点的右边连接上孩子时,此时该父节点的右子树比左子树高了一层,平衡因子_bf + +
  • 当该父节点的左边连接上孩子时,此时该父节点的左子树比右子树高了一层,平衡因子_bf – –

如图所示:

在这里插入图片描述

2.2.2 插入结点后对其他结点衡因子的影响

2. 插入一个结点对整个树的影响:

  • 插入一个结点真正会影响的是其祖先的平衡因子的改变
  • 同时插入一个结点对兄弟结点的平衡因子没有影响

如图所示:

在这里插入图片描述

2.2.3 在不同位置插入情况分析处理

3. 在链接新的结点的时候要满足AVL树的规则

(1)向上更新:

  • 更新新插入节点祖先的平衡因子
  • 没有违反规则就结束了,违反规则,不平衡了就需要处理
  • 这里的处理是旋转处理(接下来会重点介绍)
  • 在更新的过程中只要是发现违反了AVL树规则的就需要旋转处理

(2)如何向上更新:

  • 更新的方式是沿着祖先路径更新(回溯)
  • 将parent结点更新到它的_parent位置上,将cur结点更新到它的_parent位置上
  • 在这个过程中一旦发现有违反AVL树规则的时即parent的平衡因子变成2或-2时
  • 这时就需要进行旋转处理

具体过程如下:

  • 子树高度变了,就要继续往上更新
  • 子树的高度不变, 则更新完成
  • 子树违反平衡规则,则停止更新, 旋转子树

情况一:

  • 原来是 1 or -1 -->0 (插入结点填在了矮的那一边)

在这里插入图片描述
在这里插入图片描述

情况二:

  • 原来是 0 -->1 or -1 (插入结点导致一边变高了)

在这里插入图片描述

  • 当parent->_bf == 1时

在这里插入图片描述

  • 当parent->_bf == -1时

在这里插入图片描述

情况三:

  • 一定要检查,不保证其他地方不会出现错误
    在这里插入图片描述

我们讨论问题要将各个方面的都要考虑到位才行,即使前面都正确是不会走到这一步的,但是为了万无一失还是要将这一步写上。

情况四:

  • 当插入的位置满了时

在这里插入图片描述
具体代码如下:

bool Insert(const pair& kv)
{if (_root == nullptr)
	{_root = new Node(kv);
		_root->_bf = 0;
		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;
	}
	else
	{parent->_left = cur;
	}
	//三叉链的链接 -- 链上父节点
	cur->_parent = parent;
	
	while (parent)
	{if (cur == parent->_right)
		{	parent->_bf++;
		}
		else if (cur == parent->_left)
		{	parent->_bf--;
		}

		//是否继续更新
		if (parent->_bf == 0) //原来是 1 or -1 -->0 (插入结点填在了矮的那一边)
		{	//高度不变,更新结束
			break;
		}
		else if(parent->_bf == 1 || parent->_bf == -1)
			//原来是 0 -->1 or -1 (插入结点导致一边变高了)
		{	//子树的高度变了,继续更新祖先
			cur = cur->_parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
			//原来是 1 or -1 -->2 or -2 (插入结点导致本来高的一边又变高了)
		{	//子树不平衡了 -- 需要旋转处理(左单旋的特征 -- 右边高)
			if (parent->_bf == 2 && cur->_bf == 1)//左单旋
			{		RatateL(parent);
			}
			//子树不平衡了 -- 需要旋转处理(右单旋的特征 -- 左边高)
			else if (parent->_bf == -2 && cur->_bf == -1)//右单旋
			{		RatateR(parent);
			}
			else if (parent->_bf == -2 && cur->_bf == 1)//左右双旋
			{		RatateLR(parent);
			}
			else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋
			{		RatateRL(parent);
			}
			//旋转完之后ppNode为根的子树高度不变 -- 所以对ppNode的平衡因子没有影响
			break;
		}
		else // 一定要检查 -- 不保证其他地方不会出现错误
		{	//插入之前AVL数就存在平衡子树,|平衡因子| >= 2结点
			assert(false);
		}
	}

	return true;
}

2.3 AVL树的旋转操作:(重点)

上述我们已经阐述了,在什么情况下需要对AVL树进行旋转操,接下来我们就来讲一下具体的旋转步骤。

旋转原则:

  • 保持搜索树的规则
  • 子树变平衡

旋转一共分为四种旋转方式:

  • 左单旋、右单旋
  • 左右双旋、右左双旋
2.3.1 左单旋

当右子树高的时候,这时就要向左旋转。

旋转过程:

  • 将要旋转的子树的根节点设为parent,根结点的右子树为subR,subR的左节点为subRL
  • 将subRL给parent的右,再将parent给subR的左
  • 改变其链接关系即可
  • 这样一来subR做了子树的根,根结点的左右子树高度差从2变成了0

旋转详情图:

在这里插入图片描述

  • 代表所有情况的抽象图、长方形条表示的是子树

原理:

  • 左旋转的目的是将左子树变高
  • 本来右子树高,向左旋转之后,将左子树和右子树变得一样高
  • 根节点的右子树的所有结点肯定比根结点大
  • 所以subRL可以放在parent->left
  • subRL肯定比subR小,parent也比subR小
  • 所以都可以放在subR的左边

代表所有情况的抽象图长方形条表示的是子树

下面来讨论一下h

  • h == 0时
    在这里插入图片描述
  • h == 1时

此时有两种情况,新增的节点有可能是链接在这棵树最右边结点的,左边也有可能是链接在右边

在这里插入图片描述

  • h == 2时

此时一共有36种情况

在这里插入图片描述
解释:

  • 因为是左单旋,所以这棵树的最左边一定是高度为二的满二叉树
  • 不然要是用其余两种非满二叉树的情况,肯可能空白的子树都已经不满足AVL树了,局部子树就要旋转了
  • 一共有三个位置插入空白子树,最后一个已经定下来了,所以还剩两个位置
  • 剩下的两个位置每个位置能有三种空白子树可以选择,所以是3 * 3一共9种
  • 固定下来的空白子树可以新增结点的位置一共有4处
  • 所以综上所述一共有9 * 4一共36种
  • h == 3时
    ……
  • 此时一定是比h == 2时候的情况更复杂
  • 所以层数越高,情况就越多
  • 所以我们用长方形代替了子树

具体代码如下:

//右边高就要左旋转
//左单旋
void RatateL(Node* parent)
{Node* subR = parent->_right;
	Node* subRL = subR->_left;

	parent->_right = subRL;
	if (subRL != nullptr)
	{subRL->_parent = parent;
	}

	Node* ppNode = parent->_parent;

	subR->_left = parent;
	parent->_parent = subR;

	if (parent == _root)
	{_root = subR;
		_root->_parent = nullptr;
	}
	else
	{if (parent == ppNode->_left)
		{	ppNode->_left = subR;
		}
		else if(parent == ppNode->_right)
		{	ppNode->_right = subR;
		}

		subR->_parent = ppNode;
	}

	//更新平衡因子
	parent->_bf = 0;
	subR->_bf = 0;
}

同时代码的一些细节也是需要把控的

  • subRL可能是nullptr空指针,要加以判断不然会引起非法访问
  • parent有可能就是树的根,parent也有可能只是整个树的局部子树
  • 所以要将parent->_parent先保存起来,方便之后的链接工作

在这里插入图片描述


2.3.2 右单旋

当左子树高的时候,这时就要向右旋转。

旋转详情图:

在这里插入图片描述
旋转过程:

  • 过程和原理与左单旋过程类似,可以参考左单旋过程

与左单旋一样当讨论h时,也能分出很多种,h = 1时是2种,h = 2时36种。

具体代码如下:

//左边高就要右旋转
//右单旋
void RatateR(Node* parent)
{Node* subL = parent->_left;
	Node* subLR = subL->_right;

	parent->_left = subLR;
	if (subLR != nullptr)
	{subLR->_parent = parent;
	}

	Node* ppNode = parent->_parent;

	subL->_right = parent;
	parent->_parent = subL;

	if (parent == _root)
	{_root = subL;
		subL->_parent = nullptr;
	}
	else
	{if (ppNode->_left == parent)
		{	ppNode->_left = subL;
		}
		else if (ppNode->_right == parent)
		{	ppNode->_right = subL;
		}
		subL->_parent = ppNode;
	}
	//更新平衡因子
	subL->_bf = 0;
	parent->_bf = 0;
}

细节把控也与左单旋类似可以参考左单旋。


2.3.3 左右双旋

光有左右单旋是解决不了所有问题的,如图所示就是特殊情况:

在这里插入图片描述
如图所示,很显然右单旋并没有解决问题,旋转之后仍然不是AVL树,此时我们就引入了双旋:

旋转详情图:

在这里插入图片描述
同样可以对h进行讨论,也会对应很多种情况,不再一 一赘述。

具体代码如下:

//左右双旋
void RatateLR(Node* parent)
{Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;

	RatateL(parent->_left);
	RatateR(parent);

	//更新平衡因子 -- 全是0的情况也要单独写,不要依赖单旋
	if (bf == 0)
	{parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (bf == 1)
	{parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else if (bf == -1)
	{parent->_bf = 1;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else
	{//subLR->_bf旋转前就有问题
		assert(false);
	}
}
  • 我们在实现双旋的时候可以复用单旋
  • 但是单旋有个坑,会出现将平衡因子搞成0的情况

两种解决方案:

  • 将单旋中更新的平衡因子拿出来
  • 旋转之前将位置记录下来

我们采用第一种方法,单独将平衡因子拿出来处理。


2.3.4 右左双旋

旋转详情图:

在这里插入图片描述
同样的右左双旋和左右双旋差不多,可以参考上文。

具体代码如下:

//右左双旋
void RatateRL(Node* parent)
{Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;

	RatateR(parent->_right);
	RatateL(parent);

	if (bf == 0)
	{subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else if (bf == 1)
	{subRL->_bf = 0;
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == -1)
	{subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else
	{//subLR->_bf旋转前就有问题
		assert(false);
	}
}

3. 验证AVL树

我们先增加几个成员函数:

1.层序遍历打印树

void levelOrder()
{vector>vv;
	if (_root == nullptr)
	{return;
	}

	queueq;
	int levelSize = 1;
	q.push(_root);

	while (!q.empty())
	{//levelSize控制一层一层出
		vectorlevelV;
		while (levelSize--)
		{	Node* front = q.front();
			q.pop();
			levelV.push_back(front->_kv.first);

			if (front->_left != nullptr)
			{		q.push(front->_left);
			}

			if (front->_right != nullptr)
			{		q.push(front->_right);
			}
		}
		vv.push_back(levelV);

		for (auto e : levelV)
		{	cout<< e<< " ";
		}
		cout<< endl;

		//上一层出完,下一层就都进队列
		levelSize = q.size();
	}
}

2.中序遍历二叉树:

void _InOrder(Node* root)
{if (root == nullptr)
		return;

	_InOrder(root->_left);
	cout<< root->_kv.first<< " ";
	_InOrder(root->_right);
}

void InOrder()
{_InOrder(_root);
	cout<< endl;
}

3.求二叉树高度:

int _Height(Node* root)
{if (root == nullptr)
	{return 0;
	}

	//后续的方式
	int lh = _Height(root->_left);
	int rh = _Height(root->_right);

	return lh >rh ? lh + 1 : rh + 1;
}

int Height()
{return _Height(_root);
}

验证一:

void TestAVLTree()
{//升序 -- 右边高左单旋
	//int arr[] = { 1,2,3,4,5,6,7,8 };

	//降序 -- 左边高右单旋
	int arr[] = {8,7,6,5,4,3,2,1 };

	AVLTreet;
	for (auto e : arr)
	{t.Insert(make_pair(e, e));
	}

	t.levelOrder();
}

在这里插入图片描述
如图所示的两棵树均是满足AVL树,但是这这种验证还是不太严谨。

3.1 严格验证AVL树:
  • 在插入一个结点之后,验证该棵树的每一棵子树是否都满足AVL树的规则:
bool _IsBalanceTree(Node* root)
{//空树也是AVL树
	if (nullptr == root)
		return true;

	//计算pRoot节点的平衡因子:即pRoot左右子树的高度差
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);

	//求差值
	int diff = rightHeight - leftHeight;

	//如果计算出的平衡因子与pRoot的平衡因子不相等,或者
	//pRoot平衡因子的绝对值超过1,则一定不是AVL树
	if (abs(diff) >= 2)
	{cout<< root->_kv.first<< "结点平衡因子异常"<< endl;
		return false;
	}

	//平衡因子没有异常但是和结点的对不上
	if (diff != root->_bf)
	{//说明更新有问题
		cout<< root->_kv.first<< "结点平衡因子不符合实际"<< endl;
		return false;
	}

	//pRoot的左和右如果都是AVL树,则该树一定是AVL树
	//把自己和自己的左右子树都检查了,递归检查
	return _IsBalanceTree(root->_left)
		&& _IsBalanceTree(root->_right);
}

bool IsBalanceTree()
{return _IsBalanceTree(_root);
}
  • 通过递归的方式将整棵树的子树都验证一遍。

验证二:

  • 我们插入随机值,这样更具有普遍性
  • 顺序插入我们也顺便实验一下
void TestAVLTree()
{const size_t N = 1024 * 1024 * 10;
	vectorarr;
	arr.reserve(N);//避免频繁扩容

	srand(time(0));
	for (size_t i = 0; i< N; i++)
	{arr.push_back(rand());
		//arr.push_back(i);
	}

	AVLTreet;
	for (auto e : arr)
	{t.Insert(make_pair(e, e));
	}

	cout<< "是否平衡?"<< t.IsBalanceTree()<< endl;
	cout<< "高度:"<< t.Height()<< endl;

	//t.InOrder();
}

在这里插入图片描述

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站栏目:【C++、数据结构】AVL树模拟实现-创新互联
文章起源:http://ybzwz.com/article/dcssii.html