【数据结构】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;
}

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

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