C++实现AVL树

深碍√TFBOYSˉ_ 2023-09-28 18:03 4阅读 0赞

### C++实现AVL树 ###

*  前言
 *  一、AVL树的概念
 *  二、AVL树节点的定义
 *  三、AVL树的插入操作
 *  四、AVL树的旋转
 *   *  1. 左单旋
     *  2. 右单旋
     *  3. 左右双旋
     *  4. 右左双旋
     *  5. 总结
 *  五、AVL树的验证
 *   *  1、验证其为二叉搜索树
     *  2、验证其为平衡树
 *  六、AVL树的性能分析
 *  实现AVL树的完整代码

# 前言 #

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

# 一、AVL树的概念 #

1.  AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树（Self-Balancing Binary Search Tree,简称平衡二叉树）。
2.  AVL树的定义：它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
3.  AVL树的性质：

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

![这是一棵AVL树][AVL]  
**如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O ( l o g 2 n ) O(log\_2 n) O(log2n)，搜索时间复杂度 O ( l o g 2 n ) O(log\_2 n) O(log2n)。**

# 二、AVL树节点的定义 #

**AVL树节点的定义：**

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

# 三、AVL树的插入操作 #

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

> 1.  按照二叉搜索树的方式插入新节点
> 2.  调整平衡因子，若遇到平衡因子不符合AVL树的规则，则需要进行旋转操作

bool Insert(const pair<K, V>& kv)
    	{
        
    		// 1、搜索树的插入规则
    		// 2、看是否违反平衡规则，若违反则需要“旋转”处理
    		if (_root == nullptr)
    		{
        
    			_root = new Node(kv);
    			_root->_bf = 0;
    			return true;
    		}
    
    		Node* parent = nullptr;
    		Node* cur = _root;
    		while (cur)
    		{
        
    			if (cur->_kv.first < kv.first)
    			{
        
    				parent = cur;
    				cur = cur->_right;
    			}
    			else if (cur->_kv.first > kv.first)
    			{
        
    				parent = cur;
    				cur = cur->_left;
    			}
    			else
    			{
        
    				return false;
    			}
    		}
    
    		//找到了插入位置
    		cur = new Node(kv);
    		if (parent->_kv.first < kv.first)
    		{
        
    			parent->_right = cur;
    		}
    		else
    		{
        
    			parent->_left = cur;
    		}
    		cur->_parent = parent;
    
    		//更新平衡因子
    
    		while (parent) //最远更新到parent
    		{
        
    			if (cur == parent->_right)
    			{
        
    				parent->_bf++;
    			}
    			else
    			{
        
    				parent->_bf--;
    			}
    
    			//判断是否继续更新
    			if (parent->_bf == 0)
    			{
        
    				break;
    			}
    			else if (parent->_bf == -1 || parent->_bf == 1) // 此时插入结点的那边变高了
    			{
        
    				//继续更新祖先
    				cur = cur->_parent;
    				parent = parent->_parent;
    			}
    			else if (parent->_bf == -2 || parent->_bf == 2) // 插入结点使得本来高的一边又变高了 -> 旋转
    			{
        
    				if (parent->_bf == 2 && cur->_bf == 1) // 左单旋
    				{
        
    					// 左单旋
    				}
    				else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋
    				{
        
    					// 右单旋
    				}
    				else if (parent->_bf == -2 && cur->_bf == 1) // 左右双旋
    				{
        
    					// 左右双旋
    				}
    				else if (parent->_bf == 2 && cur->_bf == -1) // 右左双旋
    				{
        
    					// 右左双旋
    				}
    				else
    				{
        
    					assert(false);
    				}
    				break;
    			}
    			else
    			{
        
    				assert(false);  // 树本来就存在问题
    			}
    		}
    		return true;
    	}

# 四、AVL树的旋转 #

**如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种。**

## 1. 左单旋 ##

**新节点插入较高右子树的右侧—右右，即需要左单旋。**

图示：  
![69da044dbc734584a59e4859f1fd4558.png][]  
左单旋代码;

void RotateL(Node* parent)
    	{
        
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    
    		parent->_right = subRL;
    		if(subRL)
    			subRL->_parent = parent;
    
    		Node* grandParent = parent->_parent;
    		subR->_left = parent;
    		parent->_parent = subR;
    
    		if (parent == _root)
    		{
        
    			_root = subR;
    			subR->_parent = nullptr;
    		}
    		else
    		{
        
    			if (parent == grandParent->_left)
    			{
        
    				grandParent->_left = subR;
    			}
    			else
    			{
        
    				grandParent->_right = subR;
    			}
    			subR->_parent = grandParent;
    		}
    		subR->_bf = parent->_bf = 0; //更新平衡因子
    	}

## 2. 右单旋 ##

**新节点插入较高左子树的左侧—左左，即需要右单旋。**  
图示:  
![ad5ce2dcd5df405881264a7bd1a396e1.png][]  
右单旋代码：

void RotateR(Node* parent)
    	{
        
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    
    		parent->_left = subLR;
    		if (subLR)
    			subLR->_parent = parent;
    
    		Node* grandParent = parent->_parent;
    		subL->_right = parent;
    		parent->_parent = subL;
    
    		if (parent == _root)
    		{
        
    			_root = subL;
    			subL->_parent = nullptr;
    		}
    		else
    		{
        
    			if (parent == grandParent->_left)
    			{
        
    				grandParent->_left = subL;
    			}
    			else
    			{
        
    				grandParent->_right = subL;
    			}
    			subL->_parent = grandParent;
    		}
    
    		subL->_bf = parent->_bf = 0;
    
    	}

## 3. 左右双旋 ##

**新节点插入较高左子树的右侧—左右，即需要先左单旋再右单旋。**  
图示：  
![cf6a94ce6a5a45db8a41b6da392376c7.png][]

**此时在60的子树插入一个新节点就会引起左右双旋，插入分为左子树插入和右子树插入。这两种情况的插入完成之后对其平衡因子的更新有所不同，因此旋转完成后需要讨论更新其平衡因子。**  
![2fc747758da84d0c8f6755b432139654.png][]

![628243a2738246c48fcfaa349cb71d8e.png][]  
**当60结点不存在时也需要单独讨论**  
![50e411e70b7f4e6c82529859acea0aea.png][]

实现代码：复用左、右单旋。

void RotateLR(Node* parent)
    	{
        
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    
    		int bf = subLR->_bf;
    
    		RotateL(parent->_left);
    		RotateR(parent);
    
    
    		//更新平衡因子
    		if (1 == bf)
    			subL->_bf = -1;
    		else if (-1 == bf)
    			parent->_bf = 1;
    		else
    		{
        
    			assert(false);
    		}
    	}

## 4. 右左双旋 ##

**新节点插入较高右子树的左侧—右左，即需要先右单旋再左单旋。**  
右左双旋与左右双旋类似。  
![97f1a0a755b54c21a6bf3d27097d8a52.png][]

代码实现：

void RotateRL(Node* parent)
    	{
        
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    
    		int bf = subRL->_bf;
    
    		RotateR(parent->_right);
    		RotateL(parent);
    
    		//更新平衡因子
    		if (1 == bf)
    		{
        
    			parent->_bf = -1;
    		}
    		else if(-1 == bf)
    		{
        
    			subR->_bf = 1;
    		}
    		else
    		{
        
    			assert(false);
    		}
    	}

## 5. 总结 ##

假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑

1.  parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR，当subR的平衡因子为1时，执行左单旋；当subR的平衡因子为-1时，执行右左双旋。
2.  parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL，当subL的平衡因子为-1是，执行右单旋；当subL的平衡因子为1时，执行左右双旋。
3.  旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新。

# 五、AVL树的验证 #

**AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：**

## 1、验证其为二叉搜索树 ##

**如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。**

验证代码如下：

void InOrder()
    	{
        
    		_InOrder(_root);
    		cout << endl;
    	}
    		void _InOrder(Node* root)
    	{
        
    		if (root == nullptr)
    			return;
    
    		_InOrder(root->_left);
    		cout << root->_kv.first << " ";
    		_InOrder(root->_right);
    	}

## 2、验证其为平衡树 ##

验证规则：

1.  每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子的情况)
2.  节点的平衡因子是否计算正确

验证代码如下：

bool IsBalanceTree()
    {
        
    	return _IsBalanceTree(_root);
    }
    
    bool _IsBalanceTree(Node* root)
    	{
        
    		// 空树也是AVL树
    		if (nullptr == root)
    			return true;
    
    		// 计算root节点的平衡因子：即root左右子树的高度差
    		int leftHeight = _Height(root->_left);
    		int rightHeight = _Height(root->_right);
    		int diff = rightHeight - leftHeight;
    
    		// 如果计算出的平衡因子与root的平衡因子不相等，或者
    		// root平衡因子的绝对值超过1，则一定不是AVL树
    		if (abs(diff) >= 2) //每个节点子树高度差的绝对值不超过1
    		{
        
    			cout << root->_kv.first << "节点平衡因子异常" << endl;
    			return false;
    		}
    
    		if (diff != root->_bf) //节点的平衡因子是否计算正确
    		{
        
    			cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
    			return false;
    		}
    
    		// root的左和右如果都是AVL树，则该树一定是AVL树
    		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
    	}

# 六、AVL树的性能分析 #

*  **AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 O ( l o g 2 n ) O(log\_2 n) O(log2n)**。
 *  **但是如果要对AVL树做一些结构修改的操作，性能非常低下**，比如：**插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置**。因此：**如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合**。

# 实现AVL树的完整代码 #

#pragma once
    #include<assert.h>
    #include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    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;
    
    public:
    	bool Insert(const pair<K, V>& kv)
    	{
        
    		// 1、搜索树的插入规则
    		// 2、看是否违反平衡规则，若违反则需要“旋转”处理
    		if (_root == nullptr)
    		{
        
    			_root = new Node(kv);
    			_root->_bf = 0;
    			return true;
    		}
    
    		Node* parent = nullptr;
    		Node* cur = _root;
    		while (cur)
    		{
        
    			if (cur->_kv.first < kv.first)
    			{
        
    				parent = cur;
    				cur = cur->_right;
    			}
    			else if (cur->_kv.first > kv.first)
    			{
        
    				parent = cur;
    				cur = cur->_left;
    			}
    			else
    			{
        
    				return false;
    			}
    		}
    
    		//找到了插入位置
    		cur = new Node(kv);
    		if (parent->_kv.first < kv.first)
    		{
        
    			parent->_right = cur;
    		}
    		else
    		{
        
    			parent->_left = cur;
    		}
    		cur->_parent = parent;
    
    		//更新平衡因子
    
    		while (parent) //最远更新到parent
    		{
        
    			if (cur == parent->_right)
    			{
        
    				parent->_bf++;
    			}
    			else
    			{
        
    				parent->_bf--;
    			}
    
    			//判断是否继续更新
    			if (parent->_bf == 0)
    			{
        
    				break;
    			}
    			else if (parent->_bf == -1 || parent->_bf == 1) // 此时插入结点的那边变高了
    			{
        
    				//继续更新祖先
    				cur = cur->_parent;
    				parent = parent->_parent;
    			}
    			else if (parent->_bf == -2 || parent->_bf == 2) // 插入结点使得本来高的一边又变高了 -> 旋转
    			{
        
    				if (parent->_bf == 2 && cur->_bf == 1) // 左单旋
    				{
        
    					RotateL(parent);
    				}
    				else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋
    				{
        
    					RotateR(parent);
    				}
    				else if (parent->_bf == -2 && cur->_bf == 1) // 左右双旋
    				{
        
    					RotateLR(parent);
    				}
    				else if (parent->_bf == 2 && cur->_bf == -1) // 右左双旋
    				{
        
    					RotateRL(parent);
    				}
    				else
    				{
        
    					assert(false);
    				}
    				break;
    			}
    			else
    			{
        
    				assert(false);  // 树本来就存在问题
    			}
    		}
    		return true;
    	}
    
    	void InOrder()
    	{
        
    		_InOrder(_root);
    		cout << endl;
    	}
    
    	bool IsBalanceTree()
    	{
        
    		return _IsBalanceTree(_root);
    	}
    
    	vector<vector<int>> levelOrder() {
        
    		vector<vector<int>> vv;
    		if (_root == nullptr)
    			return vv;
    
    		queue<Node*> q;
    		int levelSize = 1;
    		q.push(_root);
    
    		while (!q.empty())
    		{
        
    			// levelSize控制一层一层出
    			vector<int> levelV;
    			while (levelSize--)
    			{
        
    				Node* front = q.front();
    				q.pop();
    				levelV.push_back(front->_kv.first);
    				if (front->_left)
    					q.push(front->_left);
    
    				if (front->_right)
    					q.push(front->_right);
    			}
    			vv.push_back(levelV);
    			for (auto e : levelV)
    			{
        
    				cout << e << " ";
    			}
    			cout << endl;
    
    			// 上一层出完，下一层就都进队列
    			levelSize = q.size();
    		}
    
    		return vv;
    	}
    
    	int Height()
    	{
        
    		return _Height(_root);
    	}
    private:
    
    	bool _IsBalanceTree(Node* root)
    	{
        
    		// 空树也是AVL树
    		if (nullptr == root)
    			return true;
    
    		// 计算root节点的平衡因子：即root左右子树的高度差
    		int leftHeight = _Height(root->_left);
    		int rightHeight = _Height(root->_right);
    		int diff = rightHeight - leftHeight;
    
    		// 如果计算出的平衡因子与root的平衡因子不相等，或者
    		// root平衡因子的绝对值超过1，则一定不是AVL树
    		if (abs(diff) >= 2) // 每个节点子树高度差的绝对值不超过1
    		{
        
    			cout << root->_kv.first << "节点平衡因子异常" << endl;
    			return false;
    		}
    
    		if (diff != root->_bf) // 节点的平衡因子是否计算正确
    		{
        
    			cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
    			return false;
    		}
    
    		// root的左和右如果都是AVL树，则该树一定是AVL树
    		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
    	}
    
    
    	void _InOrder(Node* root)
    	{
        
    		if (root == nullptr)
    			return;
    
    		_InOrder(root->_left);
    		cout << root->_kv.first << " ";
    		_InOrder(root->_right);
    	}
    
    	int _Height(Node* root)
    	{
        
    		if (root == nullptr)
    			return 0;
    
    		int lh = _Height(root->_left);
    		int rh = _Height(root->_right);
    
    		return lh > rh ? lh + 1 : rh + 1;
    	}
    
    	void RotateL(Node* parent)
    	{
        
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    
    		parent->_right = subRL;
    		if(subRL)
    			subRL->_parent = parent;
    
    		Node* grandParent = parent->_parent;
    		subR->_left = parent;
    		parent->_parent = subR;
    
    		if (parent == _root)
    		{
        
    			_root = subR;
    			subR->_parent = nullptr;
    		}
    		else
    		{
        
    			if (parent == grandParent->_left)
    			{
        
    				grandParent->_left = subR;
    			}
    			else
    			{
        
    				grandParent->_right = subR;
    			}
    			subR->_parent = grandParent;
    		}
    		subR->_bf = parent->_bf = 0; //更新平衡因子
    	}
    
    	void RotateR(Node* parent)
    	{
        
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    
    		parent->_left = subLR;
    		if (subLR)
    			subLR->_parent = parent;
    
    		Node* grandParent = parent->_parent;
    		subL->_right = parent;
    		parent->_parent = subL;
    
    		if (parent == _root)
    		{
        
    			_root = subL;
    			subL->_parent = nullptr;
    		}
    		else
    		{
        
    			if (parent == grandParent->_left)
    			{
        
    				grandParent->_left = subL;
    			}
    			else
    			{
        
    				grandParent->_right = subL;
    			}
    			subL->_parent = grandParent;
    		}
    
    		subL->_bf = parent->_bf = 0;
    
    	}
    
    	void RotateLR(Node* parent)
    	{
        
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    
    		int bf = subLR->_bf;
    
    		RotateL(parent->_left);
    		RotateR(parent);
    
    
    		//更新平衡因子
    		if (1 == bf)
    			subL->_bf = -1;
    		else if (-1 == bf)
    			parent->_bf = 1;
    		else
    		{
        
    			assert(false);
    		}
    	}
    
    	void RotateRL(Node* parent)
    	{
        
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    
    		int bf = subRL->_bf;
    
    		RotateR(parent->_right);
    		RotateL(parent);
    
    		//更新平衡因子
    		if (1 == bf)
    		{
        
    			parent->_bf = -1;
    		}
    		else if(-1 == bf)
    		{
        
    			subR->_bf = 1;
    		}
    		else
    		{
        
    			assert(false);
    		}
    	}
    
    private:
    	Node* _root = nullptr;
    };

[AVL]: https://img-blog.csdnimg.cn/529d99cf6f834bd789399f6a47bfab35.png
[69da044dbc734584a59e4859f1fd4558.png]: https://img-blog.csdnimg.cn/69da044dbc734584a59e4859f1fd4558.png
[ad5ce2dcd5df405881264a7bd1a396e1.png]: https://img-blog.csdnimg.cn/ad5ce2dcd5df405881264a7bd1a396e1.png
[cf6a94ce6a5a45db8a41b6da392376c7.png]: https://img-blog.csdnimg.cn/cf6a94ce6a5a45db8a41b6da392376c7.png
[2fc747758da84d0c8f6755b432139654.png]: https://img-blog.csdnimg.cn/2fc747758da84d0c8f6755b432139654.png
[628243a2738246c48fcfaa349cb71d8e.png]: https://img-blog.csdnimg.cn/628243a2738246c48fcfaa349cb71d8e.png
[50e411e70b7f4e6c82529859acea0aea.png]: https://img-blog.csdnimg.cn/50e411e70b7f4e6c82529859acea0aea.png
[97f1a0a755b54c21a6bf3d27097d8a52.png]: https://img-blog.csdnimg.cn/97f1a0a755b54c21a6bf3d27097d8a52.png