【数据结构】AVL树及平衡化旋转

前端之家收集整理的这篇文章主要介绍了【数据结构】AVL树及平衡化旋转前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

二叉搜索树可以缩短查找的效率,但是如果数据有序或接近有序时二叉搜索树将退化为单支树,查找效率将会下降。因此,我们通过向二叉搜索树种插入结点后,保证左右子树的高度之差的绝对值不超过1来调节结点,降低树的高度。

一. AVL树概念:

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

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

2.左子树和右子树高度之差(简称平衡因子)的绝对值不超过1;

如果一颗二叉搜索树是高度平衡的,它就是AVL树。


二. 平衡化旋转

在AVL树中最重要的是平衡化旋转,使树达到平衡状态。平衡化旋转有四种旋转,分别是:左单旋,右单旋,左右双旋,右左双旋,下面我们将看一下怎样旋转使树平衡:

首先有几点需要说明:

1.图中结点右侧紫色的数字表示该节点的平衡因子;

2.平衡因子等于右子树高度与左子树高度之差;

3.在写代码时,除了要改变结点指针的指向,还需要注意平衡因子的变化。


1)左单旋及右单旋:



2)右左双旋,当新增加的结点是较高右子树的左侧时,需要右左双选调整,它有三种情况,分别如下:





3)左右双旋,当新增加的结点是较高左子树的右侧时,需要左右双选调整,与右左双旋类似:


三. 结点的插入

在AVL树中插入结点,需要以下四步:

1.如果是空树,插入后即为根结点,插入后直接返回true;

2. 如果树不为空,寻找插入位置,若在寻找过程中找到key,则插入失败返回false;

3. 插入结点;

4. 更新平衡因子,对树进行调整,新结点的平衡因子为0,插入后其双亲结点的平衡因子有三种情况:

双亲结点的平衡因子为0:即结点插入到成功,并达到了平衡,结束处理;

双亲结点的平衡因子的绝对值为1:

说明插入前parent的平衡因子为0,插入后以parent为根的子树没有失去平衡,但该子树的高度增加,需要从parent向根结点方向回溯,继续查看parent的双亲的平衡性;

双亲结点的平衡因子的绝对值为2:则新结点出入到了较高的子树,需要进行平衡化处理:

若parent的平衡因子为2,则说明右子树较高,设parent的右子树为subR:当subR的平衡因子为1时,执行左单旋;若subR的平衡因子为-1,执行右左双旋;

若parent的平衡因子为-2,则说明左子树较高,设parent的左子树为subL: 当subL的平衡因子为1时,执行右单旋;若subL的平衡因子为-1,执行左右双旋;



具体实现代码如下:
#include <iostream>
using namespace std;
template <class K,class V>
struct AVLTreeNode
{
	AVLTreeNode(const K& key,const V& value)
	: _pLeft(NULL),_pRight(NULL),_pParent(NULL),_key(key),_value(value),_bf(0)
	{}
	AVLTreeNode<K,V>* _pLeft;
	AVLTreeNode<K,V>* _pRight;
	AVLTreeNode<K,V>* _pParent;
	K _key;
	V _value;
	int _bf;
};
template <class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K,V> Node;
	typedef Node* pNode;
public:
	AVLTree()
		: _pRoot(NULL)
	{}

	bool Insert(const K& key,const V& value)
	{
		if (NULL == _pRoot)//1. 空树直接添加结点
		{
			_pRoot = new Node(key,value);
			return true;
		}
		//2. 非空树
		//(1) 查找添加的位置
		pNode pParent = NULL;
		pNode pCur = _pRoot;
		while (pCur)
		{
			if (key < pCur->_key)
			{
				pParent = pCur;
				pCur = pCur->_pLeft;
			}
			else
			{
				pParent = pCur;
				pCur = pCur->_pRight;
			}
		}
		//(2) 插入结点
		pCur = new Node(key,value);
		if (key < pParent->_key)//插入到左边
		{
			pCur->_pParent = pParent;
			pParent->_pLeft = pCur;
		}
		else if (key > pParent->_key)//插入到右边
		{
			pCur->_pParent = pParent;
			pParent->_pRight = pCur;
		}
		else//插入的结点已经存在
			return false;
		//(3) 更新平衡因子,使二叉树平衡
		while (pParent)
		{
			if (pParent->_pLeft == pCur)
				pParent->_bf--;
			else if (pParent->_pRight == pCur)
				pParent->_bf++;

			if (pParent->_bf == 0)
				break;//不需要调节
			else if (pParent->_bf == 1 || pParent->_bf == -1)//平衡因子在-1或1时,继续向上调节
			{
				pCur = pParent;
				pParent = pParent->_pParent;
			}
			else//平衡因子在2或者-2时,调节至平衡
			{
				if (pParent->_bf == 2)
				{
					if (pCur->_bf == 1)
						RotateL(pParent);
					else
						RotateRL(pParent);
				}
				else
				{
					if (pCur->_bf == -1)
						RotateR(pParent);
					else
						RotateLR(pParent);
				}
				break;
			}
		}//end of while
		return true;
	}

	void InOrder()
	{
		_InOrder(_pRoot);
	}

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

	int Height()
	{
		return _Height(_pRoot);
	}

private:
	bool _IsBalance(pNode pRoot)
	{
		if (pRoot == NULL)
			return true;
		int left = _Height(pRoot->_pLeft);
		int right = _Height(pRoot->_pRight);
		if (abs(right - left) > 1)
			return false;
		return true;
	}

	int _Height(pNode pRoot)
	{
		if (NULL == pRoot)
			return 0;
		int left = _Height(pRoot->_pLeft);
		int right = _Height(pRoot->_pRight);
		return left > right ? left + 1 : right + 1;
	}

	void RotateL(pNode pParent)
	{
		pNode pSubR = pParent->_pRight;
		pNode pSubRL = pSubR->_pLeft;
		pParent->_pRight = pSubRL;//调节pSubRL
		if (pSubRL)
			pSubRL->_pParent = pParent;
		pNode pPParent = pParent->_pParent;//记录pParent的双亲
		pSubR->_pLeft = pParent;//调节pSubR
		pParent->_pParent = pSubR;
		pSubR->_pParent = pPParent;//调节pSubR的双亲
		if (pParent == _pRoot)
		/*if (pPParent == NULL)*/
			_pRoot = pSubR;
		else
		{
			if (pParent == pPParent->_pLeft)
				pPParent->_pLeft = pSubR;
			else if (pParent == pPParent->_pRight)
				pPParent->_pRight = pSubR;
		}
		pSubR->_bf = 0;
		pParent->_bf = 0;
	}

	void RotateR(pNode pParent)
	{
		pNode pSubL = pParent->_pLeft;
		pNode pSubLR = pSubL->_pRight;
		pParent->_pLeft = pSubLR;//调节pSubLR
		if (pSubLR)
			pSubLR->_pParent = pParent;
		pNode pPParent = pParent->_pParent;//记录pParent的双亲
		pSubL->_pRight = pParent;
		pParent->_pParent = pSubL;
		pSubL->_pParent = pPParent;//调节pSubL的双亲
		if (pParent == _pRoot)
		/*if (pPParent == NULL)*/
			_pRoot = pSubL;
		else
		{
			if (pParent == pPParent->_pLeft)
				pPParent->_pLeft = pSubL;
			else
				pPParent->_pRight = pSubL;
		}
		pSubL->_bf = 0;
		pParent->_bf = 0;
	}

	void RotateLR(pNode pParent)
	{
		pNode pSubL = pParent->_pLeft;
		pNode pSubLR = pSubL->_pRight;
		int bf = pSubLR->_bf;
		RotateL(pSubL);
		RotateR(pParent);
		if (bf == -1)
			pParent->_bf = 1;
		else if (bf == 1)
			pSubL->_bf = -1;
	}

	void RotateRL(pNode pParent)
	{
		pNode pSubR = pParent->_pRight;
		pNode pSubRL = pSubR->_pLeft;
		int bf = pSubRL->_bf;
		RotateR(pSubR);
		RotateL(pParent);
		if (bf == -1)
			pSubR->_bf = 1;
		else if (bf == 1)
			pParent->_bf = -1;
	}

	void _InOrder(pNode pRoot)
	{
		if (pRoot)
		{
			_InOrder(pRoot->_pLeft);
			cout << "<" << pRoot->_key << "," << pRoot->_value << ">" << endl;
			_InOrder(pRoot->_pRight);
		}
	}
private:
	pNode _pRoot;
};
void Test()
{
	int arr[] = { 4,2,6,1,3,5,15,7,16,14 };
	AVLTree<int,int> t;
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
		t.Insert(arr[i],arr[i]);
	t.InOrder();

	if (t.IsBalance())
		cout << "平衡" << endl;
	else
		cout << "不平衡" << endl;
	cout << "树的高度为:";
	cout << t.Height() << endl;
}
原文链接:https://www.f2er.com/datastructure/382243.html

猜你在找的数据结构相关文章