268-AVL树的学习(左,右单旋转)

快来打我* 2022-11-17 15:00 146阅读 0赞

## AVL树（平衡二叉树） ##

## AVL树的定义 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
**代码：**

typedef int KeyType;
    typedef struct AVLNode
    {
        
    	AVLNode* leftchild;
    	AVLNode* parent;
    	AVLNode* rightchild;
    	int balance; // -1 ,0 ,1（平衡因子） 
    	KeyType key;
    }AVLNode, * AVLTree;

AVLNode* Buynode(KeyType kx)
    {
        
    	AVLNode* s = (AVLNode*)malloc(sizeof(AVLNode));
    	if (nullptr == s) exit(1);
    	memset(s, 0, sizeof(AVLNode));
    	s->key = kx;
    	return s;
    }
    void Freenode(AVLNode* p)
    {
        
    	free(p);
    }

## AVL树的插入 ##

![在这里插入图片描述][20210410214024502.png_pic_center]

## 平衡化旋转 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][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]  
**50看作A，20看作B，70看作C，60看作D，80看作E**  
**树的高度都为1（h）**  
**如果插入一个节点E，h就变成h+1。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]  
**50的平衡因子变为2。一旦失去平衡性要进行调整。**  
**旋转要保证，中序遍历是从小到大，平衡因子趋近于0。**

## 如何旋转 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]

## 左单旋转 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]

void RotateLeft(AVLTree& root, AVLNode* ptr)
    {
        
    	AVLNode* newroot = ptr->rightchild;
    	newroot->parent = ptr->parent;// 1、保持双亲一致 
    	ptr->rightchild = newroot->leftchild;
    	if (newroot->leftchild != nullptr)//在只有3个结点的情况下 
    	{
        
    		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、 
    }

## 右单旋转 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/4278062c401f431a9793434b0cfd2f6f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/33df2b75250a4c298672003cdee4fca8.png
[20210410214024502.png_pic_center]: /images/20221022/55dfddd551254838aeb8fecec8c9d560.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/cd4a9786e23a4c1e93c72e2ba8719594.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/a02692d9b06b41fbb5a2912c1dce6e5e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221022/2429db8f23a54496b2a8ceeb624d9321.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221022/8a4f3f4a139e41f2b19fa55a7f70bcad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221022/f58cece653c3463ba08449a6644d6b72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221022/1175e3855a354607a69ccc708c22a6b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221022/a502e635892c4ba8be07920a8a0a2d20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221022/77c083ba93184ee3879f723f31af8305.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221022/43bdae29b3674154a0c1143068c1cccd.png