269-AVL树(左，右双旋转)

港控/mmm° 2022-11-18 13:58 150阅读 0赞

## AVL树(左，右双旋转) ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
**我们依次插入数据结点56,90,67。最后形成了“折线”，所以我们要进行双旋转**

![在这里插入图片描述][20210413174032672.png_pic_center]  
**我们依次插入数据结点78,34,45。最后形成了“折线”，所以我们要进行双旋转**

**我们要求的中序遍历是从小到大，旋转之后使得每个节点的平衡因子尽可能向0靠拢。**

**我们要借助左单旋转函数和右单旋转函数的能力来进行**  
![在这里插入图片描述][20210413174255466.png_pic_center]  
**我们把34和45，以45为基准，进行左单旋转，34放下来，45放上去，再以45位基准，把78进行右单旋转。**  
![在这里插入图片描述][2021041317443224.png_pic_center]

## 我们来看下面这个问题 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
(a)是平衡二叉树，我们可能在D或者F或者G插入数据，如果我们在D插入数据，D的高度由h变成h+1，我们回溯到B的时候，B的平衡因子由0变为-1，我们回溯到A，A的平衡因子由-1变成-2，我们的这3个结点在斜线上，进行右单旋转就OK了。  
也有可能我们在F或者G插入数据，无论插入到F还是G底下，E的树高h，如果插入到的是G底下，E的高度变成h+1，回溯到B，B的平衡因子变为1，回溯到A，A的平衡因子变为-2。形成折线。我们以E为基准对B进行左旋，然后把A进行右旋。

## 我们再来看下面这张图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
**首先通过E节点进行转轴，对B进行左单旋转操作，变成c图。我们以E为基准点，对A进行右单旋转。最终的图形是d图。**

**如何知道进行1次右单旋转或者1次左单旋转或者1次左单旋转后再进行1次右单旋转？**  
![在这里插入图片描述][20210413181822526.png_pic_center]  
**如何判断这3个节点在一条直线上。如果是左平衡，节点的平衡因子从上到下依次为-2，-1，就在一条斜线上。（进行单旋转）**

**如果是下图，节点的平衡因子从上到下依次是-2,1，就是在一条折线上。（进行双旋转）**  
![在这里插入图片描述][20210413182045601.png_pic_center]

## 左单旋转的代码 ##

void RotateLeft(AVLTree& root, AVLNode* ptr)
    {
        
    	AVLNode* newroot = ptr->rightchild;
    	newroot->parent = ptr->parent;// 1
    	ptr->rightchild = newroot->leftchild;
    	if (newroot->leftchild != nullptr)
    	{
        
    		newroot->leftchild->parent = ptr;// 2
    	}
    	newroot->leftchild = ptr;
    	if (ptr->parent == nullptr)
    	{
        
    		root = newroot;
    	}
    	else
    	{
        
    		if (ptr->parent->leftchild == ptr)
    		{
        
    			ptr->parent->leftchild = newroot;
    		}
    		else
    		{
        
    			ptr->parent->rightchild = newroot;
    		}
    	}
    	ptr->parent = newroot;	 // 3
    }

## 右单旋转的代码 ##

void RotateRight(AVLTree& root, AVLNode* ptr) 
    {
        
    	AVLNode* newroot = ptr->leftchild;
    	newroot->parent = ptr->parent;//1
    	ptr->leftchild = newroot->rightchild;
    	if (newroot->rightchild != nullptr)
    	{
        
    		newroot->rightchild->parent = ptr;
    	}
    	newroot->rightchild = ptr;
    	if (ptr->parent == nullptr)
    	{
        
    		root = newroot;
    	}
    	else
    	{
        
    		if (ptr->parent->leftchild == ptr)
    		{
        
    			ptr->parent->leftchild = newroot;
    		}
    		else
    		{
        
    			ptr->parent->rightchild = newroot;
    		}
    	}
    	ptr->parent = newroot;
    }

## 左平衡的程序代码 ##

**如果形成的是下图这种结构。**  
![在这里插入图片描述][20210413182327201.png_pic_center]  
在A节点发生了不平衡，ptr指向A节点，在哪个节点发生了不平衡，就把哪个节点的指针给给ptr，我们定义2个指针。一个指向其左孩子，一个指向空。  
**case ==-1的情况**  
对B进行右单旋转  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]  
**case==1的情况**  
情况：是跑到E这个地方插入了。  
不管在F还是G插入，总会导致E的树高增高。导致B的平衡因子变成1，A的平衡因子变为-2。形成折线。我们要进行双旋转。  
![在这里插入图片描述][20210413183205418.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]  
**我们要进行先左后右的双旋转。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]  
**如果我们是在G插入节点**，A的左子树要指向G，B的右子树要指向F，E的左边要指向B，E的右边要指向A，并且E作为根节点。E的平衡因子是1，A的配合因子是0，B的平衡因子是-1。  
**如果是嵌套的case的值是-1，则是在F节点插入节点。**

**E的平衡因子是0的可能性：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]

void LeftBalance(AVLTree& tree, AVLNode* ptr)//左平衡,对不平衡的AVL树进行左平衡 
    {
        
    	AVLNode* leftsub = ptr->leftchild, * rightsub = nullptr;
    	switch (leftsub->balance)
    	{
        
    	case 0: cout << "Left balance \n"; break;
    	case -1://如果是等于-1，是右单旋转 
    		ptr->balance = 0;
    		leftsub->balance = 0;
    		RotateRight(tree, ptr);
    		break;
    	case 1://进行双旋转 
    		rightsub = leftsub->rightchild;
    		switch (rightsub->balance)
    		{
        
    		case 1:
    			ptr->balance = 0;
    			leftsub->balance = -1;
    			break;
    		case 0:	     
    			ptr->balance = 0;
    			leftsub->balance = 0;
    			break;
    		case -1:    
    			ptr->balance = 1;
    			leftsub->balance = 0;
    			break;
    		}
    		rightsub->balance = 0;
    		RotateLeft(tree,leftsub);
    		RotateRight(tree,ptr);
    		break;
    	}
    }

## 右平衡的程序代码 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]  
首先进行左单旋转  
![在这里插入图片描述][2021041318590978.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]

void RightBalance(AVLTree& tree, AVLNode* ptr)//右平衡 
    {
        
    	AVLNode* rightsub = ptr->rightchild, * leftsub = nullptr;
    	switch (rightsub->balance)
    	{
        
    	case 0: cout << "right balance \n"; break;
    	case 1://左单旋转 
    		ptr->balance = 0;
    		rightsub->balance = 0;
    		RotateLeft(tree, ptr);
    		break;
    	case -1://双旋转 
    		leftsub = rightsub->leftchild;
    		switch (leftsub->balance)
    		{
        
    		case 1:
    			ptr->balance = -1;
    			rightsub->balance = 0;
    			break;
    		case 0: 
    			ptr->balance = 0;
    			rightsub->balance = 0;
    			break;
    		case -1: 
    			ptr->balance = 0;
    			rightsub->balance = 1;
    			break;
    		}
    		leftsub->balance = 0;
    		RotateRight(tree, rightsub);
    		RotateLeft(tree, ptr);
    		break;
    	}
    }

## 插入数据 ##

bool Insert(AVLTree& tree, KeyType kx)//插入 
    {
        
    
    	Adjust_AVL(tree, p);
    	return true;
    }

**进行调整**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]  
**在E插入一个数据130**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]  
**如果我们插入一个67，然后插入34，然后插入100。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]  
**则不需要调整。  
如果我们再插入23，45**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 13]

**高度不变，不需要回溯。**  
**如果我们再插入120。90。也不需要回溯**![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 14]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 15]  
**我们再插入130和140。需要进行旋转，旋转后，不需要回溯**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 16]  
**调整后，不会使得平衡因子超过2。**  
**一旦调用平衡函数，高度不会发生变化。**

void Adjust_AVL(AVLTree& tree, AVLNode* ptr)//调整AVL树 
    {
        
    	AVLNode* pa = ptr->parent;//指向双亲 
    	bool high = true;//高度初始化为真
    	while (high && pa != nullptr)//还没到根节点 
    	{
        
    		if (pa->rightchild == ptr)//ptr插入到右子树 
    		{
        
    			switch (pa->balance)//看平衡因子 
    			{
        
    			case 0: pa->balance = 1; break;//右边插入，变为1 
    			case -1:
    			//右边低 左边高，给右边插入 
    				pa->balance = 0;
    				high = false;//高度不变，不需要回溯
    				break;
    			case 1:
    			//右边高 ，左边低，给右边插入，调用右平衡 
    				RightBalance(tree,pa);
    				high = false;//高度不变，不需要回溯				
    				break;
    			}
    		}
    		else //在双亲的左边 
    		{
        
    			switch (pa->balance)
    			{
        
    			case 0: pa->balance = -1; break;//在左边插入，变为-1 
    			case 1: //右边高左边低，在左边插入 
    				pa->balance = 0; 
    				high = false;//高度不变，不需要回溯
    				break;
    			case -1:
    		    //右边低左边高，在左边插入 
    				LeftBalance(tree, pa);//调动左平衡 
    				high = false;//高度不变，不需要回溯
    				break;
    		    }
    		}
    		ptr = pa;
    		pa = ptr->parent;//回溯 
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/964ab62be06a45f2932158ce64a64e31.png
[20210413174032672.png_pic_center]: /images/20221022/31fa233dc3bd4ee0ab996f20deecaca5.png
[20210413174255466.png_pic_center]: /images/20221022/5188aa1cf7564830a7b7d2313680be95.png
[2021041317443224.png_pic_center]: /images/20221022/ae36070aa224481c9929ab5031fcad2d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/b5ff292d037147c0949c584dda4121e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/f5e6edf8214947d0983d0fe8aa8bf140.png
[20210413181822526.png_pic_center]: /images/20221022/6eb6e4daeb68429fb74372822ee34124.png
[20210413182045601.png_pic_center]: /images/20221022/b349230ddf424d56828b51b94a75ccdc.png
[20210413182327201.png_pic_center]: /images/20221022/15e356838c954cd49e4920aa1b8ed584.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/4babe5d29a4e4c5bb7fe4127f3e90e55.png
[20210413183205418.png_pic_center]: /images/20221022/800aecd4be89438a916f6735bd56eb5c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221022/de21ff777ae54e8ba57f415b62d74874.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221022/1fe86be787ff47659057c5744f443f45.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221022/cd7fb81a2d284e42a38435b34d28bee5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221022/3a9e932f1b954eb782620bd34cb2ee68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221022/d2dc01663d3845e7b8481c3177875cf0.png
[2021041318590978.png_pic_center]: /images/20221022/b6fe35024b51417ca2bd9800d4b2d5c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221022/b0f91d71559a4e4c98dff34b4630f54c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221022/859bf2168751455689fc8d72f54fc8f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221022/0654a7908b0543e1836dd3dc9cd22e30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221022/96ed3aa2b7cb4b6caf19484324097552.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221022/f68ded3bacbf45dd8d85742399e46e3d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20221022/757b8b49403d4e47bf10ac23ceb588fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 15]: /images/20221022/64b8780c3f154cc9b7833b43f6b4a0ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 16]: /images/20221022/dbb184c8c93740bc8aac54a8e639f200.png