首页 > 编程语言 >AVL树 ---（C++）

AVL树 ---（C++）

时间：2024-06-12 23:29:22浏览次数：22  
标签：--- cur parent balanceFactor C++ AVL root 节点 left

        本篇讲全面的讲解 AVL 树的插入，旋转以及验证 AVL 树的性能（本篇未实现删除代码）。至于为什么会有 AVL 树，这是因为简单的二叉搜索树并不能直接的保证搜索的效率，因为当我们在二叉搜索树中插入一段有序的序列的时候，二叉搜索树就会退化为单枝树，这个时候进行搜索的时候，时间复杂度就变为了 O(n^2)，如下：

        但是通过 AVL 树的旋转就可以很好的解决这个问题，使树近似等于完全二叉树或者满二叉树。

AVL 树代码

        先给出代码，接着在下文中给出解释：

#pragma once
#include <iostream>
#include <assert.h>

using namespace std;

template <class K, class V>
struct AVLTreeNode {
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	int _balanceFactor;

	AVLTreeNode(const pair<K, V>& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _balanceFactor(0)
	{}
};

template <class K, class V>
class AVLTree {
public:
	typedef AVLTreeNode<K, V> Node;
	Node* find(const K& key) {
		Node* cur = _root;
		while (cur) {
			if (cur->_kv.first < key)
				cur = cur->_right;
			else if (cur->_kv.first > key)
				cur = cur->_left;
			else
				return cur;
		}
		return 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 == nullptr
		cur = new Node(kv);
		//if (parent->_left == cur)
		//	parent->_left = cur;
		//else
		//	parent->_right = cur;
		if (parent->_kv.first > kv.first)
			parent->_left = cur;
		else
			parent->_right = cur;
		cur->_parent = parent;
		// 需要更新平衡因子
		// 如果是在父亲的左边，父亲的平衡因子减一、右边加一
		if (parent->_left == cur)
			parent->_balanceFactor--;
		else
			parent->_balanceFactor++;
		// 查看爷爷结点是否需要更新

		while (parent) {
			if (parent->_balanceFactor == 0) {
				break;
			}
			else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
				if (parent == _root)
					break;
				// 现在的parent就不可能等于null
				parent = parent->_parent;
				cur = cur->_parent;
				if (parent->_left == cur)
					parent->_balanceFactor--;
				else
					parent->_balanceFactor++;
			}
			else if(parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
				if (parent->_balanceFactor == 2 && cur->_balanceFactor == 1)
					RotateLeft(parent);
				else if (parent->_balanceFactor == -2 && cur->_balanceFactor == -1)
					RotateRight(parent);
				else if (parent->_balanceFactor == -2 && cur->_balanceFactor == 1)
					RotateLeftRight(parent);
				else if (parent->_balanceFactor == 2 && cur->_balanceFactor == -1)
					RotateRightLeft(parent);
				else
					assert(false);
				break;
			}
			else {
				assert(false);
			}
		}

		return true;
	}

	void RotateRight(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		// 将左孩子的右节点链接到原父亲结点
		if (subLR) subLR->_parent = parent;
		parent->_left = subLR;
		
		Node* ppNode = parent->_parent;
		// 将左孩子变为原父亲结点的父亲
		subL->_right = parent;
		parent->_parent = subL;
		// 将爷爷结点重新链接
		if (ppNode == nullptr) {
			_root = subL;
			_root->_parent = nullptr;
		}
		else {
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;
			subL->_parent = ppNode;
		}
		subL->_balanceFactor = parent->_balanceFactor = 0;
	}

	void RotateLeft(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* ppNode = parent->_parent;

		parent->_right = subRL;
		if (subRL) subRL->_parent = parent;
		
		subR->_left = parent;
		parent->_parent = subR;

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

	void RotateRightLeft(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int balanceFactor = subRL->_balanceFactor;
		RotateRight(subR);
		RotateLeft(parent);
		// 更新平衡因子
		subRL->_balanceFactor = 0;
		if (balanceFactor == -1) {
			parent->_balanceFactor = 0;
			subR->_balanceFactor = 1;
		}
		else if (balanceFactor == 1) {
			parent->_balanceFactor = -1;
			subR->_balanceFactor = 0;
		}
		else if (balanceFactor == 0) {
			parent->_balanceFactor = 0;
			subR->_balanceFactor = 0;
		}
		else {
			assert(false);
		}
	}

	void RotateLeftRight(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int balanceFactor = subLR->_balanceFactor;
		// 先左旋后右旋
		RotateLeft(subL);
		RotateRight(parent);

		subLR->_balanceFactor = 0;
		if (balanceFactor == -1) {
			subL->_balanceFactor = 0;
			parent->_balanceFactor = 1;
		}
		else if (balanceFactor == 1) {
			parent->_balanceFactor = 0;
			subL->_balanceFactor = -1;
		}
		else if (balanceFactor == 0) {
			parent->_balanceFactor = 0;
			subL->_balanceFactor = 0;
		}
		else {
			assert(false);
		}
	}

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

	int height() {
		int h = _height(_root);
		return h;
	}

	int size() {
		int s = _size(_root);
		return s;
	}

	bool IsBalance() {
		return _IsBalance(_root);
	}

private:
	bool _IsBalance(Node* root) {
		if (root == nullptr)
			return true;
		int leftHeight = _height(root->_left);
		int rightHeight = _height(root->_right);
		if (abs(leftHeight - rightHeight) >= 2)
			return false;
		if (abs(root->_balanceFactor) >= 2)
			return false;
		return _IsBalance(root->_left) && _IsBalance(root->_right);
	}

	int _height(Node* root) {
		if (root == nullptr)
			return 0;
		int left = _height(root->_left);
		int right = _height(root->_right);
		int height = max(left, right);
		return height + 1;
	}

	int _size(Node* root) {
		if (root == nullptr)
			return 0;
		return _size(root->_left) + _size(root->_right) + 1;
	}

	void _InOrder(Node* root) {
		if (root == nullptr) return;
		_InOrder(root->_left);
		cout << root->_kv.first << " " << root->_kv.second << endl;
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

AVL 树的概念于抽象数据结构

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

        1. 它的左右子树都是 AVL 树

        2. 左右子树的高度之差（平衡因子）的绝对值不超过 1

        左右子树的高度差不超过 1，可以降低树的高度，减少平均搜索长度。如下：

        关于 AVL 树的抽象数据结构，我们首先需要抽象出 AVL 树节点的数据结构，在 AVL 树中，我们存储的关键数据为键值对 pair，AVL 树节点中的平衡因子。然后需要一个指向左子树的指针，指向右子树的指针同时还需要一个指向父节点的指针，可以让我们便于更新每个节点的平衡因子。如下：

template <class K, class V>
struct AVLTreeNode {
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	int _balanceFactor;

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _balanceFactor(0)
	{}
};

AVL 树的插入

        关于 AVL 树而言，只是在二叉搜索树的基础上引入了平衡因子，所以 AVL 树也可以看出二叉搜索树（左右高度差不大于1的二叉搜索树），所以对于 AVL 树的插入，可以分为以下两步：

        1. 按照二叉搜索树的方式插入新节点。

        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->_right;
		else if (cur->_kv.first > kv.first)
			parent = cur, cur = cur->_left;
		else
			return false;
	}
	// cur == nullptr
	cur = new Node(kv);
    
    // 链接孩子节点和父节点
	if (parent->_kv.first > kv.first)
		parent->_left = cur;
	else
		parent->_right = cur;
	cur->_parent = parent;

	// 需要更新平衡因子...
	
	

	return true;
}

        插入成功，则返回 true，插入失败（树中已经存在键值）则返回 false。

        以上只是完成了插入，插入元素之后，我们还需要更新节点的平衡因子，更新平衡因子按照以下原则进行更新：

        1. 插入元素位置位于父节点的右边，父节点的平衡因子 +1；        

        2. 插入元素位置位于父节点的左边，父节点的平衡因子 -1。

        3. 更新完父节点的平衡因子之后，父节点的平衡因子的取值可能为 0、正负1、正负2。

        5. 父节点的平衡因子更新完之后为0，不会影响父节点的父节点的平衡，所以不用在往上更新。

        6. 父节点的平衡因子跟新完之后为正负1，说明原来父节点的平衡因子为0，这时还会影响父节点的父节点的平衡因子，所以需要继续向上更新。当某个节点的平衡原则为正负二的时候，我们就需要通过选择使树平衡。

        如下：

// 需要更新平衡因子
// 如果是在父亲的左边，父亲的平衡因子减一、右边加一
if (parent->_left == cur)
	parent->_balanceFactor--;
else
	parent->_balanceFactor++;
// 查看爷爷结点是否需要更新

while (parent) {
	if (parent->_balanceFactor == 0) {
		break;
	}
	else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
		if (parent == _root)
			break;
		// 现在的parent就不可能等于null
		parent = parent->_parent;
		cur = cur->_parent;
		if (parent->_left == cur)
			parent->_balanceFactor--;
		else
			parent->_balanceFactor++;
	}
	else if(parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
		if (parent->_balanceFactor == 2 && cur->_balanceFactor == 1)
			RotateLeft(parent);
		else if (parent->_balanceFactor == -2 && cur->_balanceFactor == -1)
			RotateRight(parent);
		else if (parent->_balanceFactor == -2 && cur->_balanceFactor == 1)
			RotateLeftRight(parent);
		else if (parent->_balanceFactor == 2 && cur->_balanceFactor == -1)
			RotateRightLeft(parent);
		else
			assert(false);
		break;
	}
	else {
		assert(false);
	}
}

        对于如上的代码中，其中最难的一步就是旋转，关于旋转一共会出现四种情况：左单旋、右单旋、左右双旋、右左双旋。

AVL 树的旋转

        我们首先介绍右单旋，当新节点插入导较高左子树的左侧就会出现右单旋，关于右单旋出现的情况如下：

        当出现如上所示的情况时（父亲节点的平衡因子等于-2，左孩子节点的平衡因子为-1时），我们就需要进行右旋，也就是将左孩子作为父节点，父节点作为右孩子，在将左孩子的右节点链接到原父节点上。其中还有需要注意的点：右旋时的父节点不一定是根节点，所以我们在旋转的时候，还需要记录下父节点的父节点，最后将其链接到一起。

void RotateRight(Node* parent) {
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	// 将左孩子的右节点链接到原父亲结点
	if (subLR) subLR->_parent = parent;
	parent->_left = subLR;
	
	Node* ppNode = parent->_parent;
	// 将左孩子变为原父亲结点的父亲
	subL->_right = parent;
	parent->_parent = subL;
	// 将爷爷结点重新链接
	if (ppNode == nullptr) {
		_root = subL;
		_root->_parent = nullptr;
	}
	else {
		if (ppNode->_left == parent)
			ppNode->_left = subL;
		else
			ppNode->_right = subL;
		subL->_parent = ppNode;
	}
	subL->_balanceFactor = parent->_balanceFactor = 0;
}

        记得最后将节点的平衡因子设置为0。

        接着我们介绍左单旋：当新节点插入到较高右子树的右侧，关于这种情况如下：

        关于左单旋，其思想和右单旋基本一致，不过是将右单旋的给镜像了过来。所以当父节点的平衡因子为2，右节点的平衡因子为1的时候，我们就需要对树进行左单旋。也就是让右孩子的左节点作为父节点的右孩子，左节点作为父节点，原父节点作为左孩子的左节点。注意原父节点的父节点是否为 nullptr，最后需要更新节点的平衡因子。如下：

void RotateLeft(Node* parent) {
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* ppNode = parent->_parent;

	parent->_right = subRL;
	if (subRL) subRL->_parent = parent;
	
	subR->_left = parent;
	parent->_parent = subR;

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

        第三种情况，左右双旋。左右双旋就是分别需要左旋一次，然后右旋一次，接着更新我们的平衡因子，如下：

        如上图所示，当左孩子节点的平衡因子为1，父节点的平衡因子为-2的时候，我们就需要进行左右双旋，当我们旋转之后，当前父节点的平衡因子一定为0，但原父节点和左孩子节点的平衡因子一共有三种情况，分别是0 0，1 0，0 -1。当 h = 0 的时候，插入的节点就是以上的60节点，旋转之后所有节点（一共就3个节点）都是为0，当节点插入到60的左边，那么30的平衡因子为0（如图），当节点插入到60的右边，90的平衡因子则为0。

        因为在单独调用左单选，右单旋之后，会将所有节点的平衡因子都置为0，所以我们需要进行特殊处理。如下：

void RotateLeftRight(Node* parent) {
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int balanceFactor = subLR->_balanceFactor;
	// 先左旋后右旋
	RotateLeft(subL);
	RotateRight(parent);

	subLR->_balanceFactor = 0;
	if (balanceFactor == -1) {
		subL->_balanceFactor = 0;
		parent->_balanceFactor = 1;
	}
	else if (balanceFactor == 1) {
		parent->_balanceFactor = 0;
		subL->_balanceFactor = -1;
	}
	else if (balanceFactor == 0) {
		parent->_balanceFactor = 0;
		subL->_balanceFactor = 0;
	}
	else {
		assert(false);
	}
}

        最后一种情况：右左双旋。也就是先右旋然后在左旋，也就是和以上的情况是堆成的情况，如下：

        对于需要右左旋转的情况为父节点为2，右孩子为1.关于转换的细节和以上的左右双旋的情况向对称，在这就不细讲了，代码如下：

void RotateRightLeft(Node* parent) {
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int balanceFactor = subRL->_balanceFactor;
	RotateRight(subR);
	RotateLeft(parent);
	// 更新平衡因子
	subRL->_balanceFactor = 0;
	if (balanceFactor == -1) {
		parent->_balanceFactor = 0;
		subR->_balanceFactor = 1;
	}
	else if (balanceFactor == 1) {
		parent->_balanceFactor = -1;
		subR->_balanceFactor = 0;
	}
	else if (balanceFactor == 0) {
		parent->_balanceFactor = 0;
		subR->_balanceFactor = 0;
	}
	else {
		assert(false);
	}
}

AVL 树的验证 + 测试

        接下来我们将对我们是新的 AVL 树进行验证，也就是看我们写出的代码是否符合 AVL 树的特性，其中主要包括特性测试和压力测试。在进行测试之前，我们需要先写出一些辅助函数，如下：

template <class K, class V>
class AVLTree {
public:
	typedef AVLTreeNode<K, V> Node;

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

	int height() {
		int h = _height(_root);
		return h;
	}

	int size() {
		int s = _size(_root);
		return s;
	}

	bool IsBalance() {
		return _IsBalance(_root);
	}

private:
	bool _IsBalance(Node* root) {
		if (root == nullptr)
			return true;
		int leftHeight = _height(root->_left);
		int rightHeight = _height(root->_right);
		if (abs(leftHeight - rightHeight) >= 2)
			return false;
		if (abs(root->_balanceFactor) >= 2)
			return false;
		return _IsBalance(root->_left) && _IsBalance(root->_right);
	}

	int _height(Node* root) {
		if (root == nullptr)
			return 0;
		int left = _height(root->_left);
		int right = _height(root->_right);
		int height = max(left, right);
		return height + 1;
	}

	int _size(Node* root) {
		if (root == nullptr)
			return 0;
		return _size(root->_left) + _size(root->_right) + 1;
	}

	void _InOrder(Node* root) {
		if (root == nullptr) return;
		_InOrder(root->_left);
		cout << root->_kv.first << " " << root->_kv.second << endl;
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

        我们先进行特性测试，如下：

        如上所示，我们一共验证了两组数据，其中包含了左旋、右旋、左右双旋、右左双旋四种情况。

        接着进行暴力测试，生成一百万个数据，主要测试性能和插入是否成功：

        如上所示，插入一百万个数据也可以生成平衡树。

        测试源码如下：

void TestAVL01() {
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	// {16, 3, 7, 11, 9, 26, 18, 14, 15}
	AVLTree<int, int> avtree;
	
	for (auto e : a) {
		if (e == 4) {
			int i = 0;
		}
		avtree.insert(make_pair(e, e));
	}
	avtree.InOrder();
	cout << avtree.height() << endl;
	cout << avtree.size() << endl;
	cout << avtree.IsBalance() << endl;
}

void TestAVL02() {
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (int i = 0; i < N; i++) {
		v.push_back(rand() + 1);
	}
	size_t begin1 = clock();
	AVLTree<int,int> tree;
	for (auto e : v)
		tree.insert({e, e});
	size_t end1 = clock();
	cout << "insert" << end1 - begin1 << endl;

	cout << "Height:" << tree.height() << endl;
	cout << "Size:" << tree.size() << endl;

	size_t begin2 = clock();
	for (auto e : v)
		tree.find(e);
	size_t end2 = clock();
	cout << "find:" << end2 - begin2 << endl;

	cout << tree.IsBalance() << endl;
}

标签：---,cur,parent,balanceFactor,C++,AVL,root,节点,left
From： https://blog.csdn.net/m0_74830524/article/details/139096631

相关文章

  • python-11-def函数 好比是sop 调用函数可以让程序听令
    学习内容：《python编程：从入门到实践》第二版知识点：定义函数、调用函数、形参、实参练习内容：练习8-1：消息编写一个名为display_message()的函数，它打印一个句子，指出你在本章学的是什么。调用这个函数，确认显示的消息正确无误。练习8-2：喜欢的图书编写一个名为favorite_book()......
  • 【AI应用探讨】— GPT-4o模型应用场景
    目录1.自然语言处理（NLP）任务文本生成机器翻译问答系统2.聊天机器人与虚拟助手智能聊天机器人虚拟助手与陪伴3.内容创作与辅助创意写作代码生成4.教育辅助学习工具5.客户服务与支持客户服务聊天机器人技术支持6.研究与分析数据分析市场研究科学研究7.......
  • 文科生脑回路| AI大模型-Agent入门自学笔记
    大型语言模型(LargeLanguage Models,LLM)能通过分析海量文本数据，学习人类语言的内在规律和知识结构，从而展现出惊人的语言理解和生成能力。通过与大语言模型交互，不仅可以获取所需信息，还能生成高质量的文本内容、解决复杂的问题、开发智能应用程序等。以大型语言模型为核心......
  • 微信AI机器人使用说明-2024本地部署版（非wechaty）
     一、效果演示微信机器人实现的功能，先看视频的演示效果：2024年最新稳定的本地部署AI微信机器人使用方法演示可以对话可以语音可以绘画支持主账号管理好友权限管理免费体验AI好友: yuzitao-716二、支持功能1.绑定主账号：绑定主账号之后，主账号可以给其他用户、其他群组......
  • 性能测试工具-JMeter
    官网:https://jmeter.apache.org/安装JMeter1.安装JDK下载地址:https://www.oracle.com/java/technologies/downloads/#jdk22-windows执行java--version查看版本2.安装JMeter下载地址:https://dlcdn.apache.org//jmeter/binaries/apache-jmeter-5.6.3.zip下载到本地......
  • c++ 游戏：俄罗斯方块
    ​​​​​​​#include<iostream>#include<string>#include<cstdlib>#include<windows.h>#include<ctime>#include<conio.h>#include<cstdio>usingnamespacestd;classTetris{private:intrank;//游戏难度等级intscore;//得分intid;/......
  • D-Bus——DBUS_SESSION_BUS_ADDRESS 环境变量为空
            DBUS_SESSION_BUS_ADDRESS环境变量通常在用户会话环境中定义，用于指示会话总线的地址。在root用户环境下，这个环境变量可能为空，原因如下：原因分析会话总线与用户会话相关：        会话总线（sessionbus）是与特定用户会话相关的总线，每个用户登录后都会......
  • D-Bus——session bus调用机制
            当D-Bus会话总线（sessionbus）客户端拿到环境变量DBUS_SESSION_BUS_ADDRESS的值后，它会按照以下步骤来连接和与会话总线进行通信：1.获取环境变量        首先，D-Bus客户端程序会读取环境变量DBUS_SESSION_BUS_ADDRESS。这个环境变量包含了会话总线的......
  • D-Bus——system bus调用机制
            在D-Bus中，系统总线（systembus）和会话总线（sessionbus）的工作方式有所不同。会话总线主要依赖环境变量来找到总线地址，而系统总线则依赖于标准的系统路径和配置。系统总线的服务查找机制系统总线的启动：        系统总线守护进程（dbus-daemon--syste......
  • 精细化运营-银行存量客户管理的关键策略与挑战【文末送书】
    银行存量客户运营在现代金融行业中，银行面临着激烈的竞争和不断变化的市场环境。为了在这种环境中立于不败之地，银行不仅需要吸引新客户，更需要有效地运营存量客户。银行存量客户运营指的是通过各种策略和手段，提高现有客户的满意度和忠诚度，进而增加客户的终身价值。本文将探讨......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99