C++ AVLTree高度平衡的二叉搜索树怎么实现

发布时间:2023-03-09 14:12:38 作者:iii
来源:亿速云 阅读:82

这篇“C++ AVLTree高度平衡的二叉搜索树怎么实现”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C++ AVLTree高度平衡的二叉搜索树怎么实现”文章吧。

一、AVL树的概念

二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。

因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。

一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:

它的左右子树都是AVL树

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

平衡因子= 右子树高度-左子树高度

C++ AVLTree高度平衡的二叉搜索树怎么实现

如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在O(log2N) ,搜索时间复杂度O(log2N)

二、AVL树节点的定义

节点结构:三叉链结构(左、右、父),以及平衡因子bf+构造函数(左右为空,平衡因子初始化为0)

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

三、AVL树的插入

AVL树在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。步骤过程:

找到插入的位置:根据二叉搜索树的做法

进行插入:判断插入的位置是parent的左还是右

更新平衡因子:如果不平衡的话,就要进行旋转

找到插入位置(比较节点大小即可):

插入之后,与二叉搜索树不同的是:我们还需要去进行平衡因子的更新,调平衡:

如果新增加的在右,平衡因子加加

如果新增加的在左,平衡因子减减

更新一个结点之后我们需要去进行判断,子树的高度是否发生了变化:

1.如果parent的平衡因子是0:说明之前parent的平衡因子是1或-1,说明之前parent一边高、一边低;这次插入之后填入矮的那边,parent所在的子树高度不变,不需要继续往上更新

2.如果parent的平衡因子是1或者-1:说明之前parent的平衡因子是0,两边一样高,插入之后一边更高,parent所在的子树高度发生变化,继续往上更新

3.平衡因子是2或-2,说明之前parent的平衡因子是1或-1,现在插入严重不平衡,违反规则,需要进行旋转处理

最坏的情况下:需要一直更新到根root:

C++ AVLTree高度平衡的二叉搜索树怎么实现

我们更新平衡因子时第一个更新的就是parent,如果parent->_bf1或parent->_bf-1需要继续往上进行平衡因子的更新,向上迭代,直到parent为空的情况:

else if (parent->_bf == 1 || parent->_bf == -1)
{
    cur = parent;
    parent = parent->_parent;
}

当parent->_bf = 2或parent->_bf==-2时,我们就需要进行旋转了:

????如果parent的平衡因子是2,cur的平衡因子是1时,说明右边的右边比较高,我们需要进行左单旋

????如果parent的平衡因子是-2,cur的平衡因子是-1时,说明左边的左边比较高,我们需要进行右单旋

????如果parent的平衡因子是-2,cur的平衡因子是1时,我们需要进行左右双旋

????如果parent的平衡因子是2,cur的平衡因子是-1时,我们需要进行右左双旋

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 = new Node(kv);
		if (parent->_kv.first < kv.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)
			{
				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)
				{
					RotateLR(parent);
				}
				//右左双旋
				else if (parent->_bf ==2&&cur->_bf ==-1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

四、AVL树的旋转

在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡化。根据节点插入位置的不同,AVL树的旋转分为四种。

旋转规则:

1.让这颗子树左右高度差不超过1

2.旋转过程中继续保持它是搜索树

3.更新调整孩子节点的平衡因子

4.让这颗子树的高度根插入前保持一致

1.左单旋

新节点插入较高右子树的右侧&mdash;右右:左单旋

抽象图:

C++ AVLTree高度平衡的二叉搜索树怎么实现

a/b/c是高度为h的AVL子树,代表多数情况:h>=0,其中h可以等于0、1、2&hellip;,不过都可以抽象成h,处理情况都一样:此时parent等于2,subR等于1。

具体左旋的步骤:

subRL成为parent的右子树:注意subL和parent的关系,调整parent的右以及subRL的父(subRL可能为空)

parent成为subR的左子树:调整parent的父与subR的左

subR成为相对的根节点:调整subR与ppNode:注意parent是不是整棵树的root,如果是,则让subR为_root,同时让_root->_parent置为空

更新平衡因子

左旋调整:subR的左子树值(subRL)本身就比parent的值要大,所以可以作为parent的右子树;而parent及其左子树当中结点的值本身就比subR的值小,所以可以作为subR的左子树。

**更新平衡因子bf:**subR与parent的bf都更新为0

C++ AVLTree高度平衡的二叉搜索树怎么实现

代码实现左旋转:

//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		Node* ppNode = 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;
		}
		parent->_bf = subR->_bf = 0;
	}

2.右单旋

新节点插入较高左子树的左侧&mdash;左左:右单旋

有了前面左旋的基础,我们在来看右旋就没有那么费劲了:

C++ AVLTree高度平衡的二叉搜索树怎么实现

a/b/c是高度为h的AVL树,右旋旋转动作:b变成60的左边,60变成30的右边,30变成子树的根。

30比60小,b值是处于30和60之间,此时作为60的左边是没有问题的。

有了这个图,在结合前面左单旋的基础,我们就能很快实现我们的右单旋代码:

//右单旋
void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subL;
		subL->_right = parent;
		//if(_root==parent)
		if (ppNode == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
		subL->_bf = parent->_bf = 0;
	}

3.左右双旋

新节点插入较高左子树的右侧&mdash;左右:先左单旋再右单旋

C++ AVLTree高度平衡的二叉搜索树怎么实现

a/d是高度为h的AVL树,b/c是高度为h-1的AVL树。

以30为轴点进行左单旋:b变成30的右边,30变成60的左边,60变成子树根

C++ AVLTree高度平衡的二叉搜索树怎么实现

以90为轴点进行右单旋:c变成90的左边,90变成60的右边,60变成子树的根

C++ AVLTree高度平衡的二叉搜索树怎么实现

左右双旋:以subL为轴点左旋,以parent为轴点进行右旋,在进行平衡因子的更新(最大的问题)

我们从总体的角度来看,左右双旋的结果就是:就是把subLR的左子树和右子树,分别作为subL和parent的右子树和左子树,同时subL和parent分别作为subLR的左右子树,最后让subLR作为整个子树的根

subLR的左子树作为subL的右子树:因为subLR的左子树结点比subL的大

subLR的右子树作为parent的左子树:因为subLR的右子树结点比parent的小

平衡因子的更新:重新判断(识别插入节点是在b还是在c)根据subLR平衡因子的初始情况进行分类:

如果subLR初始平衡因子是-1时,左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0(插入在b)

C++ AVLTree高度平衡的二叉搜索树怎么实现

如果subLR的初始平衡因子是1时,左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0(插入在c)

C++ AVLTree高度平衡的二叉搜索树怎么实现

如果subLR初始平衡因子是0时,左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0(subLR自己新增)

C++ AVLTree高度平衡的二叉搜索树怎么实现

代码实现:

//左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR ->_bf;
		RotateL(parent->_left);
		RotateR(parent);
		//更新平衡因子
		if (bf == -1)//b插入,subLR左子树新增
		{
			subL->_bf = 0;
			parent->_bf = 1;
			subLR->_bf = 0;
		}
		else if (bf == 1)//c插入,subLR右子树新增
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == 0)//subLR自己新增加
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

4.右左双旋

新节点插入较高右子树的左侧&mdash;右左:先右单旋再左单旋

插入

C++ AVLTree高度平衡的二叉搜索树怎么实现

subR为轴点进行右单旋:

C++ AVLTree高度平衡的二叉搜索树怎么实现

parent为轴进行左单旋:

C++ AVLTree高度平衡的二叉搜索树怎么实现

既右左双旋:

C++ AVLTree高度平衡的二叉搜索树怎么实现

右左双旋后,根据subRL 初始平衡因子的不同分为三种情况分别对应subRL = 0、1、-1情况,与左右双旋情况类似。

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

五、进行验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分两步:

验证其为二叉搜索树

如果中序遍历可得到一个有序的序列,就说明为二叉搜索树

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

验证其为平衡树

每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确

如果是空树,是AVL树;高度差不大于2,并且递归左右子树的高度差都不大于2,也是AVL树;判断平衡因子和该点的高度差是否相等

//求高度
int Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int lh = Height(root->_left);
		int rh = Height(root->_right);
		return lh > rh ? lh + 1 : rh + 1;
	}
//判断平衡
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->_kv.first << "平衡因子异常" << endl;
			return false;
		}
		return abs(rightHeight - leftHeight) < 2
			&& IsBalance(root->_left)
			&& IsBalance(root->_right);
	}

六、AVLTree的性能

AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度即log2( N) 。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。

因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合.

送上源码:

#pragma once
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;
template<class K,class V>
struct AVLTreeNode
{
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;//balance factor
	AVLTreeNode(const pair<K,V>&kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}
};
template <class K,class V>
struct AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	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 = new Node(kv);
		if (parent->_kv.first < kv.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)
			{
				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)
				{
					RotateLR(parent);
				}
				//右左双旋
				else if (parent->_bf ==2&&cur->_bf ==-1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}
	//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		Node* ppNode = 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;
		}
		parent->_bf = subR->_bf = 0;
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subL;
		subL->_right = parent;
		//if(_root==parent)
		if (ppNode == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
		subL->_bf = parent->_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 == -1)//b插入,subLR左子树新增
		{
			subL->_bf = 0;
			parent->_bf = 1;
			subLR->_bf = 0;
		}
		else if (bf == 1)//c插入,subLR右子树新增
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == 0)//subLR自己新增加
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	//右左双旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
		RotateR(subR);
		RotateL(parent);
		if (bf == 1)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			subR->_bf = 1;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	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 lh = Height(root->_left);
		int rh = Height(root->_right);
		return lh > rh ? lh + 1 : rh + 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->_kv.first << "平衡因子异常" << endl;
			return false;
		}
		return abs(rightHeight - leftHeight) < 2
			&& IsBalance(root->_left)
			&& IsBalance(root->_right);
	}
private:
	Node* _root = nullptr;
};
//测试
void TestAVLTree()
{
	//int a[] = { 8,3,1,10,6,4,7,14,13 };
	//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, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e,e));
	}
	t.InOrder();
	cout << t.IsBalance() << endl;
}
void TestAVLTree2()
{
	srand(time(0));
	const size_t N = 100000;
	AVLTree<int, int> t;
	for (size_t i = 0; i < N; i++)
	{
		size_t x = rand();
		t.Insert(make_pair(x, x));
	}
	//t.InOrder();
	cout << t.IsBalance() << endl;
}

以上就是关于“C++ AVLTree高度平衡的二叉搜索树怎么实现”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注亿速云行业资讯频道。

推荐阅读:
  1. python如何调用c++中ctype的list传数组或者返回数组
  2. 怎么在python中通过调用c++传递数组

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++ avltree

上一篇:idea如何构建web项目

下一篇:Golang中interface{}的注意事项是什么

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》