IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> C++手撕AVL树 -> 正文阅读

[C++知识库]C++手撕AVL树

文章目录

1.概念

(1)二叉搜索树的缺点

要手撕AVL树，我们首先要知道什么是AVL树。AVL树是在二叉搜索树的基础之上改造的。当我们插入的是一个有序的序列的时候，二叉搜素树会使用一条直线来进行存储，这样并不利于查找。
在这里插入图片描述
当遇到这种情况的时候我们就需要对这棵树来进行调整。AVL树会通过旋转等操作，来规避这种情况。最终满足每一个节点的平衡因子的绝对值<=1，从而达到近似平衡的目的。
节点的平衡因子值=右子树的高度-左子树高度

(2)定义节点

在AVL树中，除了需要定义平衡因子bf之外，还需要定义指向节点父节点的指针。方便我们来进行平衡因子的更新。

struct AVLTreeNode
{
	AVLTreeNode* right;
	AVLTreeNode* left;
	AVLTreeNode* parent;
	pair<int, int> _kv;
	int _bf;
	AVLTreeNode(pair<int, int> kv)
		:right(nullptr)
		,left(nullptr)
		,parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

同时和map一样，我们使用pair类型来进行数据的存储。

2.插入

(1)拆分

AVL树的插入就是AVL树的精髓所在，我们在插入节点的同时还需要对平衡因子进行控制。
AVL树的插入我们可以拆分成五个函数，其中四个为旋转函数，一个为主要的插入函数。
而这个主要的插入函数，我们还可以将其分为三个部分：找节点，插节点，更新平衡因子。而更新平衡因子后就需要判断是否需要进行旋转的操作。
在进行插入之前，我们将插入的节点定义为kv。

(2)找节点与插节点

这一过程与二叉搜索树是相同的，这里就不多赘述了。二叉搜索树
直接上代码：

		//初始化头结点
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		//找到要插入节点的位置
		Node* cur = _root;
		Node* parent = nullptr;
		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
			{
				assert(false);
			}
		}
		//插入节点
		cur = new Node(kv);
		if (parent->_kv.first<kv.first)
		{
			parent->right = cur;
			cur->parent = parent;
		}
		else if (parent->_kv.first>kv.first)
		{
			parent->left = cur;
			cur->parent = parent;
		}
		else
		{
			assert(false);
		}

(3)更新平衡因子与旋转

更新平衡因子

每当我们插入一个节点的时候，就需要对该节点的所有父辈节点来进行平衡因子的更新。注意，当插入节点后，只有其父辈节点的平衡因子才会受到影响，而其他节点的平衡因子不会被影响。
可以根据每个节点的parent来找到其父亲节点，从而逐渐向上更新平衡因子。
当遇到以下两种情况平衡因子的更新停止。

1.某一父辈节点的平衡因子为0。
2.更新到根节点。

旋转

当更新之后的平衡因子为2或者-2的时候，不符合AVL树的平衡因子在-1~1之间的定义，此时需要发生旋转。触发旋转的条件与当前节点cur和它的parent有关。
当parent和cur的平衡因子分别为：

(1)2和1，触发左旋

	void RotateL(Node* parent)
	{
		Node* cur = parent->right;
		Node* curL = cur->left;
		Node* parentParent = parent->parent;
		parent->right = curL;
		if (curL)
			curL->parent = parent;
		cur->left = parent;
		parent->parent = cur;
		if (parent == _root)
		{
			_root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		parent->_bf = 0;
		cur->_bf = 0;
	}

用一张图来表示一下这个过程：
h表示某树的高度，当在红色部分处插入一个节点时，60的平衡因子变为1，30的平衡因子变为2。
在这里插入图片描述
此时就需要发生旋转：
在这里插入图片描述
通过旋转使树重新变成一棵AVL树，整个过程分为三步：

1.60的左子树置为30,30的右子树置为60的左子树。
2.将30与更上层的父辈节点链接起来。
3.将30和60的平衡因子都更新为0。

注意，由于AVL树是三叉树，因此在链接的时候需要将父节点也链接起来。因此在将60的左子树链接到30的右子树的时候，需要进行判空来避免空指针的解引用：

	void RotateL(Node* parent)
	{
		Node* cur = parent->right;
		Node* curL = cur->left;
		Node* parentParent = parent->parent;
		parent->right = curL;
		if (curL)
			curL->parent = parent;
		cur->left = parent;
		parent->parent = cur;
		if (parent == _root)
		{
			_root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		parent->_bf = 0;
		cur->_bf = 0;
	}

(2)-2和-1，触发右旋

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

右旋同样分为两步：

1.将30的右链接到60的左子树。将60链接到30的右。
2.将30与上层节点链接起来。
3.将30和60的平衡因子都更新为0。

	void RotateR(Node* parent)
	{
		Node* cur = parent->left;
		Node* curL = cur->left;
		Node* curR = cur->right;
		Node* parentParent = parent->parent;
		parent->left = curR;
		if (curR)
			curR->parent = parent;
		cur->right = parent;
		parent->parent = cur;
		if (parent == _root)
		{
		    _root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		cur->_bf = 0;
		parent->_bf = 0;
	}

(3)-2和1，左右双旋

当为-2和1或者2和-1的时候，仅仅靠单旋是解决不了问题的，这个时候我们就需要进行双旋：
在这里插入图片描述
左单旋：
在这里插入图片描述
右单旋：
在这里插入图片描述
无论是在红色部分或者蓝色部分插入节点，都会导致发生左右双旋。
左右双旋分为三步：

1.对30节点进行左单旋。
2.对90节点进行右单旋。
3.根据60的平衡因子来更新30和90的平衡因子：当60的平衡因子为0时，30和90的平衡因子也为0；当60的平衡因子为1时，30的平衡因子为-1，90的平衡因子为0；当60的平衡因子为-1时，30的平衡因子为0,90的平衡因子为1。

	void RotateLR(Node* parent)
	{
		Node* subL = parent->left;
		Node* subLR =subL->right;
		int bf = subLR->_bf;
		RotateL(parent->left);
		RotateR(parent);
		if (bf == 0)
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
	}

(4)2和-1，右左双旋

在这里插入图片描述
右单旋：
在这里插入图片描述
左单旋：
在这里插入图片描述
无论是在红色部分或者蓝色部分插入节点，都会导致发生右左双旋。
右左双旋分为三步：

1.对90节点进行右单旋。
2.对30节点进行左单旋。
3.根据60的平衡因子来更新30和90的平衡因子：当60的平衡因子为0时，30和90的平衡因子也为0；当60的平衡因子为1时，30的平衡因子为-1，90的平衡因子为0；当60的平衡因子为-1时，30的平衡因子为0,90的平衡因子为1。

	void RotateRL(Node* parent)
	{
		Node* subR = parent->right;
		Node* subRL = subR->left;
		int bf = subRL->_bf;
		RotateR(parent->right);
		RotateL(parent);
		if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

3.判断

我们可以建立一个函数来判断一棵树是否为AVL树。
我们使用递归来进行这一过程，依次判断各个子树是否为AVL树。
要判断我们就需要知道每一棵树的高度，此时我们需要构造一个求树的高度的函数Height。它也由递归来实现。

	int Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int leftHeight = Height(root->left);
		int rightHeight = Height(root->right);
		return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 1;
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	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->_bf << endl;
			cout << "应该是：" << rightHeight - leftHeight << endl;
			return false;
		}
		return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->left) && _IsBalance(root->right);
	}

4.完整代码及测试代码

完整代码：

#pragma once
#include<iostream>
#include<assert.h>
#include<math.h>
using namespace std;
struct AVLTreeNode
{
	AVLTreeNode* right;
	AVLTreeNode* left;
	AVLTreeNode* parent;
	pair<int, int> _kv;
	int _bf;
	AVLTreeNode(pair<int, int> kv)
		:right(nullptr)
		,left(nullptr)
		,parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};
class AVLTree
{
	typedef AVLTreeNode Node;
public:
	AVLTree()
	{
		_root = nullptr;
	}
	void InOrder()
	{
		_InOrder(_root);
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->right);
	}
	int Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int leftHeight = Height(root->left);
		int rightHeight = Height(root->right);
		return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 1;
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	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->_bf << endl;
			cout << "应该是：" << rightHeight - leftHeight << endl;
			return false;
		}
		return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->left) && _IsBalance(root->right);
	}
	//右单旋
	void RotateR(Node* parent)
	{
		Node* cur = parent->left;
		Node* curL = cur->left;
		Node* curR = cur->right;
		Node* parentParent = parent->parent;
		parent->left = curR;
		if (curR)
			curR->parent = parent;
		cur->right = parent;
		parent->parent = cur;
		if (parent == _root)
		{
		    _root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		cur->_bf = 0;
		parent->_bf = 0;
	}
	//左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->right;
		Node* curL = cur->left;
		Node* parentParent = parent->parent;
		parent->right = curL;
		if (curL)
			curL->parent = parent;
		cur->left = parent;
		parent->parent = cur;
		if (parent == _root)
		{
			_root = cur;
			_root->parent = nullptr;
		}
		else
		{
			if (parentParent->left == parent)
			{
				parentParent->left = cur;
				cur->parent = parentParent;
			}
			else if (parentParent->right == parent)
			{
				parentParent->right = cur;
				cur->parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
		parent->_bf = 0;
		cur->_bf = 0;
	}
	//左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->left;
		Node* subLR =subL->right;
		int bf = subLR->_bf;
		RotateL(parent->left);
		RotateR(parent);
		if (bf == 0)
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_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)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	bool InsertNode(pair<int, int> kv)
	{
		//初始化头结点
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		//找到要插入节点的位置
		Node* cur = _root;
		Node* parent = nullptr;
		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
			{
				assert(false);
			}
		}
		//插入节点
		cur = new Node(kv);
		if (parent->_kv.first<kv.first)
		{
			parent->right = cur;
			cur->parent = parent;
		}
		else if (parent->_kv.first>kv.first)
		{
			parent->left = cur;
			cur->parent = parent;
		}
		else
		{
			assert(false);
		}
		//更新插入节点以上的平衡因子
		while (parent)
		{
			if (cur == parent->left)
			{
				parent->_bf--;
			}
			else if (cur == parent->right)
			{
				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)
				{
					RotateR(parent);//右单旋
				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);//左单旋
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
			}
			else
			{
				assert(false);
			}
		}
	}
private:
	Node* _root;
};

测试代码：

#define _CRT_SECURE_NO_WARNINGS 1  
#include"AVLTree.h"
void TestRotateR()
{
	AVLTree t;
	t.InsertNode(make_pair(5, 1));
	t.InsertNode(make_pair(4, 1));
	t.InsertNode(make_pair(3, 1));
	t.InsertNode(make_pair(2, 1));
	t.InsertNode(make_pair(1, 1));
	t.InsertNode(make_pair(0, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void TestRotateL()
{
	AVLTree t;
	t.InsertNode(make_pair(0, 1));
	t.InsertNode(make_pair(1, 1));
	t.InsertNode(make_pair(2, 1));
	t.InsertNode(make_pair(3, 1));
	t.InsertNode(make_pair(4, 1));
	t.InsertNode(make_pair(5, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void Testbf()
{
	AVLTree t;
	t.InsertNode(make_pair(5, 1));
	t.InsertNode(make_pair(7, 1));
	t.InsertNode(make_pair(3, 1));
	t.InsertNode(make_pair(4, 1));
	t.InsertNode(make_pair(2, 1));
	t.InsertNode(make_pair(8, 1));
	t.InsertNode(make_pair(9, 1));
	t.InsertNode(make_pair(6, 1));
	t.InsertNode(make_pair(1, 1));
	t.InsertNode(make_pair(11, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void TestRL()
{
	AVLTree t;
	t.InsertNode(make_pair(60, 1));
	t.InsertNode(make_pair(50, 1));
	t.InsertNode(make_pair(90, 1));
	t.InsertNode(make_pair(100, 1));
	t.InsertNode(make_pair(80, 1));
	t.InsertNode(make_pair(70, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void TestLR()
{
	AVLTree t;
	t.InsertNode(make_pair(90, 1));
	t.InsertNode(make_pair(100, 1));
	t.InsertNode(make_pair(60, 1));
	t.InsertNode(make_pair(50, 1));
	t.InsertNode(make_pair(70, 1));
	t.InsertNode(make_pair(80, 1));
	t.InOrder();
	cout << t.IsBalance() << endl;
}
int main()
{
	//TestRotateR();
	//Testbf();
	//TestRotateL();
	//TestRL();
	TestLR();
}
  C++知识库 最新文章
【C++】友元、嵌套类、异常、RTTI、类型转换
通讯录的思路与实现（C语言)
C++PrimerPlus 第七章 函数-C++的编程模块（
Problem C: 算法9-9~9-12：平衡二叉树的基本
MSVC C++ UTF-8编程
C++进阶 多态原理
简单string类c++实现
我的年度总结
【C语言】以深厚地基筑伟岸高楼-基础篇（六
c语言常见错误合集
上一篇文章      下一篇文章      查看所有文章
加:2022-06-16 21:31:10  更:2022-06-16 21:31:23 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/23 17:18:01-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码