408-AVL树学习大全

朱雀 2022-09-04 13:46 104阅读 0赞

**AVL树又叫  
二叉平衡搜索树**  
**是在BST树的基础上增加节点平衡操作**  
（**节点平衡**：任意节点的左右子树高度差不超过1）（可以是0,1，-1）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
**上图也称作BST树，但是搜索的时间复杂度不能达到对数时间了！**  
**已经相当于一个链表了！**

## AVL树的旋转操作 ##

**AVL树为了维护节点平衡引入的四种节点旋转操作**

节点失衡的原因是由于：  
**1、左孩子的左子树太高了**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
我们看到：40节点失衡了！不满足AVL树的概念了！  
所以我们为了得到一个平衡树（AVL）树，以达到log以2为底的n的时间复杂度  
要进行旋转操作  
**顺时针的右旋转操作！！！**  
以40为轴，把30转到40这个位置，把40转下来了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]  
**如果原本30还有一个右孩子，怎么办？**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]  
**因为x都是大于30，小于40的（搜索树的性质）**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]  
**左右子树有变的节点要改变高度值，进行更新**  
**node和child的高度值都要更新哦！！！**

**2、右孩子的右子树太高了：**  
![在这里插入图片描述][1c969d65b19f4d8d81122c627583e160.png]  
**40的左右子树高度差超过1，失衡了。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]  
**所以我们现在要做个左旋转操作！**  
以40为轴，50旋转上去，50的左孩子就是40了，x就是按照大于40小于50的范围

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 7]  
**然后node和child的高度值都要更新哦！！！**

**3、左孩子的右子树太高了：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 8]  
一次旋转是解决不了问题的！  
**得做 左 右 旋转！** **（左平衡操作）**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 9]  
**首先，以child为根节点做一个左旋转，变成**  
![在这里插入图片描述][920b71d285c7423cb3d5d48ebadcf5ae.png]  
**然后就以40为根节点，做一个右旋转操作**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 10]

**4、由于右孩子的左子树太高了：**  
![在这里插入图片描述][feda00d5c9be4923bbadf0ca8a7eed8c.png]  
**得 进行 右 左 旋转** **（右平衡操作）**

**首先以child为根节点进行一个右旋转**

![在这里插入图片描述][85bfc266fb754697b983f2f76d2f7cd8.png]  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 11][]  
**然后再以40节点为轴做一个左旋转操作**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 12]  
**我们把这2种情况的节点的高度更新和旋转操作都封装在左右旋转的函数上！！！**

**AVL树的旋转操作就是以上4种情况了，解决了局部平衡，全局是否平衡，需要向上回溯！**

## AVL树的代码定义 ##

//AVL树   二叉平衡搜索树
    template<typename T>
    class AVLTree
    {
        
    public:
    	//AVL的初始化
    	AVLTree() :root_(nullptr) {
        }
    private:
    	//定义AVL树节点类型
    	struct Node
    	{
        
    		Node(T data = T())
    			:data_(data)
    			, left_(nullptr)
    			, right_(nullptr)
    			, height_(1)
    		{
        }
    		T data_;
    		Node* left_;
    		Node* right_;
    		int height_;//记录节点的高度值
    	};
    	//指向根节点
    	Node* root_;
    };

## AVL树的节点平衡操作代码实现 ##

//返回节点的高度值
    int height(Node* node)
    {
        
    	return node == nullptr ? 0 : node->height_;
    }
    
    //右旋转操作 以参数node为轴做右旋转操作，并把新的根节点返回
    Node* rightRotate(Node* node)
    {
        
    	//节点旋转
    	Node* child = node->left_;//右旋转是左孩子的左子树太高了 
    	node->left_ = child->right_;
    	child->right_ = node;
    	//高度更新
    	node->height_ = max(height(node->left_), height(node->right_)) + 1;
    	child->height_ = max(height(child->left_), height(child->right_)) + 1;
    	//返回旋转后的子树新的根节点
    	return child;
    }
    
    //左旋转操作 以参数node为轴做左旋转操作，并把新的根节点返回
    Node* leftRotate(Node* node)
    {
        
    	//节点旋转
    	Node* child = node->right_;//右旋转是右孩子的右子树太高了 
    	node->right_ = child->left_;
    	child->left_ = node;
    	//高度更新
    	node->height_ = max(height(node->left_), height(node->right_)) + 1;
    	child->height_ = max(height(child->left_), height(child->right_)) + 1;
    	//返回旋转后的子树新的根节点
    	return child;
    }
    
    //左平衡操作 以参数node为轴做左-右旋转操作，并把新的根节点返回
    //左孩子的右子树太高了
    Node* leftBalance(Node* node)
    {
        
    	node->left_ = leftRotate(node->left_);
    	return rightRotate(node);
    }
    
    //右平衡操作 以参数node为轴做右-左旋转操作，并把新的根节点返回
    //右孩子的左子树太高了
    Node* rightBalance(Node* node)
    {
        
    	node->right_ = rightRotate(node->right_);
    	return leftRotate(node);
    }

## AVL树insert插入代码实现 ##

//AVL树的插入操作实现
    Node* insert(Node* node, const T& val)
    {
        
    	if (node == nullptr)//递归结束，已经找到插入的位置了
    	{
        
    		return new Node(val);//生成节点返回
    	}
    
    	if (node->data_ > val)//当前节点值大于要插入的值
    	{
        
    		node->left_ = insert(node->left_, val);//向左边插入
    		//添加1： 在递归回溯时判断节点是否失衡  node的左子树太高 node失衡了
    		if (height(node->left_) - height(node->right_) > 1)
    		{
        
    			if (height(node->left_->left_) >= height(node->left_->right_))
    			{
        
    				//节点失衡，由于左孩子的左子树太高
    				node = rightRotate(node);
    			}
    			else
    			{
        
    				//节点失衡，由于左孩子的右子树太高
    				node = leftBalance(node);
    			}
    		}
    	}
    	else if (node->data_ < val)//当前节点值小于要插入的值
    	{
        
    		node->right_ = insert(node->right_, val);//向右边插入
    		//添加2： 在递归回溯时判断节点是否失衡  node的右子树太高 node失衡了
    		if (height(node->right_) - height(node->left_) > 1)
    		{
        
    			if (height(node->right_->right_) >= height(node->right_->left_))
    			{
        
    				//节点失衡，由于右孩子的右子树太高
    				node = leftRotate(node);
    			}
    			else
    			{
        
    				//节点失衡，由于右孩子的左子树太高
    				node = rightBalance(node);
    			}
    		}
    	}
    	else
    	{
        
    		; //找到相同节点了，不用再往下递归了，直接向上回溯
    	}
    
    	//添加3： 因为子树中增加了新的节点  在递归回溯时检测更新节点高度
    	node->height_ = max(height(node->left_), height(node->right_)) + 1;
    
    	return node;
    }

## AVL树的删除操作 ##

//删除操作实现
    Node* remove(Node* node, const T& val)
    {
        
    	if (node == nullptr)//没找到要删除的节点
    	{
        
    		return nullptr;
    	}
    
    	if (node->data_ > val)//当前节点的值大于要删除的节点的值
    	{
        
    		node->left_ = remove(node->left_, val);
    		//左子树删除节点，可能造成右子树太高
    		if (height(node->right_) - height(node->left_) > 1)
    		{
        
    			if (height(node->right_->right_) >= height(node->right_->left_))
    			{
        
    				//右孩子的右子树太高
    				node = leftRotate(node);
    			}
    			else
    			{
        
    				//右孩子的左子树太高
    				node = rightBalance(node);
    			}
    		}
    	}
    	else if (node->data_ < val)//当前节点的值小于要删除的节点的值
    	{
        
    		node->right_ = remove(node->right_, val);
    		//右子树删除节点，可能导致左子树太高
    		if (height(node->left_) - height(node->right_) > 1)
    		{
        
    			if (height(node->left_->left_) >= height(node->left_->right_))
    			{
        
    				//左孩子的左子树太高
    				node = rightRotate(node);
    			}
    			else
    			{
        
    				//左孩子的右子树太高
    				node = leftBalance(node);
    			}
    		}
    	}
    	else
    	{
        
    		//找到了 先处理有两个孩子的节点删除情况
    		if (node->left_ != nullptr && node->right_ != nullptr)
    		{
        
    			//为了避免删除前驱或者后继节点造成节点失衡，谁高删除谁
    			if (height(node->left_) >= height(node->right_))
    			{
        
    				//删前驱节点
    				Node* pre = node->left_;
    				while (pre->right_ != nullptr)
    					pre = pre->right_;
    				node->data_ = pre->data_;//覆盖
    				node->left_ = remove(node->left_, pre->data_);//直接删前驱节点
    			}
    			else
    			{
        
    				//删后继节点
    				Node* post = node->right_;
    				while (post->left_ != nullptr)
    					post = post->left_;
    				node->data_ = post->data_;//覆盖
    				node->right_ = remove(node->right_, post->data_);//直接删除后继节点
    			}
    		}
    		else//删除节点，最多有一个孩子
    		{
        
    			if (node->left_ != nullptr)
    			{
        
    				Node* left = node->left_;
    				delete node;
    				return left;
    			}
    			else if (node->right_ != nullptr)
    			{
        
    				Node* right = node->right_;
    				delete node;
    				return right;
    			}
    			else//删除的是叶子节点，给父亲节点的孩子域返回空
    			{
        
    				return nullptr;
    			}
    		}
    	}
    	//更新节点高度
    	node->height_ = max(height(node->left_), height(node->right_)) + 1;
    	return node;//递归回溯过程中，把当前节点给父节点返回
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/3d53af7e62ee4b2ca74d5059395bf5ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/8027660f712e499eae84d70dfdd4074d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/1db766e2e4b548faa2105c31146579cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20220829/fcc5160cee6e49bca0db58d6f9f94c81.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/f35043bd7271466085b301163956e7fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]: /images/20220829/87c6c75eada14e5bb332800e0d1ca89c.png
[1c969d65b19f4d8d81122c627583e160.png]: /images/20220829/761dbbff8ae0485ba8d91b58960757ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]: /images/20220829/c03ce4dbe59441fe9d15ef8336543806.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6]: /images/20220829/12f6bf201c1d42a2ae215e85810f4d19.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 7]: /images/20220829/d968bbff4dcb449c9bd14162baba2536.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 8]: /images/20220829/6c8707286dda4cd9930db2757c178919.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 9]: /images/20220829/af13c6b22f89481492b0096a733dc1cd.png
[920b71d285c7423cb3d5d48ebadcf5ae.png]: /images/20220829/99370baa89ea42609cc64dfb5cc2753d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 10]: /images/20220829/3ddc70f72f474011ae115db579da4928.png
[feda00d5c9be4923bbadf0ca8a7eed8c.png]: /images/20220829/4e5f43ba69d84ffeba58a701d5491b23.png
[85bfc266fb754697b983f2f76d2f7cd8.png]: /images/20220829/3496d1c207db43cc8ef84a23c50d95df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 11]: /images/20220829/f61c6e960691498baebafe3e8e006bbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 12]: /images/20220829/3ba5245111f64f0eb6c063488cf0e104.png