C++高级数据结构算法#自平衡的二叉搜索树(AVL树)

浅浅的花香味﹌ 2022-01-14 05:07 123阅读 0赞

### 文章目录 ###

*   *   *  前言
         *  自平衡的二叉搜索树(AVL树)
         *  AVL树的结构定义
         *  AVL树的旋转
         *   *  AVL树失衡的4种情况 :
             *  失衡的处理方法
             *   *  左旋操作
                 *  右旋操作
                 *  左平衡操作
                 *  右平衡操作
         *  AVL树插入操作
         *  AVL树的删除操作
         *  判断一颗二叉搜索树是不是平衡树
         *  判断一颗二叉树是否是平衡二叉搜索树

### 前言 ###

二叉搜索树是基于折半查找思想设计的一种数据结构 . 通过分析 , 可知二叉搜索树的确可以在很大程度上提高搜索的效率 . 然而 , **尽管当二叉搜索树处于平衡状态的时候 , 其操作时间复杂度为O(logN)** ,  **但当二叉搜索树是单支树时 , 其搜索效率为O(N) .** **可见 , 二叉搜索树的平衡性是影响其操作效率的关键 .** 由此出发 , 学者们设计了第一个平衡二叉搜索树 , 即AVL树 .

### 自平衡的二叉搜索树(AVL树) ###

**定义 :** AVL树的左右子树都是AVL树 , 且左子树和右子树的高度之差的绝对值不超过 1.

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

### AVL树的结构定义 ###

**与BST树不同的是 , AVL树中还加入了高度 height , 存储节点的高度**

template<typename T>
    class AVL
    {
        
    public:
    	AVL() {
         _root = nullptr; }
    private:
    	struct AVLNode
    	{
        
    		AVLNode(T data = T())
    			:_data(data)
    			, _left(nullptr)
    			, _right(nullptr)
    			, _height(1) 
    		{
        }
    		T _data;
    		AVLNode *_left;
    		AVLNode *_right;
    		int _height; // 存储的就是节点的高度
    	};	
    	AVLNode *_root;
    
    	// 返回节点的高度
    	int height(AVLNode *node)const
    	{
        
    		return node == nullptr ? 0 : node->_height;
    	}
    
    	// 返回左右子树最高的层数
    	int maxHeight(AVLNode *node1, AVLNode *node2)
    	{
        
    		return height(node1) > height(node2) ? height(node1) : height(node2);
    	}
    };

**注 : AVL的平衡性是一种相对平衡, 而非绝对平衡 .**  
**如果给AVL树中每个节点都附加一个数字 , 该数字指示该节点右子树的高度减去左子树的高度所得的高度差 , 那么这个数字即为该节点的平衡因子 .平衡因子只能取 -1 , 0 或 1 .**  
**对于有n个节点的AVL树 , 其高度可保持在\[log\_2n\]左右 , 平均搜索复杂度也可保持为O(logn)**

### AVL树的旋转 ###

作为一种平衡二叉树 , AVL树的基本操作(insert,remove,find)与普通的二叉搜索树无异 . **但是其中有些操作可能会破坏AVL树的平衡性 , 实时地保护这种平衡性非常重要 , 通常通过调整树的结构 , 使之保持平衡 , 这种用以进行平衡化处理的操作被称为旋转 .**

#### AVL树失衡的4种情况 : ####

*  1.向某节点的左子树中插入一个左孩子 , 如图a
 *  2.向某节点的右子树中插入一个右孩子 , 如图b
 *  3.向某节点的左子树中插入一个右孩子 , 如图c
 *  4.向某节点的右子树中插入一个左孩子 , 如图d

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 1]

#### 失衡的处理方法 ####

**被分为两类 :即单旋和双旋**  
**单旋 : 分为左旋和右旋  
双旋 : 分为左平衡(先左后右) 和 右平衡(先右后左)**

在插入一个新节点后, 就需要从插入位置沿通向根的路径回溯 , 检查各节点的平衡因子 . 如果在某一节点发现高度不平衡 , 则停止回溯 , 然后从发生不平衡的起点起 , 沿刚才的回溯的路径取下两层的节点 .  
**如果三个节点处于一条直线上 , 则采用单旋进行平衡化 ; 如果三个节点不处于一条直线上(形如 : " < " ; " > " ) , 则采用双旋进行平衡化**

*  **右旋 : 形如 " / " 的直线上 , 以3个呈直线排列的节点中间节点为轴 , 进行顺时针旋转 . 该节点的右子树则变成其原父节点的左子树**
 *  **左旋 : 形如 " \\ " 的直线上 , 以3个呈直线排列的节点中间节点为轴 , 进行逆时针旋转 , 该节点的左子树则变成其原父节点的右子树**
 *  **左平衡(先左后右) : 形如 "＜＂ 的折线上 , 以3个呈折线排列的节点中的末节点为轴 , 进行逆时针旋转(左旋) , 使末节点代替中间节点的位置, 也就是让末节点成为原中间节点的父节点 , 而末节点的左子树则变成原中间节点的右子树 . 这时 , 三个节点将成直线排列 , 再以新的中间节点为轴做右旋操作 .**
 *  **右平衡(先右后左) ; 形如 " > " 的折线上 , 以3个呈折线排列的节点中的末节点为轴 , 进行顺时针旋转(右旋) , 使末节点代替中间节点的位置 , 也就是让末节点成为原中间节点的父节点 , 而末节点的右子树则变成原中间节点的左子树 . 这时 , 三个节点将成直线排列 , 再以新的中间节点为轴做左旋操作 .**

##### 左旋操作 #####

左旋 : 形如 " \\ " 的直线上 , 以3个呈直线排列的节点中间节点为轴 , 进行逆时针旋转 , 该节点的左子树则变成其原父节点的右子树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 2]

// 左旋转操作 以node为根节点进行左旋转，返回旋转后的根节点
    	/*
    	左旋 : 形如 " \ " 的直线上 , 以3个呈直线排列的节点中间节点为轴 , 进行逆时针旋转 , 该节点的左子树则变成其原父节点的右子树
    
    	流程 : 
    	[以三个节点最上面的节点作为根节点(局部)传入]
    	记录当前三个节点的中间节点
    	中间节点的左子树变成其原父节点的右子树
    	其原父节点变成中间节点的左孩子
    	更新原父节点的高复和中间节点的高度
    	返回旋转后的根节点
    	*/
    	AVLNode* leftRotate(AVLNode *node)
    	{
        
    		AVLNode* child = node->_right;  //记录当前三个节点的中间节点
    		node->_right = child->_left;  //中间节点的左子树变成其原父节点的右子树
    		child ->_left = node;  //其原父节点变成中间节点的左孩子
    		node->_height = maxHeight(node->_left,node->_right);  //更新原父节点的高度
    		child->_height = maxHeight(child->_left,child->_right);   //更新中间节点的高度
    		return child;  //返回旋转后的根节点
    	}

##### 右旋操作 #####

右旋 : 形如 " / " 的直线上 , 以3个呈直线排列的节点中间节点为轴 , 进行顺时针旋转 . 该节点的右子树则变成其原父节点的左子树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 3]

// 右旋转操作
    	/*
    	右旋 : 形如 " / " 的直线上 , 以3个呈直线排列的节点中间节点为轴 , 进行顺时针旋转 . 该节点的右子树则变成其原父节点的左子树
    
    	流程 : 
    	[以三个节点最上面的节点作为根节点(局部)传入]
    	记录当前三个节点的中间节点
    	中间节点的右子树变成其原父节点的左子树
    	其原父节点变成中间节点的右孩子
    	更新原父节点的高复和中间节点的高度
    	返回旋转后的根节点
    	*/
    	AVLNode* rightRotate(AVLNode *node)
    	{
        
    		AVLNode* child = node->_left;  //记录当前三个节点的中间节点
    		node->_left= child->_right;  //中间节点的右子树变成其原父节点的左子树
    		child ->_right = node;  //其原父节点变成中间节点的右孩子
    		node->_height = maxHeight(node->_left,node->_right);  //更新原父节点的高复
    		child->_height = maxHeight(child->_left,child->_right);   //更新中间节点的高度
    		return child;  //返回旋转后的根节点
    	}

##### 左平衡操作 #####

左平衡(先左后右) : 形如 "＜＂ 的折线上 , 以3个呈折线排列的节点中的末节点为轴 , 进行逆时针旋转(左旋) , 使末节点代替中间节点的位置, 也就是让末节点成为原中间节点的父节点 , 而末节点的左子树则变成原中间节点的右子树 . 这时 , 三个节点将成直线排列 , 再以新的中间节点为轴做右旋操作 .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 4]

// 左平衡  左-右旋转
    	/*
    	左平衡(先左后右) : 形如 "＜＂ 的折线上 , 以3个呈折线排列的节点中的末节点为轴 , 进行逆时针旋转(左旋) , 
    	使末节点代替中间节点的位置,  也就是让末节点成为原中间节点的父节点 , 
        而末节点的左子树则变成原中间节点的右子树 . 这时 , 三个节点将成直线排列 , 再以新的中间节点为轴做右旋操作 .
    
    	流程 :
    	(先以折线的拐点作为根节点(局部)传入 , 再以三个节点最上面的节点作为根节点(局部)传入)
    	先进行左旋操作
    	再进行右旋操作
    	*/
    	AVLNode* leftBalance(AVLNode *node)
    	{
        
    		node->_left = leftRotate(node->_left);  //更新旋转后的中间节点
    		return rightRotate(node);
    	}

##### 右平衡操作 #####

右平衡(先右后左) ; 形如 " > " 的折线上 , 以3个呈折线排列的节点中的末节点为轴 , 进行顺时针旋转(右旋) , 使末节点代替中间节点的位置 , 也就是让末节点成为原中间节点的父节点 , 而末节点的右子树则变成原中间节点的左子树 . 这时 , 三个节点将成直线排列 , 再以新的中间节点为轴做左旋操作 .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 5]

// 右平衡  右-左旋转
    	/*
    	右平衡(先右后左) ; 形如 " > " 的折线上 , 以3个呈折线排列的节点中的末节点为轴 , 进行顺时针旋转(右旋) , 
    	使末节点代替中间节点的位置 , 也就是让末节点成为原中间节点的父节点 , 
        而末节点的右子树则变成原中间节点的左子树 . 这时 , 三个节点将成直线排列 , 再以新的中间节点为轴做左旋操作
    
    	流程 :
    	(先以折线的拐点作为根节点(局部)传入 , 再以三个节点最上面的节点作为根节点(局部)传入)
    	先进行右旋操作
    	再进行左旋操作
    	*/
    	AVLNode* rightBalance(AVLNode *node)
    	{
        
    		node->_right = rightRotate(node->_right);  //更新旋转后的中间节点
    		return leftRotate(node);
    	}

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

// 递归实现AVL树的插入操作  BST + 平衡
    	void insert(const T &val)
    	{
        
    		this->_root = insert(_root , val);
    	}

//以node为起始节点 , 插入val值
    	/*
    	插入的方法和BST相同  , 就是多了判断失衡
    	流程 : 
    	每次插入一个节点 , 都要判断是否失衡
    	如果失衡 , 判断是四种情况的哪一种 
    	如果是向某节点的左子树中插入一个左孩子 , 则进行右旋操作
    	如果是向某节点的左子树中插入一个右孩子 , 则进行左平衡操作
    	如果是向某节点的右子树中插入一个右孩子 , 则进行左旋操作
    	如果是向某节点的右子树中插入一个左孩子 , 则进行右平衡操作
    	最后更新节点的高度
    	*/
    	AVLNode* insert(AVLNode *node, const T &val)
    	{
        
    		//如果这是一个根节点 或者 叶子节点的子节点 (递归回退条件)
    		if (node == nullptr)
    		{
        
    			return new AVLNode(val);
    		}
    
    		if (node->_data > val)
    		{
        
    			node->_left = insert(node->_left, val);
    			// AVL添加的节点失衡判断
    			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);
    			// AVL添加的节点失衡判断
    			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
    		{
        
    			;
    		}
    
    		// 在递归回溯过程中，更新节点的高度值
    		node->_height = maxHeight(node->_left, node->_right) + 1;
    		return node;
    	}

### AVL树的删除操作 ###

// 递归实现AVL树的删除操作  BST + 平衡
    	void remove(const T &val)
    	{
        
    		this->_root = remove(_root,val);
    	}

// 以node为起始节点，删除值为val的节点
    	/*
    	删除操作和BST树的大致相同 , 在AVL树中 , 删除一个节点有可能造成失衡的情况
    	所以在每次删除后都要判断是否失衡 , 如果失衡 , 则进行平衡操作
    	
    	流程 :
    	先找到要删除的节点
    	找到节点后 , 先判断是否是情况3
    	如果是情况三的话 , 不能像BST树那种直接使用前驱结点来代替删除节点 , 如果这样的话有可能造成失衡
    	所以在这里要进行判断 , 删除节点的左子树和右子树谁更高 , 谁高就用那边的节点代替 , 即左子树高 , 则用前驱结点 ; 右子树高 , 则用后记节点
    	再判断是否是情况2和情况1
    	如果删除的节点在左子树中找到 , 则左子树的高度 -1 , 有可能造成右子树失衡
    	所以要判断是否失衡 
    	如果是右子树的右孩子造成的失衡 , 则进行左旋操作
    	如果是右子树的左孩子造成的失衡 , 则进行右平衡操作
    	如果是左子树的左孩子造成的失衡 , 则进行右旋操作
    	如果是左子树的右孩子造成的失衡 , 则进行左平衡操作
    	最后要更新节点的高度
    	*/
    	AVLNode* remove(AVLNode *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)
    			{
        
    				//因为不知到哪边的子树高 , 所以如果向BST树单纯的使用前驱节点代替可能还会造成失衡
    				//所以判断一下哪边高 , 左高就用前驱节点替换 , 右高就用后继结点替换
    				if (height(node->_left) >= height(node->_right))
    				{
        
    					// 前驱替换
    					AVLNode *pre = node->_left;
    					while (pre->_right != nullptr)
    					{
        
    						pre = pre->_right;
    					}
    					//替换
    					node->_data = pre->_data;
    					//替换之后,  找前驱结点
    					node->_left = remove(node->_left, pre->_data);
    				}
    				else
    				{
        
    					// 后继替换
    					AVLNode *post = node->_right;
    					while (post->_left != nullptr)
    					{
        
    						post = post->_left;
    					}
    					//替换
    					node->_data = post->_data;
    					//替换之后 , 找后继节点
    					node->_right = remove(node->_right, post->_data);
    				}
    			}
    			//情况2和情况1
    			else
    			{
        
    				//情况1
    				if (node->_left != nullptr)
    				{
        
    					AVLNode *left = node->_left;
    					delete node;
    					return left;
    				}
    				else if (node->_right != nullptr)
    				{
        
    					AVLNode *right = node->_right;
    					delete node;
    					return right;
    				}
    				else
    				{
        
    					//情况2
    					delete node;
    					return nullptr;
    				}
    			}
    		}
    
    		// 在递归回溯过程中，更新节点的高度值
    		node->_height = maxHeight(node->_left, node->_right) + 1;
    		return node;
    	}

### 判断一颗二叉搜索树是不是平衡树 ###

// 判断一颗二叉搜索树是不是平衡树，是返回true，否则返回false
    	/*
    	 * 判断一棵二叉搜索树是否是平衡树，因为题目条件已经说明了该树是一棵二叉搜索树
    	 * 了，因此我们直接从二叉搜索树与平衡二叉搜索树在性质上的重要区别入手，即一颗
     	 * 平衡二叉搜索树任一结点的左右子树高度差不超过 1，因此我们借助了求层数的函数
    	 * level(),在函数递归前判断是否满足该条件即可，若不满足，我们直接结束，若满足
    	 * 继续递归遍历其他结点即可。
     	*/
    	bool isAVL()
    	{
        
    		return isAVL(_root);
    	}
    	
    	//求层数
    	int level()
    	{
        
    		return level(_root);
    	}

bool isAVL(AVLNode *node)
    	{
        
    		if (node == nullptr)
    		{
        
    			return true;
    		}
    	
    		if (abs(level(node->_left) - level(node->_right)) > 1)
    		{
        
    			return false;
    		}
    		return isAVL(node->_left) && isAVL(node->_right);
    	}
    
    	int level(AVLNode* node)
    	{
        
    		if (node == nullptr)
    		{
        
    			return 0;
    		}
    	
    		int left = level(node->_left);
    		int right = level(node->_right);
    	
    		return left > right ? left +1: right +1;
    	}

### 判断一颗二叉树是否是平衡二叉搜索树 ###

/*
    	* 判断一颗二叉树是否是平衡二叉搜索树，我们之前有写过判断一颗二叉树是否是
    	* 二叉搜索树(BST)的代码，我们在递归函数前进行很多的条件判断，那么我们
    	* 只需要在这部分继续添加条件，判断是否是平衡树即可。
    	*/
    	bool isAVLTree()
    	{
        
    		return isAVLTree(_root);
    	}

bool isAVLTree(AVLNode* node)
    	{
        
    		static AVLNode* prev = nullptr;
    		if (node == nullptr)
    		{
        
    			return true;
    		}
    
    		if (!isAVLTree(node->_left))
    		{
        
    			return false;
    		}
    		//中序遍历 , 根据性质 , 是从小到大排列 , 如果出现后一个节点比前一个节点小 , 则说明不是BST树,  更不是AVL树
    		if (prev != nullptr && node->_data < prev->_data)
    		{
        
    			return false;
    		}
    	
    		if (abs(level(node->_left) - level(node->_right)) > 1)
    		{
        
    			return false;
    		}
    	
    		prev = node;
    		return isAVLTree(node->_right);
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70]: /images/20220114/7f99c5ad53854a78b2c5b07f164f12b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 1]: /images/20220114/5f6b67e31bb5402dac676aa8831a4f92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 2]: /images/20220114/42cac15abd7143aca2c6f742acb31ab1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 3]: /images/20220114/1c3d168862504194bbb7341d17b6bc06.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 4]: /images/20220114/7de6cf2ffd73466698dd3f50d77fc6b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 5]: /images/20220114/e190eaf2cda54d0abc0f1e19cce07375.png