【C++进阶】：AVL树(平衡因子)

本是古典何须时尚 2024-03-08 08:26 79阅读 0赞

#### AVL树 ####

*  一.概念
 *  二.插入
 *   *  1.搜索二叉树
     *  2.平衡因子
 *  三.旋转
 *   *  1.更新平衡因子
     *  2.旋转
     *   *  1.左单旋
         *  2.右单旋
         *  3.先右旋再左旋
         *  4.先左旋再右旋
 *  四.完整代码

## 一.概念 ##

> **二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。**

![在这里插入图片描述][123e53ca06d648fd8c415fb541544b17.png]

## 二.插入 ##

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

1.  按照二叉搜索树的方式插入新节点
2.  调整节点的平衡因子

### 1.搜索二叉树 ###

![在这里插入图片描述][2c06e4b63b0b4d0a80b46113379bd8d3.png]

### 2.平衡因子 ###

![在这里插入图片描述][1cd711ac35424fc7af8bfa1782fdf93b.png]

一颗树如何插入会影响节点的平衡因子呢？（平衡因子是右节点减去左节点）

![在这里插入图片描述][2b3c4a68d5b0410abf2e3264d0c67a68.png]

如果我们插在6的左边，那么6的平衡因子减一，同理7的左子树高度加一，那么7的平衡因子减一，再继续向上5的右子树的最高高度并没有发生改变，所以5的平衡因子不发生改变。

![在这里插入图片描述][045e589937df468686d2ad94eb0e2592.png]  
同理，插在6的右边，6的平衡因子加一，7的平衡因子减一。

![在这里插入图片描述][01ab34690f6d4649a904010a9a046071.png]  
如果插在9的右边，那么8的平衡因子就会变为2，说明此树不平衡。

> **总结：  
> 1.新镇在左，parent平衡因子减减。  
> 2.新增在右，parent平衡因子加加。  
> 3.如果更新后的parent平衡因子为0，说明parent所在的树的高度不变，不会再影响祖先，不用再继续更新了。  
> 4如果更新后parent的平衡因子为1或者-1，那么就需要继续向上更新。  
> 5.如果更新后，parent平衡因子为2或-2，说明该树不平衡，对parent所在的子树进行旋转。**

## 三.旋转 ##

### 1.更新平衡因子 ###

> **由上面分析可以知道更新结束的条件是平衡因子为0或者更新到根节点。**

首先在每个节点里加入平衡因子

![在这里插入图片描述][d77775fc873e45579f690b980cc89e45.png]

接着在插入的同时更新平衡因子

![在这里插入图片描述][da5945736eaf4c46bae1a89dfd292671.png]

### 2.旋转 ###

> **旋转要保持的要求：  
> 1.旋转后也是搜索二叉树。  
> 2.变成平衡树并且降低树的高度。**

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

#### 1.左单旋 ####

![在这里插入图片描述][66638d5b0c5c475a903ed552419d3de2.png]  
![在这里插入图片描述][5f11e820d9ca48a4b9cc2ffab7d183f6.png]

通过观察我们可以发现，我们其实只需要移动蓝色的节点就可以实现左旋。我们将这三个节点分别记录，然后修改它们的内部属性即可。  
![在这里插入图片描述][df0bcab939064fdba3d576dadbd45d17.png]

![在这里插入图片描述][ef4c3f41ea94481eb6b50559cb1087aa.png]

#### 2.右单旋 ####

![在这里插入图片描述][5100a7b173304791ac089a2c7967fff0.png]  
![在这里插入图片描述][05b24b75c874486085fc7f458694dc65.png]

#### 3.先右旋再左旋 ####

![在这里插入图片描述][949611495cf24717b92215f3d7f77a83.png]  
![在这里插入图片描述][e5a355dfd19f43b28643563b105803cf.png]

这里的旋转并不难，直接复用就可以.  
![在这里插入图片描述][b1cbdbccb47f4bd5bcf9e6e421e7815d.png]

困难的部分是如何调控平衡因子，插入的位置不同，平衡因子也不同分三种情况讨论。

![在这里插入图片描述][1b8d08bd93184658ac365fb3ea03f254.png]

![在这里插入图片描述][378c9e6dc2b9464d946b3effde213ba9.png]

#### 4.先左旋再右旋 ####

同理，左右旋与上文一样，需要分三种情况来讨论。

![在这里插入图片描述][5d5682063f9e4f39951ee09af3dd20b0.png]

![在这里插入图片描述][dca7dddc7ce14432b69db28b12d9be31.png]

## 四.完整代码 ##

*测试*

#include"KVL.h"
    #include<vector>
    
    int main()
    {
        
    	AVLTree<int,int> t;
    	srand(time(0));
    	vector<int>a;
    	for (int i = 0; i < 100; i++)
    		a.push_back(rand());
    	for (auto x : a)
    		t.Insert(make_pair(x,x));
    	t.Print();
    }

*树*

#include<iostream>
    #include<assert.h>
    using namespace std;
    
    template<class K,class V>
    struct KVLTreeNode
    {
        
    	pair<K, V>_kv;
    	KVLTreeNode<K, V>* _left;
    	KVLTreeNode<K, V>* _right;
    	KVLTreeNode<K, V>* _parent;
    	int _bf;//平衡因子
    	KVLTreeNode(const pair<K,V>&kv)
    		:_kv(kv)
    		,_left(nullptr)
    		,_right(nullptr)
    		,_parent(nullptr)
    		,_bf(0)
    	{
        }
    };
    
    template<class K,class V>
    class AVLTree
    {
        
    public:
    	typedef KVLTreeNode<K,V> Node;
    	
    	bool Insert(const pair<K, V>& kv)
    	{
        
    		if (_root == nullptr)
    		{
        
    			_root = new Node(kv);
    			return true;
    		}
    
    		Node* cur = _root;
    		Node* parent = _root;
    		while (cur)
    		{
        
    			if (kv.first < cur->_kv.first)
    			{
        
    				parent = cur;
    				cur = cur->_left;
    			}
    			else if (kv.first > cur->_kv.first)
    			{
        
    				parent = cur;
    				cur = cur->_right;
    			}
    			else
    				return false;
    		}
    		cur = new Node(kv);
    		if (kv.first < parent->_kv.first)
    		{
        
    			parent->_left = cur;
    			cur->_parent = parent;
    		}
    		else
    		{
        
    			parent->_right = cur;
    			cur->_parent = parent;
    		}
    
    		//控制平衡
    		while (parent)
    		{
        
    			if (cur == parent->_left)
    			{
        
    				parent->_bf--;
    			}
    			else // if (cur == parent->_right)
    			{
        
    				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);
    				}
    				break;
    			}
    			else
    			{
        
    				assert(false);
    			}
    		}
    		return true;
    	}
    	void RotateL(Node* parent)
    	{
        
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    		Node* ppnode = parent->_parent;//记录父节点的父节点
    
    		//父节点的右孩子变成curleft
    		parent->_right = curleft;
    		if(curleft)//细节注意curleft为空时不能操作
    			curleft->_parent = parent;
    		//父节点变为cur的左孩子
    		cur->_left = parent;
    		parent->_parent = cur;
    		
    		//如果原来父节点是根节点
    		if (parent == _root)
    		{
        
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		else//如果不是根节点判断它应该是左儿子还是右儿子
    		{
        
    			if (ppnode->_left == parent)
    			{
        
    				ppnode->_left = cur;
    			}
    			else
    			{
        
    				ppnode->_right = cur;
    
    			}
    			cur->_parent = ppnode;
    		}
    
    		parent->_bf = cur->_bf = 0;
    	}
    	void RotateR(Node* parent)
    	{
        
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
    		Node* pphead = parent->_parent;
    
    		//父节点到cur右边
    		cur->_right=parent;
    		parent->_parent = cur;
    		//父节点的左孩子变成curright
    		parent->_left = curright;
    		if (curright)
    			curright->_parent = parent;
    		//cur的父节点变为原来父节点的父节点
    		if (pphead)//如果不是根节点
    		{
        
    			if (pphead->_left == parent)
    				pphead->_left = cur;
    			else
    				pphead->_right = cur;
    			cur->_parent = pphead;
    		}
    		else
    		{
        
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		parent->_bf = cur->_bf = 0;
    	}
    	void RotateRL(Node* parent)
    	{
        
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    		int bf = curleft->_bf;
    
    		RotateR(parent->_right);
    		RotateL(parent);
    		//第一种情况
    		if (bf == 0)
    		{
        
    			parent->_bf = cur->_bf = 0;
    		}
    		//第二种情况
    		else if (bf == 1)
    		{
        
    			parent->_bf = -1, cur->_bf = 0, curleft->_bf = 0;
    		}
    		//第三种情况
    		else if(bf==-1)
    		{
        
    			cur->_bf = 1, curleft->_bf = 0, parent->_bf = 0;
    		}
    		//其他情况错误
    		else
    		{
        
    			assert(false);
    		}
    	}
    	void RotateLR(Node* parent)
    	{
        
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
    		int bf = curright->_bf;
    
    		RotateL(parent->_left);
    		RotateR(parent);
    		if (bf == 0)
    		{
        
    			parent->_bf = cur->_bf = 0;
    		}
    		else if (bf == 1)
    		{
        
    			parent->_bf = curright->_bf = 0, cur->_bf = -1;
    		}
    		else if (bf == -1)
    		{
        
    			parent->_bf = 1, cur->_bf = curright->_bf = 0;
    		}
    		else
    		{
        
    			assert(false);
    		}
    	}
    
    	void Print()
    	{
        
    		Print(_root);
    	}
    	void Print(Node* root)
    	{
        
    		if (root == nullptr) return;
    
    		Print(root->_left);
    		cout << root->_kv.second << ' ';
    		Print(root->_right);
    	}
    private:
    	Node* _root=nullptr;
    };

[123e53ca06d648fd8c415fb541544b17.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/c19f416af9f3469fa6bd9b2f7f97c05b.png
[2c06e4b63b0b4d0a80b46113379bd8d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/3008535d34f24bfca4e38240dd99c7ca.png
[1cd711ac35424fc7af8bfa1782fdf93b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/ac274cca8d0e4fea9c20201ca946da69.png
[2b3c4a68d5b0410abf2e3264d0c67a68.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/d507c01855584ec99bbaea7c5b5d9d23.png
[045e589937df468686d2ad94eb0e2592.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/313d0465a3a4457b9d4747fc1e41aa14.png
[01ab34690f6d4649a904010a9a046071.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/cf39c0c3b21947f789bbf777bf39e49d.png
[d77775fc873e45579f690b980cc89e45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/24acd31943c743a39ac1e1186e8132b6.png
[da5945736eaf4c46bae1a89dfd292671.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/dc3091c5881d40f49b94043325f7ce57.png
[66638d5b0c5c475a903ed552419d3de2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/532edc9d225c4bdbb9122b5a12c27e5d.png
[5f11e820d9ca48a4b9cc2ffab7d183f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/5d23d4ffcd2c4046a0a78b6967db0821.png
[df0bcab939064fdba3d576dadbd45d17.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/fd4c4575b953433696ede16b833e1901.png
[ef4c3f41ea94481eb6b50559cb1087aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/ba3f74475ab84f37be99beee5113a2d6.png
[5100a7b173304791ac089a2c7967fff0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/d8bec87168df40058b61da0857c5efdc.png
[05b24b75c874486085fc7f458694dc65.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/63e997e6a0314daebdd30891ab7b62d5.png
[949611495cf24717b92215f3d7f77a83.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/ac95175d94d14e058eb8c1a124eebe85.png
[e5a355dfd19f43b28643563b105803cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/e9ade6b336f84495a60dc3ccf5ae8d22.png
[b1cbdbccb47f4bd5bcf9e6e421e7815d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/95782bd643d34ebdaf1db3c5368e24e1.png
[1b8d08bd93184658ac365fb3ea03f254.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/90fd6a49e5484f18b20049789574c09f.png
[378c9e6dc2b9464d946b3effde213ba9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/dc8e87f2ab3245ac8486a94dee71ea0e.png
[5d5682063f9e4f39951ee09af3dd20b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/308aa37eafc44a73bbee2b7fbf5bbd0c.png
[dca7dddc7ce14432b69db28b12d9be31.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/ba768c37a1044e7a93ed75fe5645c170.png