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

快来打我* 2022-06-01 10:18 191阅读 0赞

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

**一. AVL树概念：**

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

> 1.它的左右子树都是AVL树；
> 
> 2.左子树和右子树高度之差（简称平衡因子）的绝对值不超过1；

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

**二. 平衡化旋转**

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

首先有几点需要说明：

> 1.图中结点右侧紫色的数字表示该节点的平衡因子；
> 
> 2.平衡因子等于右子树高度与左子树高度之差；
> 
> 3.在写代码时，除了要改变结点指针的指向，还需要注意平衡因子的变化。

1）左单旋及右单旋：

![SouthEast][]

![SouthEast 1][]

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

![SouthEast 2][]

![SouthEast 3][]

![SouthEast 4][]

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

![SouthEast 5][]

![SouthEast 6][]

![SouthEast 7][]

**三. 结点的插入**

在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;
    }

![SouthEast 8][]

[SouthEast]: /images/20220601/bc4cc4c53c664f5aa977a60290abbbd1.png
[SouthEast 1]: /images/20220601/c97fb485b8774bb0bf0419c8d3ed3855.png
[SouthEast 2]: /images/20220601/da661b99d83543c1965288326e4bb069.png
[SouthEast 3]: /images/20220601/36c3fed5d91c4cadb958644d5c08c1b8.png
[SouthEast 4]: /images/20220601/3ae13ac2f3e14502a6ca77db20526e3c.png
[SouthEast 5]: /images/20220601/5205381407db4617b2b1608201775d65.png
[SouthEast 6]: /images/20220601/f3128c702f404c45820aa5a75f490e34.png
[SouthEast 7]: /images/20220601/8ddd299664484e63b8937b88c8733621.png
[SouthEast 8]: /images/20220601/7d6d2f16f62247dc8a376799a7aa0427.png