【C++】模拟实现AVL树

修修修也

发布于 2024-10-01 08:31:11

240

发布于 2024-10-01 08:31:11

文章被收录于专栏：修也的进阶日记

一.了解项目功能

在本次项目中我们的目标是实现一个AVL树 : 提供的功能有:

AVL树结点类的构造函数
AVL树的构造函数
AVL树的插入函数
插入时结点的左单旋
插入时结点的右单旋
插入时结点的左右双旋
插入时结点的右左双旋

二.逐步实现项目功能模块及其逻辑详解

通过第二部分对项目功能的介绍，我们已经对的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！

！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。

实现AVLTreeNode类模板

构造AVLTreeNode类成员变量

构造AVLTreeNode类构造函数

//贴代码

实现AVLTree类模板

构造AVLTree类成员变量

实现AVLTree类构造函数

实现AVLTree插入函数

实现AVLTree插入左单旋

实现AVLTree插入右单旋

实现AVLTree插入左右双旋

实现AVLTree插入右左双旋

由于我们要实现 的功能可以反复使用的逻辑，且至少在一开始执行一次,因此我们选择do...while的循环语句来实现这一部分的逻辑.

该部分功能实现代码如下:

//贴代码

三.项目完整代码

我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:

test.c文件

#include"AVL_Tree.h"


int main()
{
	int a[] = { 16,3,7,11,9,26,18,14,15 };
	AVLTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
		t.InOrder();
	}
	//1:	16
	//2:	3 16
	//3:	7 16(这步有错,7直接丢了),也就是说左右双旋错了
	return 0;
}

AVLTree.h文件

#pragma once

#include<iostream>
#include<assert.h>
using namespace std;

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K,V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}

	pair<K, V> _kv;
	AVLTreeNode<K,V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K,V> Node;
public:
	AVLTree()
		:_root(nullptr)
	{}

	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		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->_left)//新增结点是parent的左孩子
			{
				parent->_bf--;		//给parent的BF--.(因为这套代码逻辑是按照BF=右高-左高来写的)
			}
			else
			{
				parent->_bf++;
			}
			//当该结点的BF为0时,就不会再影响下一个父节点了,可以理解为:
			//当你变为0时,你上一步的操作一定没有影响到你这整颗树的总高度,你的总高度不变,你就不会影响父节点的平衡因子
			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);
				}

				break;//旋转结束,插入也就可以结束了
			}
			else
			{
				assert(false);
			}
		}

		return true;
	}

	//左旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		Node* ppnode = parent->_parent;

		//将失衡结点右孩子的左子树链接到失衡结点的右孩子
		parent->_right = curleft;
		if (curleft)
		{
			curleft->_parent = parent;		
		}
	
		//将失衡结点连接到失衡结点右孩子的左孩子位置
		parent->_parent = cur;
		cur->_left = parent;

		//处理父父结点的链接
		cur->_parent = ppnode;
		if (ppnode == nullptr)//为空代表parent就已经是root了
		{
			_root = cur;
		}
		else
		{
			if (ppnode->_left == parent)//失衡结点是其父节点的左孩子
			{
				ppnode->_left = cur;
			}
			else       //失衡结点是其父节点的右孩子
			{
				ppnode->_right = cur;
			}
		}

		//更新影响因子
		parent->_bf = cur->_bf = 0;
	}

	//右单旋
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		Node* ppnode = parent->_parent;

		//将失衡结点左孩子的右子树连接到失衡结点的左孩子位置
		parent->_left = curright;
		if (curright)
		{
			curright->_parent = parent;
		}

		//将失衡结点连接到失衡结点左孩子的右孩子位置
		parent->_parent = cur;
		cur->_right = parent;

		//链接父父结点
		cur->_parent = ppnode;
		if (ppnode == nullptr)//为空代表parent就已经是root了
		{
			_root = cur;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
		}

		//更新影响因子
		parent->_bf = cur->_bf = 0;
	}

	//右左双旋
	void RotateRL(Node* parent)
	{
		//记录一下cur和cur->left指针的位置,因为双旋过后会找不到
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		int curleft_bf = curleft->_bf;

		RotateR(cur);
		RotateL(parent);

		//curleft_bf已经在上面两个函数里置0了,它无论哪种情况都是0我们不用管
		//但还是处理一下,这样可以降低耦合度,防止单旋没改的情况
		//处理平衡因子
		if (curleft_bf == 1)
		{
			parent->_bf = -1;
			cur->_bf = 0;
			curleft->_bf = 0;
		}
		else if (curleft_bf == -1)
		{
			parent->_bf = 0;
			cur->_bf = 1;
			curleft->_bf = 0;
		}
		else if (curleft_bf == 0)
		{
			parent->_bf = 0;
			cur->_bf = 0;
			curleft->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	//左右双旋
	void RotateLR(Node* parent)
	{
		//记录一下cur和cur->right指针的位置,因为双旋过后会找不到
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		int curright_bf = curright->_bf;

		RotateL(cur);
		RotateR(parent);

		//处理平衡因子
		//curright_bf已经在上面两个函数里置0了,我们不用管
		//但还是处理一下,这样可以降低耦合度,防止单旋没改的情况
		if (curright_bf == -1)
		{
			parent->_bf = 1;
			cur->_bf = 0;
			curright->_bf = 0;
		}
		else if (curright_bf == 1)
		{
			parent->_bf = 0;
			cur->_bf = -1;
			curright->_bf = 0;
		}
		else if (curright_bf == 0)
		{
			parent->_bf = 0;
			cur->_bf = 0;
			curright->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}


	//中序遍历函数
	void InOrder()
	{
		_InOrder(_root);  //代替成员函数完成递归
		cout << endl;       //方便后续观察测试用例
	}

private:

	//中序遍历子递归函数
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);       //递归访问左子树
		cout << root->_kv.first << " ";   //访问根节点
		_InOrder(root->_right);      //递归访问右子树
	}


	Node* _root;
};