【AVL树】—— 我与C++的不解之缘（二十三）

什么是AVL树？

• AVL树发明者是G. M. Adelson-Velsky和E. M. Landis两个前苏联科学家，他们在1962年论文《An algorithm for the organization of information》中发表了AVL树。
• AVL树是最先发明的自平衡二叉搜索树，说白了就是能够自己控制平衡结构的一个二叉搜索树；AVL可以是一个空树，或者其左右树都是AVL树，且左右子树的高度差的绝对值不超过1。
• AVL树，左右子树的高度差不超过一，而不是0？（如果一棵树的节点个数是2、4等的情况下，高度差最好情况就是1，到不到0。
• 本篇在实现AVL树时，引入了一个新的概念(平衡因子)；每个节点都存在平衡因子，平衡因子等于右子树的高度减去左子树的高度，这样平衡因子的取值就是(0、1、-1)；（平衡因子也不是必须的，这里引入平衡因子这一概念，方便观察和控制整个AVL树的平衡。

​ 简单来说，AVL树就是一个特殊的搜索二叉树，特殊就特殊在它可以控制平衡，保持左右子树的高度差不超过1。

那又是如何实现的呢？

AVL树的实现

1. AVL树的结构

先来看一下AVL树的结构，首先就是AVL树的节点

template<class K,class V>
struct TreeNode {
	int _bf;
	pair<K, V> _kv;
	TreeNode<K, V>* _left;
	TreeNode<K, V>* _right;
	TreeNode<K, V>* _parent;

	TreeNode(const pair<K, V> kv)
		:_kv(kv)
		, _bf(0)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

这里并没有直接存储数据K，和V，而是像map那样将其封装成一个pair<K,V>类型。

再来看一下AVL树都要实现哪些方法

template<class K,class V>
class AVLTree
{
	typedef TreeNode<K, V> Node;
public:
	//插入
	bool insert(const pair<K, V> kv) {}
	//查找
	bool find(const K& kev) {}

	//中序遍历
	void order() {}
private:
	//右单旋
	void RevoleR(Node* parent) {}
	//左单旋
	void RevoleL(Node* parent) {}
	//右左双选
	void RevoleRL(Node* parent) {}
	//左右双选
	void RevoleLR(Node* parent) {}
	//中序遍历
	void order(Node* root) {}
	Node* _root;
};

这里实现了几个私有的成员方法，因为这些方法不希望在类外被直接访问。（其中order()是为了实现中序遍历，因为在类外无法访问到该树的根节点。）

2. AVL树的插入

插入过程

对于插入数据的整个过程，其实就是在搜索二叉树的基础上，增加了更新平衡因子和在更新平衡因子的过程中需要旋转的情况就行旋转。

• 按搜索二叉树的规则进行插入数据
• 新增节点以后，就可能会影响到部分祖先节点的平衡因子，所以从新增节点 -> 根节点这整个路径上节点的平衡因子（在更新的过程中，可能会遇到继续更新，更新结束以及需要旋转的情况。）
• 更新平衡因子过程中没有出现问题，插入就结束了。
• 在平衡的过程中，出现了不平衡的情况，就要堆不平衡子树进行旋转，选择后调平衡的同时，也降低了子树的高度，就不会影响上一层的平衡因子，插入也就结束了。

更新平衡因子

首先，平衡因子=右子树高度-左子树高度

• 插入节点会增加高度，所以，新增节点如果是在parent节点的右子树，则parent节点的平衡因子++；如果是在parent节点的左子树，那么parent节点的平衡因子–；
• parent所在子树的高度是否变化就决定了是否要继续往上更新平衡因子。

更新平衡因子可能遇到的情况：

• 更新之后parent节点平衡因子等于0：更新过程中parent的平衡因子变化-1->0或者1->0，这说明了插入节点之前parent子树一边高一边低，新增节点插入到了低的那一边，插入节点后以parent为根节点的子树的高度不变，就不会影响其父节点的平衡因子（就不会影响到上面节点的平衡）所以更新就结束了。
• 更新之后parent节点平衡因子等于1或-1：更新过程中parent的平衡因子变化0->-1或者0->1，这就说明了，插入节点之前，parent的左右子树高度相同了，插入节点之后parent子树的高度发生了变化，所以就会影响其父节点的平衡因子，从而影响上面节点的平衡；所以需要继续更新平衡因子。
• 更新之后parent节点平衡因子等于2或者-2：更新过程中parent的平衡因子变化1->2或者-1->-2，这说明，在插入节点之前，以parent为根节点的子树就已经一边高一边低了；然后新增节点还插入到了高的那一边，这样以parent为根节点的子树就已经不满足AVL树的结构了，此时就需要对该树就行旋转（旋转：一是将以parent为根节点的子树调整平衡，二是降低以parent为根节点的子树的高度，回复到插入以前的高度）；旋转完成后，就不需要继续更新平衡因子了。

更新之后parent节点平衡因子为0

更新之后parent节点平衡因子为1或者-1

更新之后parent节点平衡因子为2或者-2

更新平衡因子的过程实现

bool insert(const pair<K, V> kv) 
{
	Node* newnode = Node(kv);
	if (_root == nullptr)
	{
		_root = newnode;
		return true;
	}
	Node* parent = nullptr;
	Node* pcur = _root;
	while (pcur)
	{
		if (kv.first > pcur->_kv.first)
		{
			parent = pcur;
			pcur = pcur->_right;
		}
		else if (kv.first < pcur->_kv.first)
		{
			parent = pcur;
			pcur = pcur->_left;
		}
		else
		{
			return false;
		}
	}
	pcur = newnode;
	newnode->_parent = parent;
	if (kv.first > parent->_kv.first)
	{
		parent->_right = pcur;
	}
	else if (kv.first < parent->_kv.first)
	{
		parent->_left = pcur;
	}
	else
	{
		return false;
	}
	//更新平衡因子
	while (parent)
	{
		if (pcur == parent->_left)
		{
			--parent->_bf;
		}
		else
		{
			++parent->_bf;
		}
		if (parent->_bf == 0)
		{
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			pcur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//旋转
		}
	}	
	return true;
}

3.旋转

新插入节点以及更新平衡因子如上述，那么在更新平衡因子过程中，遇到平衡因子等于2（也就是以parent为根节点的子树不平衡）需要进行旋转，那如何旋转的呢？

旋转的规则：

• 保持搜索树的原则。
• 将要旋转的树从不满足到满足平衡，其次降低树的高度。

旋转一共分为四种（左单旋、右单旋、左右双旋、右左双旋），其每一种旋转都对应一种情况；

左单旋

先来看一下这种情况：

如上图中以5为根节点的子树，其中a、b、c都是高度为h的子树（h可以等于0）；现在要在a子树中插入一个节点，在更新平衡因子的过程中，5所在节点的平衡因子1 -> 2，此时该子树就不平衡了，需要进行旋转；

通过观察上图，我们可以发现，5节点的右子树太高了，所以我们需要向左旋转来平衡高度；

如何旋转呢？

旋转步骤

• b子树变成5节点的右子树；
• 以5节点为根节点的子树变成10节点的左子树；
• 10节点就变成了这个子树新的根节点。

其中5<b子树<10，所以将b子树变成5的右子树，以5为根节点的子树变成10的左子树，仍然满足搜索二叉树的规则；

然后10节点变成了这部分子树新的根节点。（并不一定是整个子树新的根节点）。

代码实现：

//左单旋
void RevoleL(Node* parent) 
{
	//旋转节点的右孩子节点
	Node* subr = parent->_right;
	//旋转节点的右孩子节点的左孩子节点
	Node* subrl = parent->_right->_left;

	//subrl变成parent的右子树
	parent->_right = subrl;
	//subrl可能为空
	if (subrl)
		subrl->_parent = parent;
	//parent->变成subr的左子树
	subr->_left = parent;

	//记录parent的父节点
	Node* pnode = parent->_parent;
	parent->_parent = subr;
	//如果parent是整个avl树的根节点
	if (pnode == nullptr)
	{
		_root = subr;
		subr->_parent = nullptr;
	}
	else
	{
		//parent父节点不为空
		subr->_parent = pnode;
		if (pnode->_left == parent)
		{
			pnode->_left = subr;
		}
		else
		{
			pnode->_right = subr;
		}
	}
	//调整完之后将parent节点与subr节点的平衡因子修改成0
	parent->_bf = 0;
	subr->_bf = 0;
}

右单旋

了解了左单旋，右单旋就十分简单了：

和左单旋的情况相似，有单旋就是10节点的左子树高，需要进行右单旋；

旋转步骤

• b子树变成10节点的左子树；
• 以10节点为根节点的子树变成5节点的右子树；
• 5节点就变成这部分子树的根节点。

其中5<b子树<10，所以将b子树变成10的左子树，以10为根节点的子树变成5的右子树；仍然保持搜索二叉树的结构。

5节点就变成了这部分子树的根节点。

代码实现

//右单旋
void RevoleR(Node* parent)
{
	//旋转节点的左孩子节点
	Node* subl = parent->_left;
	//旋转节点的左孩子节点的右孩子节点
	Node* sublr = parent->_left->_right;

	//sublr变成parent的左孩子节点
	parent->_left = sublr;
	//sublr可能为nullptr
	if (sublr)
		sublr->_parent = parent;
	
	//parent变成subl的右孩子节点
	subl->_right = parent;

	//记录parent的父节点
	Node* pnode = parent->_parent;
	if (pnode == nullptr)
	{
		_root = subl;
		subl->_parent = nullptr;
	}
	else
	{
		subl->_parent = pnode;
		if (pnode->_left == parent)
		{
			pnode->_left = subl;
		}
		else
		{
			pnode->_right = subl;
		}
	}
	//修改parent 和 subl 的平衡因子
	parent->_bf = 0;
	subl->_bf = 0;
}

左右双旋

左单旋、右单旋都是纯粹的一边高（就是在parent的左/右孩子的左/右孩子所在子树中插入数据）；按上述说，就是在a子树中插入数据，但是如果是在b子树中插入数据呢？

如上图，我们很显然不能单纯的使用右单旋或者左单旋来解决问题了；

旋转步骤

左右双旋其实就是，先对parent的左孩子节点进行一次左单选，再对parent节点进行一次右单旋；

来看分析：

这里h是能够等于0的，我们分开来讨论：
h=0

我们先对subl节点进行一次左单旋，再对parent节点进行一次右单旋；

h!=0

对于h!=0的情况，b子树中就至少有一个节点，那我们要分为两种情况讨论；

我们将一个avl树抽象成下面这种情况：

这样我们可以看出来，可能是在e子树中插入数据，也可能是在f子树中插入数据；那这两种情况就也要分开讨论：

在e子树中插入

此时，我们还是先对subl节点左单旋，变成纯粹的一边高，再对parent节点进行右单旋；

在f子树插入节点

还是先对subl左单旋，再对parent进行右单旋；

通过观察，我们可以发现，这三种情况都是进行了一次左单旋和一次右单旋，不同的是其结果中subl和parent的平衡因子不同。

这样我们在实现时，就直接复用左单旋和右单旋就好了，然后根据其平衡因子的情况来判断最后subl和parent节点的平衡因子即可。

更新平衡因子

• sublr节点平衡因子等于0： sublr、subl和parent平衡因子都为0；
• sublr节点平衡因子等于-1：sublr和subl平衡因子等于0，parent平衡因子等于1；
• sublr节点平衡因子等于1：sublr和parent平衡因子等于0，subl平衡因子等于-1；

代码实现

代码实现过程中有一个细节就是：

在进行左右单旋时，会将平衡因子修改成0，我们就需要先记录一下sublr原本的平衡因子，来保证我们单旋结束后的平衡因子的修改。

	//左右双选
	void RevoleLR(Node* parent) 
	{
		Node* subl = parent->_left;
		Node* sublr = parent->_left->_right;
		int bf = sublr->_bf;
		//对subl进行左单旋
		RevoleL(subl);
		//对parent进行右单旋
		RevoleR(parent);

		//更新平衡因子
		if (bf == 0)
		{
			parent->_bf = 0;
			subl->_bf = 0;
			sublr->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subl->_bf = -1;
			sublr->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subl->_bf = 0;
			sublr->_bf = 0;
		}
	}

右左双旋

右左双旋和左右双旋逻辑非常像，这里就不演示了，直接看代码实现：

	//右左双选
	void RevoleRL(Node* parent) 
	{
		Node* subr = parent->_right;
		Node* subrl = parent->_right->_left;
		int bf = subrl->_bf;
		RevoleR(subr);
		RevoleL(parent);
		if (bf == 0)
		{
			parent->_bf = 0;
			subr->_bf = 0;
			subrl->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			subr->_bf = 0;
			subrl->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subr->_bf = 1;
			subrl->_bf = 0;
		}
	}

在旋转实现完成之后我们就可以完善我们insert了：

//插入
bool insert(const pair<K, V> kv) 
{
	Node* newnode = Node(kv);
	if (_root == nullptr)
	{
		_root = newnode;
		return true;
	}
	Node* parent = nullptr;
	Node* pcur = _root;
	while (pcur)
	{
		if (kv.first > pcur->_kv.first)
		{
			parent = pcur;
			pcur = pcur->_right;
		}
		else if (kv.first < pcur->_kv.first)
		{
			parent = pcur;
			pcur = pcur->_left;
		}
		else
		{
			return false;
		}
	}
	pcur = newnode;
	newnode->_parent = parent;
	if (kv.first > parent->_kv.first)
	{
		parent->_right = pcur;
	}
	else if (kv.first < parent->_kv.first)
	{
		parent->_left = pcur;
	}
	else
	{
		return false;
	}
	//更新平衡因子
	while (parent)
	{
		if (pcur == parent->_left)
		{
			--parent->_bf;
		}
		else
		{
			++parent->_bf;
		}
		if (parent->_bf == 0)
		{
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			pcur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//旋转
			if (parent->_bf == 2 && parent->_left->_bf == 1)
			{
				//左单旋
				RevoleL(parent);
			}
			else if (parent->_bf == 2 && parent->_left->_bf == -1)
			{
				//右左双旋
				RevoleRL(parent);
			}
			else if (parent->_bf == -2 && parent->_right->_bf == -1)
			{
				//右单旋
				RevoleR(parent);
			}
			else if (parent->_bf == -2 && parent->_left->_bf == 1)
			{
				//左右双旋
				RevoleLR(parent);
			}
		}
	}
	
	return true;
}

旋转了解完以后，就可以完善之前的插入功能了：

//插入
bool insert(const pair<K, V> kv) 
{
	Node* newnode =  new Node(kv);
	if (_root == nullptr)
	{
		_root = newnode;
		return true;
	}
	Node* parent = nullptr;
	Node* pcur = _root;
	while (pcur)
	{
		if (kv.first > pcur->_kv.first)
		{
			parent = pcur;
			pcur = pcur->_right;
		}
		else if (kv.first < pcur->_kv.first)
		{
			parent = pcur;
			pcur = pcur->_left;
		}
		else
		{
			return false;
		}
	}
	pcur = newnode;
	newnode->_parent = parent;
	if (kv.first > parent->_kv.first)
	{
		parent->_right = pcur;
	}
	else if (kv.first < parent->_kv.first)
	{
		parent->_left = pcur;
	}
	else
	{
		return false;
	}
	//更新平衡因子
	while (parent)
	{
		if (pcur == parent->_left)
		{
			--parent->_bf;
		}
		else
		{
			++parent->_bf;
		}
		if (parent->_bf == 0)
		{
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			pcur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//旋转
			if (parent->_bf == 2 && parent->_left->_bf == 1)
			{
				//左单旋
				RevoleL(parent);
			}
			else if (parent->_bf == 2 && parent->_left->_bf == -1)
			{
				//右左双旋
				RevoleRL(parent);
			}
			else if (parent->_bf == -2 && parent->_right->_bf == -1)
			{
				//右单旋
				RevoleR(parent);
			}
			else if (parent->_bf == -2 && parent->_left->_bf == 1)
			{
				//左右双旋
				RevoleLR(parent);
			}
		}
	}
	return true;
}

4. AVL树的查找

AVL树的查找先对就简单多了，和搜索二叉树查找一样。

	//查找
	bool find(const K& kv) 
	{
		Node* ptail = _root;
		while (ptail)
		{
			if (kv.first > ptail->_kv->first)
			{
				ptail = ptail->_right;
			}
			else if (kv.first < ptail->_kv->first)
			{
				ptail = ptail->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

对于AVL树的删除，有点过于复杂，感兴趣的可以深入探究一下；后面研究过了再来探讨这个问题。

}
		else if (parent->_bf == -2 && parent->_right->_bf == -1)
		{
			//右单旋
			RevoleR(parent);
		}
		else if (parent->_bf == -2 && parent->_left->_bf == 1)
		{
			//左右双旋
			RevoleLR(parent);
		}
	}
}
return true;

}

## 4. `AVL`树的查找

`AVL`树的查找先对就简单多了，和搜索二叉树查找一样。

```cpp
	//查找
	bool find(const K& kv) 
	{
		Node* ptail = _root;
		while (ptail)
		{
			if (kv.first > ptail->_kv->first)
			{
				ptail = ptail->_right;
			}
			else if (kv.first < ptail->_kv->first)
			{
				ptail = ptail->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

对于AVL树的删除，有点过于复杂，感兴趣的可以深入探究一下；后面研究过了再来探讨这个问题。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws