【C++笔记】AVL树的模拟实现

news/2024/7/5 9:03:34

【C++笔记】AVL树的模拟实现

  • 一、AVL树的概念
  • 二、AVL树的模拟实现
    • 2.1、定义节点
    • 2.2、插入
    • 2.3、旋转
      • 2.3.1、左单旋
      • 2.3.2、右单旋
      • 2.3.3、左右双旋
      • 2.3.4、右左双旋
      • 2.3.5、插入接口的整体代码实现
  • 三、验证AVL树
    • 3.1、验证

一、AVL树的概念

二叉搜索树虽然在一般情况下可以提高查找的效率，但如果插入数据的顺序接近有序或有序，那二叉搜索树就会变成一个类似“单链表”的结构：
在这里插入图片描述
这样查找的效率就会变得和单链表一样是O(n)了，效率低下。
对此，两位俄罗斯的数学家G.M.Adelson-Velskii
和E.M.Landis在1962年
发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树要么是空树，要么就是具有以下性质的一棵二叉搜索树：

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

比如下面这棵树就是一棵AVL树：
在这里插入图片描述

二、AVL树的模拟实现

2.1、定义节点

定义AVL树的节点除了传统的左右指针和值之外还需要定义两个成员——parent指针和平衡因子，因为我们后面在调整平衡的时候必须要用到它们：

// 定义AVL树节点
template <class K, class V>
struct AVLTreeNode {
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _val;
	int _bf; // 平衡因子
	// 构造
	AVLTreeNode(const pair<K, V>& key)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_val(key)
		,_bf(0)
	{}
};

然后同样的，我们只需要在AVLTree类里面封装一个根节点的指针即可：

// AVL树
template <class K, class V>
class AVLTree {
public:
	typedef AVLTreeNode<K, V> Node;
	// ……
private :
	Node* _root = nullptr;
};

2.2、插入

因为AVL树其实结构和普通二叉树没什么区别，只是规则不一样，所以我们这里就只需要实现与其他数不同的插入即可。

AVL树的插入也实现要找到插入位置，但是在插入成功之后还需要调整平衡因子，并判断是否需要进行调整，以确保满足AVL树的规则。

最容易的情况就是在插入新节点后，左右高度差并没有超出范围，这样就不需要调整了(调整到根节点为止，如果没有一个节点的平衡因子超出范围就不需要调整)，例如在下面这AVL树中我们要插入一个值为9的节点：
在这里插入图片描述
当我们找到插入位置后就需要一直向上调整平衡因子：
在这里插入图片描述
当我们调整完后发现并么有平衡因子出现异常，因此也就不需要调整了，所执行的操作和二叉搜索树的插入一样了。

这里先给出不需要调整的代码实现：

// 插入
bool insert(const pair<K, V>& key) {
	if (nullptr == _root) {
		_root = new Node(key);
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	
	// 先插入节点
	while (cur) {
		if (key.first > cur->_val.first) {
			parent = cur;
			cur = cur->_right;
		}
		else if (key.first < cur->_val.first) {
			parent = cur;
			cur = cur->_left;
		}
		else {
			return false;
		}
	}

	// 准备插入
	cur = new Node(key);
	if (key.first > parent->_val.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) {
			return true;
		}
		else if (parent->_bf == 1 || parent->_bf == -1) { // 继续向上检查
			cur = parent;
			parent = parent->_parent;
		} else {
			assert(false);
		}
	}
	return true; // 插入成功
}

2.3、旋转

2.3.1、左单旋

而一旦我们的插入导致平衡因子超出了范围，这时候就需要调整了，比如我们想要在下面这棵AVL中在插入一个值为10的节点：
在这里插入图片描述
更新平衡因子的过程中，我们发现8这个节点的平衡因子超出了范围，这时候我们该怎样调整呢？

如果我们将8看做需要调整的这棵子树的根，那么对根为8的这棵子树进行 “左单旋” 就能解决问题。

像这样在右子树的右子树（右右）中插入新节点的情况，处理的方法称为左单旋，下面介绍具体步骤：
在这里插入图片描述
如上图所示，将节点8设置为parent，parent的parent设置成parent_parent，parent的右孩子设置成subRight，将subRight的左孩子设置成subRightL。
左单旋我们需要做的就是让subRight成为parent的右孩子，再让parent成为subRight的左孩子，然后让subRight成为这棵子树新的根，并让parent_parent连接上subRight。

相信大家看上面的图示都会感到眼花缭乱，所以我这里转化出了一个抽象图：
在这里插入图片描述
这里其实并不用关心子树的高度h具体是多高，因为h取任何值都是一样的。
从图中我们也可以观察的出，这里的本质其实是通过将subRight改成新的根节点，从而将整棵子树的高度降低了一个高度。
做完这些后不要忘了调整平衡因子，由图中我们可以很形象的看出直接把subRight和parent的平衡因子调整成0即可。
(图中省略了parent指针的处理，但是在实际实现中，parent指针是一定要处理的)

那这样做为什么正确呢？

通过之前对搜索二叉树规律的分析，我们可以得出另一个规律：对于一个根，它的左子树的所有节点一定是小于根节点的，右子树的所有节点一定是大于根的。
所以我们这里的subRightL也一定是大于parent的，所以它可以成为pareng的右子树，而subRight也一定是大于parent的，所以parent就可以成为subRight的根，所以经过上面的操作之后，这棵子树还是满足二叉搜索树的规律的。

那怎么判断什么情况下我们要进行左单旋呢？
我们可以通过平衡因子来判断，因为平衡因子的定义是右子树与左子树的高度差，所以如果一个根它的平衡因子是2并且它的右子树的平衡因子是1，则说明是在右子树的右子树中插入新节点导致的不平衡。

所以一棵子树要进行左单旋判断条件是：

root->_bf == 2 && root->_right->_bf == 1;

接下来就是左单旋的代码实现：

// 左单旋
void RotateL(Node* parent) {
	Node* subRight = parent->_right;
	Node* subRightL = subRight->_left;
	Node* parent_parent = parent->_parent;

	parent->_right = subRightL;
	if (subRightL) {
		subRightL->_parent = parent;
	}
	subRight->_left = parent;
	parent->_parent = subRight;

	if (parent == _root) { // 如果当前的parent是根
		_root = subRight;
		subRight->_parent = nullptr;
	}
	else {
		// 如果当前的parent还不是根
		if (parent == parent_parent->_left) {
			parent_parent->_left = subRight;
		}
		else {
			parent_parent->_right = subRight;
		}
		subRight->_parent = parent_parent;
	}


	// 调整平衡因子
	parent->_bf = 0;
	subRight->_bf = 0;
}

2.3.2、右单旋

右单旋和做单旋在逻辑上是一样的，基本就是左单旋改一下方向就可以了。
当我们在左子树的左子树（左左）中插入节点导致不平衡的时候，就需要用到右单旋：
在这里插入图片描述
处理过程的抽象图也和左单旋的差不多：
在这里插入图片描述
然后这是右单旋的代码实现：

	// 右单旋
	void RotateR(Node* parent) {
		Node* subLeft = parent->_left;
		Node* subLeftR = subLeft->_right;
		Node* parent_parent = parent->_parent;

		parent->_left = subLeftR;
		if (subLeftR) {
			subLeftR->_parent = parent;
		}
		subLeft->_right = parent;
		parent->_parent = subLeft;

		if (parent == _root) { // 如果当前的parent为根
			_root = subLeft;
			subLeft->_parent = nullptr;
		}
		else {
			// 如果当前的parent不为根
			if (parent == parent_parent->_left) {
				parent_parent->_left = subLeft;
			}
			else {
				parent_parent->_right = subLeft;
			}
			subLeft->_parent = parent_parent;
		}

		// 调整平衡因子
		subLeft->_bf = 0;
		parent->_bf = 0;
	}

2.3.3、左右双旋

然后还有一些情况是单纯的左单旋和右单旋不能解决的，因为它们并不是单纯的“左左”或“右右”，比如在左子树的右子树中插入一个节点导致不平衡：
在这里插入图片描述
如果这时候只是单纯的对90这个根进行右单旋的话就会变成下面这样子：
在这里插入图片描述
我们会返现调整后30节点的平衡因子还是超出了范围，所以这样是不能解决问题的。

其实这里的主要问题是插入的位置变了，我们简单的分析一下单纯的右单旋就能的出问题的出处：
在这里插入图片描述
通过观察我们发现，右边单旋我们是通过把高的那颗子树（a）“往上层移动”来达到减少整体高度的，而矮的那颗子树(b)所在的层数不变。
而如果是在b这棵子树中插入：
在这里插入图片描述
其实就变成了，减少左子树的一个高度，去增加右子树的一个高度，但是还是不平衡，而且转化后也不是一个单纯的左单旋。

那该怎样解决呢？
其实我们可以先通过对30这棵子树进行左单旋，从而使旋转后的整棵子树变成左高右低的形式：
在这里插入图片描述
这样就可以把90这棵子树变成单纯的右单旋了。
然后再对90进行右单旋就变平衡了：
在这里插入图片描述

但是平衡因子又该怎么更新呢？
对于平衡因子更新的处理，我们可以先来看看双旋后的对比：
在这里插入图片描述

从中我们可以看得出，双旋其实还可以这样处理：
让subLeft成为新的根，然后subLeft成为subLeftR的左子树，parent成为subLeftR的右子树，子树b成为subLeft的右子树，子树c成为parent的左子树。

所以平衡因子的更新，的关键点就在于subLeftR的平衡因子，或者说是看subLeftR这棵子树的左子树高还是右子树高，即子树b高还是子树c高。

如果subLeftR的平衡因子为0，则说明subLeft本身就是新加入的节点，此时a，b，c，d这四棵子树都是空，所以subLeftR、subLeft和parent的平衡因子都为0。

如果subLeftR的平衡因子为1，则表示子树c要比子树b高1，所以更新后parent的平衡因子为0，subLeft的平衡因子为-1。

如果subLeftR的平衡因子为1，则表示子树b要比子树c高1，所以更新后subLeft的平衡因子为0，parent的平衡因子为1。

然后这是左右双旋的代码实现：

// 左右双旋
void RotateLR(Node* parent) {
	Node* subLeft = parent->_left;
	Node* subLeftR = subLeft->_right;
	int bf = subLeftR->_bf;
	RotateL(parent->_left);
	RotateR(parent);

	// 调整平衡因子
	if (0 == bf) {
		parent->_bf = 0;
		subLeft->_bf = 0;
		subLeftR->_bf = 0;
	}
	else if (-1 == bf) {
		subLeft->_bf = 0;
		parent->_bf = 1;
		subLeftR->_bf = 0;
	}
	else if (1 == bf) {
		subLeft->_bf = 0;
		parent->_bf = 0;
		subLeftR->_bf = -1;
	}
	else {
		assert(false);
	}
}

2.3.4、右左双旋

右左双旋的分析逻辑其实和左右双旋一样，只是方向不同罢了。
在这里插入图片描述
然后这是右左双旋的代码实现，基本和左右双旋的一样：

// 右左双旋
void RotateRL(Node* parent) {
	Node* subRight = parent->_right;
	Node* subRightL = subRight->_left;
	int bf = subRightL->_bf;
	RotateR(parent->_right);
	RotateL(parent);
	
	// 调整平衡因子
	if (0 == bf) {
		// subRightL自己就是新增节点
		parent->_bf = 0;
		subRightL->_bf = 0;
		subRight->_bf = 0;
	}
	else if (1 == bf) {
		// subRight的右边新增
		parent->_bf = -1;
		subRight->_bf = 0;
		subRight->_bf = 0;
	}
	else if (-1 == bf) {
		// subRight的左边新增
		parent->_bf = 0;
		subRightL->_bf = 0;
		subRight->_bf = 1;
	}
	else {
		assert(false);
	}
}

2.3.5、插入接口的整体代码实现

// 插入
bool insert(const pair<K, V>& key) {
	if (nullptr == _root) {
		_root = new Node(key);
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	
	// 先插入节点
	while (cur) {
		if (key.first > cur->_val.first) {
			parent = cur;
			cur = cur->_right;
		}
		else if (key.first < cur->_val.first) {
			parent = cur;
			cur = cur->_left;
		}
		else {
			return false;
		}
	}

	// 准备插入
	cur = new Node(key);
	if (key.first > parent->_val.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) {
			return true;
		}
		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);
				return true;
			}
			else if (parent->_bf == -2 && cur->_bf == -1) { // 右单旋
				RotateR(parent);
				return true;
			}
			else if (parent->_bf == 2 && cur->_bf == -1) { // 右左双旋
				RotateRL(parent);
				return true;

			}
			else if (parent->_bf == -2 && cur->_bf == 1) { // 左右双旋
				RotateLR(parent);
				return true;
			}
		}
		else {
			assert(false);
		}
	}
	return true; // 插入成功
}

三、验证AVL树

3.1、验证

验证AVL树我们需要验证两个方面，一个是左右高度差，另一个是平衡因子，因为有时候就算左右高度差就算正常，平衡因子在更新的时候也有可能会出错。而平衡因子一旦出错，就很有可能会带出更多的错误。

所以我们可以写一个判断是否平衡的函数：

// 检查是否平衡
bool isBalance() {
	return _isBalance(_root);
}

bool _isBalance(Node* root) {
	if (nullptr == root) {
		return true;
	}
	int leftH = _height(root->_left);
	int rightH = _height(root->_right);
	// 顺便检查一些平衡因子是否异常
	if (rightH - leftH != root->_bf) {
		cout << root->_val.first << " 平衡因子异常" << endl;
		return false;
	}
	return abs(rightH - leftH) < 2 && _isBalance(root->_left) && _isBalance(root->_right);
}

// 计算高度
int _height(Node* root) {
	if (nullptr == root) {
		return 0;
	}
	return max(_height(root->_left), _height(root->_right)) + 1;
}

// 中序遍历
void Inorder() {
	_Inorder(_root);
	cout << endl;
}

// 中序遍历子函数
void _Inorder(Node* root) {
	if (nullptr == root) {
		return;
	}
	_Inorder(root->_left);
	cout << "(" << root->_val.first << ", " << root->_bf << ") ";
	_Inorder(root->_right);
}

然后我们就可以来跑几个测试看一下：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述


http://lihuaxi.xjx100.cn/news/1786838.html

相关文章

idea 插件推荐第二期

idea 插件推荐第二期

文章目录 便捷开发CodeGlance Pro (代码缩略图)GenerateAllSetter&#xff08;快速生成对象所有set方法&#xff09;GsonFormatPlus&#xff1a;json转实体RestfulToolkitX&#xff08;找到controller快捷请求接口&#xff09; 美化activate-power-mode-x (敲击计数、动效)Nyan…
阅读更多...
lc307.区域和检索 - 数组可修改

lc307.区域和检索 - 数组可修改

暴力解法 创建方法&#xff0c;通过switch-case判断所需要调用的方法。 public class RegionsAndSertches {public static void main(String[] args) {String[] str new String[]{"NumArray", "sumRange", "update", "sumRange"};i…
阅读更多...
【算法】算法题-20231114

【算法】算法题-20231114

这里写目录标题 一、LCR 181. 字符串中的单词反转二、557. 反转字符串中的单词 III三、344. 反转字符串四、给定一个已按照升序排列的有序数组&#xff0c;找到两个数使得它们相加之和等于目标数。五、力扣第49题&#xff1a;字母异位词分组 一、LCR 181. 字符串中的单词反转 …
阅读更多...
java学习part02一些特性

java学习part02一些特性

17-Java语言概述-Java语言的特点和JVM的功能_哔哩哔哩_bilibili 1.java优点 跨平台性 在jvm上运行 2.jvm 2.1实现跨平台性 不需要对每一种指令集编写编译器&#xff0c;只需要针对jvm编程&#xff0c;jvm会自动转换 2.2内存回收 内存溢出&#xff1a;用的内存太多已经占满了&…
阅读更多...
NLP---文本前期预处理的几个步骤

NLP---文本前期预处理的几个步骤

1、读取文本 text1 """ Football is a family of team sports that involve, to varying degrees, kicking a ball to score a goal. Unqualified, the word football is understood to refer to whichever form of football is the most popular in the reg…
阅读更多...
P6入门：项目初始化9-项目详情之资源 Resource

P6入门：项目初始化9-项目详情之资源 Resource

前言 使用项目详细信息查看和编辑有关所选项目的详细信息&#xff0c;在项目创建完成后&#xff0c;初始化项目是一项非常重要的工作&#xff0c;涉及需要设置的内容包括项目名&#xff0c;ID,责任人&#xff0c;日历&#xff0c;预算&#xff0c;资金&#xff0c;分类码等等&…
阅读更多...
【C语言】深入解开指针（二）

【C语言】深入解开指针（二）

&#x1f308;write in front :&#x1f50d;个人主页 &#xff1a; 啊森要自信的主页 &#x1f308;作者寄语 &#x1f308;&#xff1a; 小菜鸟的力量不在于它的体型&#xff0c;而在于它内心的勇气和无限的潜能&#xff0c;只要你有决心&#xff0c;就没有什么事情是不可能的…
阅读更多...
Springboot细节补充

Springboot细节补充

一、Bean是怎么装配的&#xff1f; 1、bean扫描 在之前的ssm中&#xff0c;spring要么用标签的形式来扫描包&#xff0c;要么使用注解ComponentScan来扫描 但是在Springboot中&#xff0c;启动类上默认有一个注解SpringBootApplication&#xff0c;里面就包含了ComponentScan…
阅读更多...
最新文章

Copyright @ 2022~2023