【C++进阶】AVL树的模拟实现（附源码）

女爷i 2024-04-22 12:13 72阅读 0赞

## 一.AVL树的概念 ##

我们知道，二叉搜索树的效率很高，如果数据有序或接近有序二叉搜索树将退化为单支树，查  
找元素相当于在顺序表中搜索元素，效率低下，为了解决这个问题，AVL树（平衡二叉树）就出现了。

AVL树的性质：

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

![7ed9e4f53e654ee9ba931165bbb53c50.png][]

上图就是一个AVL树，每个节点上的数字为这个节点的平衡因子，绝对值不超过1 ；

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在  
O(log N)，搜索时间复杂度O(logN)。

接下来让我们来模拟实现AVL树。

有两种方法可以模拟实现AVL树：

*  使用平衡因子控制高度
 *  使用高度函数控制高度

本文将采用平衡因子的方法控制高度。

--------------------

## 二.AVL树的模拟实现 ##

### AVL树的节点 ###

这里我们使用三叉链的结构，便于找到父节点

*  左指针（\_left）
 *  右指针（\_right）
 *  父指针（\_parent）
 *  平衡因子（balance factor，简写 \_bf）

template <class K,class V>   //这里我们采用KV模型
    struct AVLTreeNode
    {
    	pair<K,V> _kv;
    	AVLTreeNode* _left;
    	AVLTreeNode* _right;
    	AVLTreeNode* _parent;
    	int _bf;
    
    	AVLTreeNode(const pair<K,V>& kv)
    		:_kv(kv)
    		,_left(nullptr)
    		,_right(nullptr)
    		,_parent(nullptr)
    		,_bf(0)
    	{}
    
    };

### AVL树的插入 Insert ###

首先就是找到新插入节点的位置，这和二叉搜索树的操作是一样的，插入完成后，不要忘记更新cur的parent指针。

插入完成后要更新平衡因子，下图说明了如何更新平衡因子

![46c7c5a120f344d68724b0e1792c6597.png][]

接下来将会详细说明如何旋转。

旋转一共分为四种情况：

1.  左单旋
2.  右单旋
3.  左右双旋
4.  右左双旋

#### 左单旋 ####

左单旋的条件是：cur的平衡因子为1并且parent的平衡因子为2，也就是单纯的右边高；

具体看下图：

![bd94b82e73e14eb092bfe208bbf8381a.png][]

void RotateL(Node*parent)  //左旋
    	{
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
            Node* ppnode = parent->_parent;   //提前保存parent的父节点，便于后续cur父指针的更新
    
    		parent->_right = curleft;  //核心操作1
            cur->_left = parent;  //核心操作2
    		if (curleft)  //当curleft不为nullptr时
    		{
    			curleft->_parent = parent;
    		}
    
    		parent->_parent = cur;   //parent的父指针指向cur
            //链接ppnode和cur
    		if (ppnode == nullptr)  //当ppnode为nullptr时，即parent是根节点，旋转的是整个子树
    		{
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		else
    		{
    			//当ppnode不为nullptr时，即parent不是根节点，旋转的是局部子树，此时要链接ppnode和子树
    			if (ppnode->_left == parent)
    			{
    				ppnode->_left = cur;
    			}
    			else
    			{
    				ppnode->_right = cur;
    			}
    
    			cur->_parent = ppnode;
    		}
    
    		parent->_bf = cur->_bf = 0;  //调整平衡因子
    
    	}

#### 右单旋 ####

右单旋的条件是：cur的平衡因子为-1并且parent的平衡因子为-2，也就是单纯的左边高

![efafc3e9aad040ffb443598f7505aed1.png][]

void RotateR(Node* parent)
    	{
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
            Node* ppnode = parent->_parent;  //提前保存好parent得父节点，便于后续cur父指针的更新
    
    		parent->_left = curright;   //核心操作1
            cur->_right = parent;    //核心操作2
    		if (curright)   //更新curright的父指针，注意要判断是否为空
    		{
    			curright->_parent = parent;
    		}
    		
    		parent->_parent = cur;   //更新parent的父指针
            //链接cur与ppnode
    		if (ppnode == nullptr)
    		{
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		else
    		{
    			if (ppnode->_left == parent)
    			{
    				ppnode->_left = cur;
    			}
    			else
    				ppnode->_right = cur;
    			cur->_parent = ppnode;
    		}
    
    		parent->_bf = cur->_bf = 0;   //调整平衡因子
    	}

#### 左右双旋 ####

左右双旋的条件为：cur的平衡因子为1并且parent的平衡因子为-2

此时可以复用前面的左单旋和右单旋，但是要特别注意curleft（或是curright），parent，cur的平衡因子的更新。

![626aa0ccc1634f37977e473ccd83e5c1.png][]

void RotateLR(Node* parent)
    	{
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
    		RotateL(parent->_left);
    		RotateR(parent);
    		//调整平衡因子
    		if (curright->_bf == 0)
    		{
    			parent->_bf = 0;
    			cur->_bf = 0;
    			curright->_bf = 0;
    		}
    		else if (curright->_bf == 1)
    		{
    			parent->_bf = 0;
    			cur->_bf = -1;
    			curright->_bf = 0;
    		}
    		else if (curright->_bf == -1)
    		{
    			parent->_bf = 1;
    			cur->_bf = 0;
    			curright->_bf = 0;
    		}
    		else
    			assert(false);
    	}

#### 右左双旋 ####

右左双旋的条件为：cur的平衡因子为-1并且parent的平衡因子为2

![73f2a0bcfcb3488c8f10ad6c6e005352.png][]

void RotateRL(Node* parent)
    	{
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    		RotateR(parent->_right);
    		RotateL(parent);
    		//调整平衡因子
    		if (curleft->_bf == 0)
    		{
    			parent->_bf = 0;
    			cur->_bf = 0;
    			curleft->_bf = 0;
    		}
    		else if (curleft->_bf == 1)
    		{
    			parent->_bf = -1;
    			cur->_bf = 0;
    			curleft->_bf = 0;
    		}
    		else if (curleft->_bf == -1)
    		{
    			parent->_bf = 0;
    			cur->_bf = 1;
    			curleft->_bf = 0;
    		}
    		else
    			assert(false);
    	}

--------------------

## 三.AVL树的验证 ##

*  首先验证是否是二叉搜索树，即中序遍历一趟是否是有序序列
 *  检查平衡因子是否正确

int Height(Node* root)
    {
    	if (root == nullptr)
    		return 0;
    	int leftHeight = Height(root->_left);
    	int rightHeight = Height(root->_right);
    
    	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
    
    bool isBlance()
    {
    	return isBlance(_root);
    }
    
    bool isBlance(Node* root)
    {
    	if (root == nullptr)  //空树也是AVL树
    		return true;
    	int leftHeight = Height(root->_left);
    	int rightHeight = Height(root->_right);
    
    	if (abs(rightHeight - leftHeight) > 1)   //检查平衡因子是否正确
    		return false;
    	return isBlance(root->_left) && isBlance(root->_right);
    }

--------------------

## 四.AVL树的性能 ##

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

--------------------

## 五.源码 ##

### AVLTree.h ###

template <class K,class V>
    struct AVLTreeNode
    {
    	pair<K,V> _kv;
    	AVLTreeNode* _left;
    	AVLTreeNode* _right;
    	AVLTreeNode* _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)
    	{
    		if (_root == nullptr)
    		{
    			_root = new Node(kv);
    			return true;
    		}
    
    		Node* cur = _root;
    		Node* parent = nullptr;
    		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->_left = cur;
    		else
    			parent->_right = cur;
    
    		cur->_parent = parent;
    		//调平衡因子
    		while (parent)
    		{
    			if (cur == parent->_left)   //左子树增高，平衡因子--
    				parent->_bf--;
    			else if (cur == parent->_right)  //右子树增高，平衡因子++
    				parent->_bf++;
    
    			if (parent->_bf == 0)   //平衡因子==0时，结束
    				break;
    			else if (parent->_bf == 1 || parent->_bf == -1)
    			{
    				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)  //右左双旋
    				{
    					RotateRL(parent);
    				}
    				else if (parent->_bf == -2 && cur->_bf == 1)  //左右双旋
    				{
    					RotateLR(parent);
    				}
    				else
    					assert(false);
    			
    			}
    			else
    				assert(false);
    		}
    
    		return true;
    
    	}
    
    	void RotateL(Node*parent)  //左旋
    	{
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    
    		parent->_right = curleft;  //核心操作1
    		if (curleft)  //当curleft不为nullptr时
    		{
    			curleft->_parent = parent;
    		}
    		cur->_left = parent;  //核心操作2
    
    		Node* ppnode = parent->_parent;
    		parent->_parent = cur;
    
    		if (ppnode == nullptr)  //当ppnode为nullptr时，即parent是根节点，旋转的是整个子树
    		{
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		else
    		{
    			//当ppnode不为nullptr时，即parent不是根节点，旋转的是局部子树，此时要链接ppnode和子树
    			if (ppnode->_left == parent)
    			{
    				ppnode->_left = cur;
    			}
    			else
    			{
    				ppnode->_right = cur;
    			}
    
    			cur->_parent = ppnode;
    		}
    
    		parent->_bf = cur->_bf = 0;  //调整平衡因子
    
    	}
    
    	void RotateR(Node* parent)
    	{
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
    
    		parent->_left = curright;
    		if (curright)
    		{
    			curright->_parent = parent;
    		}
    		cur->_right = parent;
    		Node* ppnode = parent->_parent;
    		parent->_parent = cur;
    		if (ppnode == nullptr)
    		{
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		else
    		{
    			if (ppnode->_left == parent)
    			{
    				ppnode->_left = cur;
    			}
    			else
    				ppnode->_right = cur;
    			cur->_parent = ppnode;
    		}
    
    		parent->_bf = cur->_bf = 0;
    	}
    
    	void RotateRL(Node* parent)
    	{
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    		RotateR(parent->_right);
    		RotateL(parent);
    		//调整平衡因子
    		if (curleft->_bf == 0)
    		{
    			parent->_bf = 0;
    			cur->_bf = 0;
    			curleft->_bf = 0;
    		}
    		else if (curleft->_bf == 1)
    		{
    			parent->_bf = -1;
    			cur->_bf = 0;
    			curleft->_bf = 0;
    		}
    		else if (curleft->_bf == -1)
    		{
    			parent->_bf = 0;
    			cur->_bf = 1;
    			curleft->_bf = 0;
    		}
    		else
    			assert(false);
    	}
    
    	void RotateLR(Node* parent)
    	{
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
    		RotateL(parent->_left);
    		RotateR(parent);
    		//调整平衡因子
    		if (curright->_bf == 0)
    		{
    			parent->_bf = 0;
    			cur->_bf = 0;
    			curright->_bf = 0;
    		}
    		else if (curright->_bf == 1)
    		{
    			parent->_bf = 0;
    			cur->_bf = -1;
    			curright->_bf = 0;
    		}
    		else if (curright->_bf == -1)
    		{
    			parent->_bf = 1;
    			cur->_bf = 0;
    			curright->_bf = 0;
    		}
    		else
    			assert(false);
    	}
    private:
    	Node* _root=nullptr;
    };

--------------------

> **??本篇文章到此就结束了， 若有错误或是建议的话，欢迎小伙伴们指出；?️?**
> 
> **??希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；??**
> 
> **??谢谢你的阅读。??**

[7ed9e4f53e654ee9ba931165bbb53c50.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/376df800206745e493cbe90f0c4ce5fb.png
[46c7c5a120f344d68724b0e1792c6597.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/8edfbad9e5c242d4b31c7f058a4b16b5.png
[bd94b82e73e14eb092bfe208bbf8381a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/4663eda857cc41e283a731abae4162c2.png
[efafc3e9aad040ffb443598f7505aed1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/cdfb51de28764c4dba88a50cf5d95f98.png
[626aa0ccc1634f37977e473ccd83e5c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/ea4834f558514d7fa4c9ab4ca9198728.png
[73f2a0bcfcb3488c8f10ad6c6e005352.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/77939ebe2a2444a484074bb71588e6d8.png