AVL树平衡二叉搜索树详解--实现插入

Myth丶恋晨 2024-04-01 13:26 75阅读 0赞

#### 目录 ####

*   *  AVL树的概念
     *  AVL树的定义
     *   *  Node节点的定义
         *  树的定义
     *  AVL树的插入操作
     *   *  平衡因子更新情况
         *  AVL树的旋转(+调平衡因子)
         *   *  右单旋
             *  左单旋
             *  右左双旋
             *  左右双旋
     *  AVL树整体插入代码
     *  验证AVL树
     *  AVL树的性能分析

*  我们之前所学习的二叉搜索树由于可能出现**单边树的极端情况，导致效率为O(N)**。因此，本文将介绍AVL树即平衡搜索二叉树，将可以有效的避免单边树的情况。

### AVL树的概念 ###

当向[二叉搜索树][Link 1]中插入新结点后，如果能保证每个结点的**左右子树高度之差的绝对值不超过1**(需要对树中的结点进行调整)，**即可降低树的高度**，从而减少平均搜索长度。

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

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

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

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

### AVL树的定义 ###

#### Node节点的定义 ####

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;//平衡因子，右子树高度-左子树高度
    
    	AVLTreeNode(const pair<K, V>& kv)
    		:_kv(kv)
    		, _left(nullptr)
    		, _right(nullptr)
    		, _parent(nullptr)
    		, _bf(0)
    	{
        }
    };

#### 树的定义 ####

template <class K, class V>
    class AVLTree
    {
        
        typedef AVLTreeNode<K, V> Node
    private:
    	Node* _root;
    private:
        //旋转相关函数;
    	void* RotateL(Node* parent);
    	void* RotateR(Node* parent);
    	void* RotateRL(Node* parent);
    	void* RotateLR(Node* parent);
    public:
    	;
    	AVLTree()
    		:_root(nullptr)
    	{
        }
    
    	bool Insert(const pair<K, V>& kv)//插入
    	{
        }
    
    	bool Earse();//类似于BST树的删除，只不过需要旋转+要调整平衡因子，我们不做深究;
    
    
    	//中序遍历验证
    	void _Inorder(Node* root)
    	{
        
    		if (!root) return;
    		_Inorder(root->_left);
    		 cout << (_root->_kv).first<<" : "<<((_root->_kv)).second << endl;
    		_Inorder(root->_right);
    	}
    	void Inorder() {
         _Inorder(_root) };
    
    
    
    
    };

### AVL树的插入操作 ###

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

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

#### 平衡因子更新情况 ####

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

至于上面平衡因子的更新，我们需要借助“旋转”操作来更新：

#### AVL树的旋转(+调平衡因子) ####

##### 右单旋 #####

> 当结点的平衡因子出现异常时，若左子树高度高于右子树高度，那么该结点需要进行右单旋调整。  
> 如图,进行右单旋的条件为：**parent的bf为-2且subL的bf为-1**。

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

void RotateR(Node* parent)
    	{
        
    		//改变链接关系;
    		Node* SubL = parent->_left;
    		Node* SubLR = SubL->_right;
    
    		parent->_left = SubLR;
    		SubL->_right = parent;
    		//小心SubLR为空
    		if (SubLR) SubLR->_parent = parent;
    
    		//更新_parent指针
    		Node* pparent = parent->_parent;
    		parent->_parent = SubL;
    		SubL->_parent = pparent;
    
    		if (_root == parent) _root = SubL;
    		else
    		{
        
    			if (pparent->_left == parent)
    			{
        
    				pparent->_left = SubL;
    			}
    			else
    			{
        
    				pparent->_right = SubL;
    			}
    		}
    		//更新平衡因子;
    		SubL->_bf = parent->_bf = 0;
    
    	}

##### 左单旋 #####

> 与右单旋类似的，若左子树高度高于右子树高度，那么该结点需要进行左单旋调整。  
> 如图,进行左单旋的条件为：**parent的bf为2且subL的bf为1**

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

void RotateL(Node* parent)
    	{
        
    		Node* SubR = parent->_right;
    		Node* SubRL = SubR->_left;
    
    		parent->_right = SubRL;
    		SubR->_left = parent;
    
    		if (SubRL)  SubRL->_parent = parent;
    
    		Node* pparent = parent->_parent;
    		parent->_parent = SubR;
    		SubR->_parent = pparent;
    		if (parent == _root) _root = SubR;
    		else
    		{
        
    			if (pparent->_left == parent) {
        
    				pparent->_left = SubR;
    			}
    			else {
        
    				pparent->_right = SubR;
    			}
    		}
    
    		//平衡因子
    		SubR->_bf = parent->_bf = 0;
    	}

##### 右左双旋 #####

> 如图,进行右左双旋的条件为：**parent的bf为2且subR的bf为-1**.

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

//别忘记每次调整完毕需要调整平衡因子！仔细画图分析;
    	void RotateRL(Node* parent)
    	{
        
    		Node* SubR = parent->_right;
    		Node* SubRL = SubR->_left;
    		int bf = SubRL->_bf;   //以SubRL这个为依据，分类讨论后续的平衡因子情况； 
    
    		RotateR(SubR);
    		RotateL(parent);
    		
    
    		if (_bf == 0) {
        //SubRL就是新增节点; 
    			SubR->_bf = parent->_bf = SubRL->_bf = 0;
    		}
    		else if (_bf == -1) {
        //设无关的子树高度为h，SuBRL的左右子树根据分类情况设置为一个1，一个-1，然后画图旋转判断新的bf;
    			SubR->_bf = 1;
    			parent = 0;
    			SubRL = 0;
    		}
    		else if (_bf == 1) {
        
    			SubR->_bf = 0;
    			parent = -1;
    			SubRL = 0;
    		}
    		else {
        //非法情况;
    			assert(_bf);
    		}
    
    	}

##### 左右双旋 #####

> 如图,进行左右双旋的条件为：**parent的bf为-2且subL的bf为1**.

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

void RotateLR(Node* parent)
    	{
        
    		Node* SubL = parent->_left;	
    		Node* SubLR = SubL ->_right;
    		int bf = SubLR->_bf;
    
    		RotateR(SubL);
    		RotateL(parent);
    
    
    		if (_bf == 0) {
        //SubRL就是新增节点;
    			SubL->_bf = parent->_bf = SubLR->_bf= 0;
    		}
    		else if (_bf == 1) {
        
    			SubL->_bf = -1;
    			SubLR->_bf = 0;
    			parent->_bf = 0;
    		}
    		else if (_bf == -1) {
        
    			SubL->_bf = 0;
    			SubLR->_bf = 0;
    			parent->_bf = 1;
    		}
    		else {
        //非法情况;
    			assert(_bf);
    		}
    	}

### AVL树整体插入代码 ###

bool Insert(const pair<K, V>& kv)//插入
    	{
        	
    		//类似于二叉搜索树; 先find位置，再insert
    		if (_root == nullptr) {
        
    			_root = new Node(kv);
    			return true;
    		}
    
    		Node* cur = _root;
    		Node* parent = cur;
    		while (cur)
    		{
        
    			if ((cur->_kv).first > kv.first) {
        
    				parent = cur;
    				cur = cur->_left;
    			}
    			else if ((cur->_kv).first < kv.first) {
        
    				parent = cur;
    				cur = cur->_right;
    			}
    			else {
        //数据冗余 插入错误
    				return false;
    			}
    		}
    		
    		cur =new Node(kv);
    		cur->_bf = 0;
    		cur->_parent = parent;
    
    	
    		if (parent->_kv.first >cur->_kv.first) {
        
    			parent->_left = cur;	
    			//(parent->_bf)--;		 调平衡因子放下面while里轮训来,重要作用！！不然只能调一次，parent的parent就没法变了;
    		}
    		else {
        
    			parent->_right = cur;
    			//(parent->_bf)++;
    		}
    		
    
    		//插完了 得整体调整_bf了; 可能连续向上调整，也可能 不 调 整 插入以后父节点bf变0？
    		
    	
    		//核心部分！
    		while (parent)
    		{
        
    			if (parent->_left == cur)
    				parent->_bf--;
    			else
    				parent->_bf++;
    
    			//不用调整 插完父节点bf=0了; 直接break 插入完毕
    			if (parent->_bf == 0) break;
    			//可能需要调整，插完 父节点出现gap了，父节点虽然满足 但是得 向上继续看是否调整; 《一层一层节点向上检索需不需要旋转;》
    			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) {
        //这里画图分析条件，因为parent，cur都向上迭代过一次了，所以其实parent == pparent， cur == parent，他们两个就是我们用来判断旋转方法的节点了！
    					RotateR(parent);
    				}
    				//左单旋
    				else if (parent->_bf == 2 && cur->_bf == 1) {
        
    					RotateL(parent);
    				}
    				//左 右双旋
    				else if (parent->_bf == -2 && cur->_bf == 1) {
        
    					RotateLR(parent);
    				}
    				//右 左双旋
    				else if (parent->_bf == 2 && cur->_bf == -1) {
        
    					RotateRL(parent);
    				}
    				break;//调整完必满足AVL性质 break 插入完毕
    			}
    			else//若parent的bf为其他情况（不是 0 or +-1 or +-2），说明搜索树的平衡已经破坏，报错
    				assert(false);
    
    
    		}
    
    		
    		return true;
    
    	}

### 验证AVL树 ###

> 中序遍历即可验证BST树的性质，下面是刷题中用到的自底向上判断avl树;

int flag = 1;//是否是AVL树的标记;
    template<class K,class V>
    int f(AVLTreeNode<K,V>* cur)
    {
        
    	if (!cur) return 0;
    	int a = f(cur->_left) + 1;//自底向上递归
    	int b = f(cur->_right) + 1;
    	if (a - b > 1 || b - a > 1) flag = false;
    	return max(a, b);
    }
    template<class K, class V>
    bool isBalanced(AVLTreeNode< K, V>* root) {
        
    
    	f(root);
    	return flag;
    }
    
    int main()
    {
        
        
    	
    
    	AVLTree <int ,char> t;
    	t.Insert({
         1,'a' });
    	t.Insert({
         2,'a' });
    	t.Insert({
         3,'a' });
    	t.Insert({
         3,'a' });
    	t.Insert({
         4,'a' });
    	t.Insert({
         5,'a' });
    	t.Insert({
         6,'a' });
    	t.Insert({
         7,'a' });
    	
    	t.Inorder();
    
    	cout << "是否是AVL树结构?1 or 0 : " << flag << endl;
        return 0;
    
    }

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

### AVL树的性能分析 ###

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

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

后续红黑树针对avl树的优化即将登场！

[Link 1]: https://so.csdn.net/so/search?q=%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91&spm=1001.2101.3001.7020
[8329515c9c15494aa67f982a12c264a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9313ba9d81ad466bbb1c36edfe142eed.png
[7270e79c1f564774b7193c4081bf947a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/fa1abbd4fb714cd8a96c11dfcbd46df3.png
[079173446c11440ba47487c1d1e6f7af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/636618b69a564f21b1b0e0458de397b1.png
[ea0da83d73a748898f53273d3032ae51.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/70f48cacc74a469799cad01245e9e1b8.png
[f0a66ea2e3a0472b9aa31b50081b9ca2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/2ec8d1c42a2141509c5f1e6dd49df815.png
[3683f50ba9b74899832d6d3568c0cd4e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b349e777f91842e681732be840e01ddc.png
[ff86a40ff4914b70a31b01d3a790ad65.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c4b1e62289e04d3486645b186b9afb1d.png