C++ AVL树(四种旋转,插入)

这篇具有很好参考价值的文章主要介绍了C++ AVL树(四种旋转,插入)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一.AVL树的概念及性质

AVL树又称高度平衡二叉搜索树,它的高度接近log[2]N(以2为底N的对数),整棵树的形状接近完全二叉树
增删查改的时间复杂度是O(log[2]N)
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
本节我们实现的是Key-Value模型的AVL树

二.我们要实现的大致框架

1.AVL树的节点定义

这里我们的AVL树节点比起普通的二叉树的节点来说多了两个成员
第一个是平衡因子,这里我们定义的平衡因子是右子树高度-左子树高度
第二个是指向父节点的指针,方便找到父亲节点从而方便旋转的实现

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K,V>& data = pair<K,V>())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}
	AVLTreeNode<K,V>* _pLeft;
	AVLTreeNode<K,V>* _pRight;
	AVLTreeNode<K,V>* _pParent;
	pair<K,V> _data;
	int _bf;   // 节点的平衡因子
};

存放的数据类型是一个pair
pair的第一个值是Key
第二个值是Value

2.AVL树的大致框架

// AVL: 二叉搜索树 + 平衡因子的限制
template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K,V> Node;
public:
	//构造函数
	AVLTree()
		: _pRoot(nullptr)
	{}

	// 在AVL树中插入值为data的节点
	bool Insert(const pair<K,V>& data);

	// AVL树的验证
	bool IsAVLTree()
	{
		return _IsAVLTree(_pRoot);
	}

	void InOrder()
	{
		_InOrder(_pRoot);
	}

private:
	//中序遍历
	void _InOrder(Node* root);

	// 根据AVL树的概念验证pRoot是否为有效的AVL树
	bool _IsAVLTree(Node* pRoot);

	//求树的高度
	size_t _Height(Node* pRoot);

	// 右单旋
	void RotateR(Node* pParent);

	// 左单旋
	void RotateL(Node* pParent);

	// 右左双旋
	void RotateRL(Node* pParent);

	// 左右双旋
	void RotateLR(Node* pParent);

private:
	Node* _pRoot;
};

三.插入

它的插入的大体逻辑跟二叉搜索树(BST)的插入逻辑很像
只不过需要考虑平衡因子的修改以及旋转
我们先把跟二叉搜索树一样的部分写出来

1.插入逻辑跟BST相同的那一部分

// 在AVL树中插入值为data的节点
bool Insert(const pair<K,V>& data)
{
	if (_pRoot == nullptr)
	{
		_pRoot = new Node(data);
		return true;
	}
	Node* cur = _pRoot, * parent = nullptr;
	//1.找插入位置
	while (cur)
	{
		if (cur->_data > data)
		{
			parent = cur;
			cur = cur->_pLeft;
		}
		else if (cur->_data < data)
		{
			parent = cur;
			cur = cur->_pRight;
		}
		else
		{
			return false;
		}
	}
	//2.new一个新节点,开始链接
	cur=new Node(data);
	//下面就是链接节点,修改平衡因子了,这也是AVL树相比于普通的BST的插入逻辑不同的地方
	return true;
}

2.修改平衡因子

1.前置说明

首先要说明:
1.新插入的节点的平衡因子是0,是在AVL树节点的构造函数当中进行初始化的
2.在插入节点的过程中,我们一直维持平衡因子的值为-1/0/1
3.一旦平衡因子到达了2或者-2,说明此时不满足AVL树的性质,需要进行旋转来调整平衡因子,使平衡因子恢复到-1/0/1的状态

2.画图演示

下面我们来画图演示一下插入节点后对于整棵树的节点的平衡因子的影响

1.情况1(一直影响到根节点为止)

C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
那不就是一直向上影响不就行了吗?
不是的,比如下面这种情况

2.情况2(在影响到根节点之前影响消失了)

为了方便演示,把节点8的值改成了9
新插入的值为8

C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

3.深剖情况1和2

第一种情况时:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
第二种情况时:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

4.总结

C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

3.考虑旋转

在修改平衡因子时,如果某个节点的平衡因子修改之后变为了2或者-2
说明以这个节点为根节点的子树已经不是AVL树了,需要旋转这个节点

关于如何旋转我们后面会介绍
这里先说明一下什么情况下进行哪种旋转

而旋转分为4种情况:
1.左单旋

1.左单旋的介绍

C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
总结:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

2.右单旋的介绍

了解了左单旋之后,右单旋也就能够很好的理解了
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
总结:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

3.右左双旋的介绍

右左双旋的基础条件跟左单旋的基础条件很像
只不过有一点不一样,我们来看看吧
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
总结:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

4.左右双旋的介绍

同理,左右双旋跟右单旋的基础条件也很像
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
总结:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

5.旋转条件的总结:

C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

4.插入逻辑的完善

因此我们就能够写出这样的insert代码

// 在AVL树中插入值为data的节点
bool Insert(const pair<K,V>& data)
{
	if (_pRoot == nullptr)
	{
		_pRoot = new Node(data);
		return true;
	}
	Node* cur = _pRoot, * parent = nullptr;
	//1.找插入位置
	while (cur)
	{
		if (cur->_data > data)
		{
			parent = cur;
			cur = cur->_pLeft;
		}
		else if (cur->_data < data)
		{
			parent = cur;
			cur = cur->_pRight;
		}
		else
		{
			return false;
		}
	}
	//2.插入节点调整平衡因子
	cur = new Node(data);
	//在parent左边插入节点
	if (parent->_data > data)
	{
		parent->_pLeft = cur;
		parent->_bf--;
	}
	//在parent的右边插入节点
	else
	{
		parent->_pRight = cur;
		parent->_bf++;
	}
	cur->_pParent = parent;
	//3.向上影响平衡因子
	//影响的结束条件:
	//1.cur到达_pRoot,也就是parent到达nullptr
	//2.parent的bf调整之后变为0
	//因为0只能由1或者-1变过来
	//而且由1或者-1变成0时,parent这个树的高度没有发生变化,因此不会在往上去影响了
	//3.parent这棵树需要旋转
	//旋转之后会达到1个目的:
	//降低parent这棵树的高度,降为插入这个结点之前的高度
	//因此此时就不会在往上去影响了
	while (parent)
	{
		//此时无需在往上去影响
		if (parent->_bf == 0)
		{
			break;
		}
		//此时需要再往上去影响
		//因为1或者-1只能由0变过来,因此parent这个树的高度变高,需要往上去影响
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			cur = parent;
			parent = parent->_pParent;
			if (parent != nullptr)
			{
				//说明parent是左子树,因此会让祖父的bf--
				if (parent->_pLeft == cur)
				{
					parent->_bf--;
				}
				//说明parent是右子树,因此会让祖父的bf++
				else
				{
					parent->_bf++;
				}
			}
		}
		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)
			{
				RotateRL(parent);
			}
			//右单旋
			else if (parent->_bf == -2 && cur->_bf == -1)
			{
				RotateR(parent);
			}
			//左右双旋
			else if (parent->_bf == -2 && cur->_bf == 1)
			{
				RotateLR(parent);
			}
			break;
		}
		else
		{
			assert(false);
		}
	}
	return true;
}

四.旋转的动图演示和代码实现

我们在上面已经介绍完什么是左、右单旋,右左、左右双旋转了
下面我们来看一下如何实现旋转呢?

1.左单旋

1.步骤+注意事项

C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

2.动图演示

旋转之前:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
旋转过程:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
旋转完成之后
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

3.代码实现

// 左单旋
void RotateL(Node* pParent)
{
	Node* subR = pParent->_pRight;
	Node* subRL = subR->_pLeft;
	Node* grandParent = pParent->_pParent;
	pParent->_pParent = subR;
	subR->_pLeft = pParent;
	pParent->_pRight = subRL;
	if (subRL)
		subRL->_pParent = pParent;
	//说明此时pParent是_pRoot
	if (grandParent == nullptr)
	{
		_pRoot = subR;
		_pRoot->_pParent = nullptr;
	}
	//说明此时pParent所在的树是一颗子树,需要跟父亲链接
	else
	{
		if (pParent == grandParent->_pLeft)
		{
			grandParent->_pLeft = subR;
		}
		else
		{
			grandParent->_pRight = subR;
		}
		subR->_pParent = grandParent;
	}
	//调整平衡因子
	pParent->_bf = subR->_bf = 0;
}

2.右单旋

同理,右单旋也是类似的思路
而且注意事项跟左单旋如出一辙

1.动图演示

旋转之前:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
旋转过程:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
旋转完成之后:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

2.代码实现

// 右单旋
void RotateR(Node* pParent)
{
	Node* subL = pParent->_pLeft;
	Node* subLR = subL->_pRight;
	Node* grandParent = pParent->_pParent;
	subL->_pRight = pParent;
	pParent->_pParent = subL;
	pParent->_pLeft = subLR;
	if (subLR)
		subLR->_pParent = pParent;
	if (grandParent == nullptr)
	{
		_pRoot = subL;
		_pRoot->_pParent = nullptr;
	}
	else
	{
		if (pParent == grandParent->_pLeft)
		{
			grandParent->_pLeft = subL;
		}
		else
		{
			grandParent->_pRight = subL;
		}
		subL->_pParent = grandParent;
	}
	//修改平衡因子
	subL->_bf = pParent->_bf = 0;
}

3.右左双旋

右左双旋和左右双旋都是对左单旋和右单旋的复用,这里就不在赘述了
直接上动图演示

1.先右旋

旋转之前:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
旋转过程:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
旋转之后:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

2.再左旋

旋转之前:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
旋转过程:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
旋转之后:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

3.代码实现

// 右左双旋
void RotateRL(Node* pParent)
{
	Node* subR = pParent->_pRight;
	Node* subRL = subR->_pLeft;
	int bf = subRL->_bf;
	//对subR进行一次右旋
	RotateR(subR);
	//在对pParent进行一次左旋
	RotateL(pParent);
	//这两次旋转达到了一个目的:把subRL的左子树给pParent成为pParent的右子树
	//把subRL的右子树给subR成为subR的左子树

	//根据旋转前subRL的平衡因子调整平衡后的平衡因子
	if (bf == 0)
	{
		subR->_bf = pParent->_bf = subRL->_bf = 0;
	}
	//说明subRL的左子树更低
	else if (bf == 1)
	{
		pParent->_bf = -1;
		subR->_bf = subRL->_bf = 0;
	}
	else if (bf == -1)
	{
		subR->_bf = 1;
		pParent->_bf = subRL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

4.左右双旋

1.先左旋

旋转之前:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
旋转过程:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
旋转之后:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

2.再右旋

旋转之前:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
旋转过程:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
旋转之后:
C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树

3.代码实现

// 左右双旋
void RotateLR(Node* pParent)
{
	Node* subL = pParent->_pLeft;
	Node* subLR = subL->_pRight;
	int bf = subLR->_bf;
	RotateL(subL);
	RotateR(pParent);
	//旋转的过程就是把subLR的左子树给subL成为subL的右子树
	//把subLR的右子树给pParent成为pParent的左子树
	if (bf == 0)
	{
		subL->_bf = subLR->_bf = pParent->_bf = 0;
	}
	else if (bf == 1)
	{
		subL->_bf = -1;
		subLR->_bf = pParent->_bf = 0;
	}
	else if (bf == -1)
	{
		pParent->_bf = 1;
		subL->_bf = subLR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

五.AVL树的验证

为了验证AVL树的正确性
我们添加中序遍历代码,求高度代码,验证左右子树高度差不大于1的代码

// AVL树的验证
bool IsAVLTree()
{
	return _IsAVLTree(_pRoot);
}

void InOrder()
{
	_InOrder(_pRoot);
}

private:
void _InOrder(Node* root)
{
	if (root == nullptr) return;
	_InOrder(root->_pLeft);
	cout << root->_data.first << " " << root->_data.second << " ";
	_InOrder(root->_pRight);
}

// 根据AVL树的概念验证pRoot是否为有效的AVL树
bool _IsAVLTree(Node* pRoot)
{
	if (pRoot == nullptr) return true;
	int leftHeight = _Height(pRoot->_pLeft);
	int rightHeight = _Height(pRoot->_pRight);
	return abs(leftHeight - rightHeight) < 2 && _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
}

size_t _Height(Node* pRoot)
{
	if (pRoot == nullptr)
	{
		return 0;
	}
	int leftHeight = _Height(pRoot->_pLeft);
	int rightHeight = _Height(pRoot->_pRight);
	return max(leftHeight, rightHeight) + 1;
}

下面是测试代码

#include "AVLTree.h"
#include <vector>
int test1()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree<int,string> tree;
	for (auto& e : a)
	{
		cout << e << " : " << tree.Insert(make_pair(e,"wzs")) << endl;
	}
	cout << endl;
	tree.InOrder();
	cout << endl;
	cout << tree.IsAVLTree() << endl;
	return 0;
}
int test2()
{
	const int N = 300000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
		//cout << v.back() << endl;
	}

	AVLTree<int,int> t;
	for (auto e : v)
	{
		if (e == 14604)
		{
			int x = 0;
		}

		t.Insert(make_pair(e,e));
		//cout << "Insert:" << e << "->" << t.IsAVLTree()<< endl;
	}

	cout << t.IsAVLTree() << endl;

	return 0;
}

C++ AVL树(四种旋转,插入),数据结构与算法,爱上C++,c++,AVL树,高度平衡二叉搜索树
验证成功

六.完整代码

1.AVLTree.h:

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

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K,V>& data = pair<K,V>())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}
	AVLTreeNode<K,V>* _pLeft;
	AVLTreeNode<K,V>* _pRight;
	AVLTreeNode<K,V>* _pParent;
	pair<K,V> _data;
	int _bf;   // 节点的平衡因子
};


// AVL: 二叉搜索树 + 平衡因子的限制
template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K,V> Node;
public:
	AVLTree()
		: _pRoot(nullptr)
	{}

	// 在AVL树中插入值为data的节点
	bool Insert(const pair<K,V>& data)
	{
		if (_pRoot == nullptr)
		{
			_pRoot = new Node(data);
			return true;
		}
		Node* cur = _pRoot, * parent = nullptr;
		//1.找插入位置
		while (cur)
		{
			if (cur->_data > data)
			{
				parent = cur;
				cur = cur->_pLeft;
			}
			else if (cur->_data < data)
			{
				parent = cur;
				cur = cur->_pRight;
			}
			else
			{
				return false;
			}
		}
		//2.插入节点调整平衡因子
		cur = new Node(data);
		//在parent左边插入节点
		if (parent->_data > data)
		{
			parent->_pLeft = cur;
			parent->_bf--;
		}
		//在parent的右边插入节点
		else
		{
			parent->_pRight = cur;
			parent->_bf++;
		}
		cur->_pParent = parent;
		//3.向上影响平衡因子
		//影响的结束条件:
		//1.cur到达_pRoot,也就是parent到达nullptr
		//2.parent的bf调整之后变为0
		//因为0只能由1或者-1变过来
		//而且由1或者-1变成0时,parent这个树的高度没有发生变化,因此不会在往上去影响了
		//3.parent这棵树需要旋转
		//旋转之后会达到1个目的:
		//降低parent这棵树的高度,降为插入这个结点之前的高度
		//因此此时就不会在往上去影响了
		while (parent)
		{
			//此时无需在往上去影响
			if (parent->_bf == 0)
			{
				break;
			}
			//此时需要再往上去影响
			//因为1或者-1只能由0变过来,因此parent这个树的高度变高,需要往上去影响
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_pParent;
				if (parent != nullptr)
				{
					//说明parent是左子树,因此会让祖父的bf--
					if (parent->_pLeft == cur)
					{
						parent->_bf--;
					}
					//说明parent是右子树,因此会让祖父的bf++
					else
					{
						parent->_bf++;
					}
				}
			}
			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)
				{
					RotateRL(parent);
				}
				//右单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				//左右双旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

	// AVL树的验证
	bool IsAVLTree()
	{
		return _IsAVLTree(_pRoot);
	}

	void InOrder()
	{
		_InOrder(_pRoot);
	}

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr) return;
		_InOrder(root->_pLeft);
		cout << root->_data.first << " " << root->_data.second << " ";
		_InOrder(root->_pRight);
	}

	// 根据AVL树的概念验证pRoot是否为有效的AVL树
	bool _IsAVLTree(Node* pRoot)
	{
		if (pRoot == nullptr) return true;
		int leftHeight = _Height(pRoot->_pLeft);
		int rightHeight = _Height(pRoot->_pRight);
		return abs(leftHeight - rightHeight) < 2 && _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
	}

	size_t _Height(Node* pRoot)
	{
		if (pRoot == nullptr)
		{
			return 0;
		}
		int leftHeight = _Height(pRoot->_pLeft);
		int rightHeight = _Height(pRoot->_pRight);
		return max(leftHeight, rightHeight) + 1;
	}

	// 右单旋
	void RotateR(Node* pParent)
	{
		Node* subL = pParent->_pLeft;
		Node* subLR = subL->_pRight;
		Node* grandParent = pParent->_pParent;
		subL->_pRight = pParent;
		pParent->_pParent = subL;
		pParent->_pLeft = subLR;
		if (subLR)
			subLR->_pParent = pParent;
		if (grandParent == nullptr)
		{
			_pRoot = subL;
			_pRoot->_pParent = nullptr;
		}
		else
		{
			if (pParent == grandParent->_pLeft)
			{
				grandParent->_pLeft = subL;
			}
			else
			{
				grandParent->_pRight = subL;
			}
			subL->_pParent = grandParent;
		}
		//修改平衡因子
		subL->_bf = pParent->_bf = 0;
	}

	// 左单旋
	void RotateL(Node* pParent)
	{
		Node* subR = pParent->_pRight;
		Node* subRL = subR->_pLeft;
		Node* grandParent = pParent->_pParent;
		pParent->_pParent = subR;
		subR->_pLeft = pParent;
		pParent->_pRight = subRL;
		if (subRL)
			subRL->_pParent = pParent;
		//说明此时pParent是_pRoot
		if (grandParent == nullptr)
		{
			_pRoot = subR;
			_pRoot->_pParent = nullptr;
		}
		//说明此时pParent所在的树是一颗子树,需要跟父亲链接
		else
		{
			if (pParent == grandParent->_pLeft)
			{
				grandParent->_pLeft = subR;
			}
			else
			{
				grandParent->_pRight = subR;
			}
			subR->_pParent = grandParent;
		}
		//调整平衡因子
		pParent->_bf = subR->_bf = 0;
	}

	// 右左双旋
	void RotateRL(Node* pParent)
	{
		Node* subR = pParent->_pRight;
		Node* subRL = subR->_pLeft;
		int bf = subRL->_bf;
		//对subR进行一次右旋
		RotateR(subR);
		//在对pParent进行一次左旋
		RotateL(pParent);
		//这两次旋转达到了一个目的:把subRL的左子树给pParent成为pParent的右子树
		//把subRL的右子树给subR成为subR的左子树

		//根据旋转前subRL的平衡因子调整平衡后的平衡因子
		if (bf == 0)
		{
			subR->_bf = pParent->_bf = subRL->_bf = 0;
		}
		//说明subRL的左子树更低
		else if (bf == 1)
		{
			pParent->_bf = -1;
			subR->_bf = subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			subR->_bf = 1;
			pParent->_bf = subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	// 左右双旋
	void RotateLR(Node* pParent)
	{
		Node* subL = pParent->_pLeft;
		Node* subLR = subL->_pRight;
		int bf = subLR->_bf;
		RotateL(subL);
		RotateR(pParent);
		//旋转的过程就是把subLR的左子树给subL成为subL的右子树
		//把subLR的右子树给pParent成为pParent的左子树
		if (bf == 0)
		{
			subL->_bf = subLR->_bf = pParent->_bf = 0;
		}
		else if (bf == 1)
		{
			subL->_bf = -1;
			subLR->_bf = pParent->_bf = 0;
		}
		else if (bf == -1)
		{
			pParent->_bf = 1;
			subL->_bf = subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

private:
	Node* _pRoot;
};

2.test.cpp

#include "AVLTree.h"
#include <vector>
int test1()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree<int,string> tree;
	for (auto& e : a)
	{
		cout << e << " : " << tree.Insert(make_pair(e,"wzs")) << endl;
	}
	cout << endl;
	tree.InOrder();
	cout << endl;
	cout << tree.IsAVLTree() << endl;
	return 0;
}

int test2()
{
	const int N = 300000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
		//cout << v.back() << endl;
	}

	AVLTree<int,int> t;
	for (auto e : v)
	{
		if (e == 14604)
		{
			int x = 0;
		}

		t.Insert(make_pair(e,e));
		//cout << "Insert:" << e << "->" << t.IsAVLTree()<< endl;
	}

	cout << t.IsAVLTree() << endl;

	return 0;
}

int main()
{
	test1();
	cout << "=============    开始test2的验证   =================" << endl;
	test2();
	return 0;
}

以上就是C++ AVL树(四种旋转,插入)的全部内容,希望能对大家有所帮助!文章来源地址https://www.toymoban.com/news/detail-764801.html

到了这里,关于C++ AVL树(四种旋转,插入)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:AVL树讲解(C++)

    普通二叉搜索树: 二叉搜索树 二叉搜索树虽可以缩短查找的效率,但如果 数据有序或接近有序普通的二叉搜索树将退化为单支树 ,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法

    2024年02月04日
    浏览(42)
  • 数据结构(C++) : AVL树 实现篇

    目录 1.AVL树引入   (1)二叉搜索树缺点   (2)AVL树简介     [1]问题的解决     [2]AVL树的性质 2.AVL树的插入旋转操作   (1)术语解释   (2)左单旋     [1]插入到右侧的左边     [2]插入到右侧的右边   (3)右单旋     [1]插入到左侧的左边     [2]插入到左侧的右边   (4)左右双旋    

    2024年02月05日
    浏览(35)
  • 数据结构与算法——18.avl树

    这篇文章我们来看一下avl树 目录 1.概述 2.AVL树的实现 我们前面讲了二叉搜索树,它是有一个key值,然后比父节点key值大的在左边,小的在右边。这样设计是为了便于查找。但是有一种极端的情况,就是所有的结点都在一边,那查找的时间复杂度和在链表的查找时间复杂度就

    2024年02月07日
    浏览(38)
  • [数据结构 C++] AVL树的模拟实现

    问题引入: 在上一篇文章中,我们提到了二叉搜索树在插入时,可能会形成单边树,会降低二叉搜索的性能。因此我们需要平衡二叉搜索树,降低二叉搜索树的高度,使得二叉搜索树趋于一颗完全二叉树的样子,这样就可以提高二叉搜索树的性能。本篇文章就来介绍一种平衡

    2024年02月03日
    浏览(52)
  • 【数据结构与算法】平衡二叉树(AVL树)

    给你一个数列{1,2,3,4,5,6},要求创建二叉排序树(BST),并分析问题所在。 BST 存在的问题分析 : 左子树全部为空,从形式上看,更像一个单链表。 插入速度没有影响。 查询速度明显降低(因为需要依次比较),不能发挥 BST 的优势,因为每次还需要比较左子树,其查询速度

    2024年02月13日
    浏览(42)
  • 数据结构07:查找[C++][平衡二叉排序树AVL]

    图源:文心一言 考研笔记整理1w+字,小白友好、代码可跑,请小伙伴放心食用~~🥝🥝 第1版:查资料、写BUG、画导图、画配图~🧩🧩 参考用书: 王道考研《2024年 数据结构考研复习指导》 参考用书配套视频: 7.3_2 平衡二叉树_哔哩哔哩_bilibili 特别感谢:  Chat GPT老师、文心

    2024年02月11日
    浏览(48)
  • Python - 深夜数据结构与算法之 AVL 树 & 红黑树

    目录 一.引言 二.高级树的简介 1.树 2.二叉树 3.二叉搜索树 4.平衡二叉树 三.AVL 树 ◆ 插入节点 ◆ 左旋 ◆ 右旋 ◆ 左右旋 ◆ 右左旋 ◆ 一般形式 ◆ 实际操作 ◆ 总结 四.红黑树 ◆ 概念 ◆ 示例 ◆ 对比 五.总结 前面我们介绍了二叉树、二叉搜索树、多叉树等基础的树形结构,

    2024年01月19日
    浏览(44)
  • 算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十)

    1. 插入排序(insertion-sort):                                           是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入     算法稳定性:                  

    2024年02月09日
    浏览(56)
  • 数据结构算法-插入排序

    一、概念及其介绍 插入排序(InsertionSort),一般也被称为直接插入排序。 对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增 1 的有序表 。在其实现过程使用双层

    2024年02月21日
    浏览(46)
  • C++数据结构之平衡二叉搜索树(一)——AVL的实现(zig与zag/左右双旋/3+4重构)

    本文是介绍众多平衡二叉搜索树(BBST)的第一篇——介绍AVL树。故先来引入BBST的概念。由于上一篇介绍的二叉搜索树(BST)在极度退化的情况下,十分不平衡,不平衡到只朝一侧偏,成为一条链表,复杂度可达 O ( n ) O(n) O ( n ) ,所以我们要在“平衡”方面做一些约束,以防

    2024年02月13日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包