二叉树进阶--二叉搜索树的进一步优化--AVL树 Self-balancing binary search tree

前言：

在上一次的文章中，我们详细介绍了二叉树的进阶树型，即BS树(二叉搜索树),但在文章的结尾，二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，我们迫切需要一个可以解决这个问题同时又不会破坏BS树本身性质的解决方案，这便是我们今天的AVL树。

AVL树的性质：

前言问题的解决方法：

对于前言中的问题，AVL树的解决方案为：
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度
这样就避免了出现单支树的情况，同时保证了BS树的结构不变。

AVL树的性质：

故我们现在就可以总结出AVL树的一般规律了：
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
1.它的左右子树都是AVL树，同时符合BS树的基本规律
2.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 $O(log_2 n)$ ，搜索时间复杂度O( $log_2 n$ )。
如图：
在这里插入图片描述
对于这样一棵单支树，我们就可以变成：

这样就提高了我们的搜索效率！
因此，我们也可以把AVL树简记为：一棵进行了高度平衡的二叉搜索树

!!!AVL树的实现(重点):

对于AVL树的结构和性质我们已经足够了解了，现在就让我们去实现一下AVL树吧：

1.单个节点结构体：

对于AVL树的每一个节点来说，首先我们必备的就是数据，左指针，右指针。其次，由于我们在平衡树的过程中涉及到一个频繁的改变节点指向的问题，因此我们还需要一个指向上一个父亲节点的指针parent，同时，我们还需要对每个节点存储一个平衡因子，以方便对树进行平衡。
因此，我们可以这样构建结构体：

template<class K,class V>
struct AVLTreeNode//构建三叉链，多加一个指向上一个节点的指针_parent
{
	AVLTreeNode(const pair<K, V>& kv)//构造函数
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;//更新平衡因子,父亲指针，指向节点的父亲
	pair<K, V> _kv;//kv键值对
	int _bf;//平衡因子，balance factor
};

由于是为了后续的map和set做准备，因此我们这里采取使用键值对pair的方式来当作本次我们的数据的数据类型_kv
注意，别忘了构造函数，这里不能用默认的，因为bf我们是都要从0开始初始化的。

2.AVL树类主体：

对于AVL树而言，我们的主类形式大体如下：

template<class K, class V>
class AVLTree
{
	typedef struct AVLTreeNode<K, V> Node;
public:
  //在这里实现对应的函数功能
  //
  //
  //............
private:
	Node* _root = nullptr;
}

和二叉树的基本结构一样，我们的成员同样也只需要一个root根节点即可，方便遍历和向下移动等操作。

3.AVL树的插入！！！：

AVL树的插入，就是我们AVL树的精华所在，我们也是在这里进行平衡的，在这里，我大致将插入分为两个部分
1.常规的BS树插入过程
2.平衡树的过程

1.树的插入过程：

AVL树由于其本质和BS树差不多，因此前面的插入过程也大体相似，其步骤逻辑就是：
首先找到对应的位置，然后创建节点在对应的位置插入，这两部分。需要注意的地方是：我们要对空树进行判断，如果是空树就直接root=对应的新节点即可了，其他的同BS树的插入步骤一样。
代码如下：

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;
		}
	}//指针移动完毕,找到我们要插入节点的对应空位，直到nullptr为止，然后开始插入节点
		cur = new Node(kv);
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;//让父亲指针指向插入节点的父亲节点
		}
		else if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
    
    //下面就是第二部分平衡树的过程
    //..............
}

2.树的平衡过程：

当我们插入完节点后，倘若不平衡，那它就是一棵普通的二叉搜索树无疑，因此只有通过接下来的平衡过程，它才会变成一棵我们看到的AVL树。
在这里，我大致将其分为两个部分：
1.调控平衡因子
2.通过平衡因子对树进行调整
我们大体的代码结构如下：
首先我们要说明平衡因子数值的计算方式：
以节点右树的高度为正，节点左树高度为负，通过右减去左来确定对应的平衡因子的数值。

while(parent)//和向上调整一样，看parent的改变效果，直到达到根节点为止，此时cur为根节点，parent为空了
{
	if (cur == parent->_left)
	{
		parent->_bf--;//对父亲平衡因子进行调整
	}
	else if (cur == parent->_right)
	{
		parent->_bf++;
	}
    //首先是先对我们第一部分创建的parent的平衡因子进行更新，从parent开始持续性地向上检查调整平衡因子，从而做出对应的平衡策略
	if (parent->_bf == 0)
	{
		break;
	}//如果平衡因子为0，说明两边高度差相同，这说明这棵树是平衡的，那就不需要向上调整了，直接结束本次插入即可
	else if(parent->_bf==1||parent->_bf==-1)
	{
		cur = parent;
		parent = parent->_parent;//这里存储的parent，就是为了向上调整因子而准备的
	}//如果为1/-1，说明存在平衡不平衡的可能性，则继续向上调整
	else if(parent->_bf==2||parent->_bf==-2)//2或者-2的情况，需要旋转平衡调整
	{
		//这里是针对不同情况进行旋转调整的过程
	}
	else//这里说明出现大于2的情况了，已经不是AVL树了，不调整直接报错,我们规定平衡因子的绝对值超过2以上就已经不是AVL树了，直接报错即可
	{
		assert(false);
	}
}

3.针对不同情况对树的调整方法：

我们在调控AVL树的时候，会遇到下面的四种情况：
1… 新节点插入较高左子树的左侧—（简记为左左)：
如图：
在这里插入图片描述
而我们的目的是将其调整为下面的情况：

故在这里，我们就采取右单旋的方法即可解决，方法思路如下：

对于方框的部分，我们不需要去管，只需要对parent，sub1,sub2进行处理即可，最后别忘了对平衡因子进行更新处理即可。
代码如下：

void RotateR(Node* parent)//右单旋旋转调整
{
	Node* sub1 = parent->_left;
	Node* sub2 = sub1->_right;
	Node* PPparent = parent->_parent;
	parent->_left = sub2;
	if (sub2)
	{
		sub2->_parent = parent;
	}
	sub1->_right = parent;
	parent->_parent = sub1;
	if (_root == parent)//如果为根节点，直接更新root即可，父亲指针指向空
	{
		_root = sub1;
		sub1->_parent = nullptr;
	}
	else//如果不为，则依照正常的逻辑进行父亲节点和对应的root节点进行互相指向即可
	{
		if (PPparent->_right == parent)
		{
			PPparent->_right = sub1;
		}
		else if (PPparent->_left == parent)
		{
			PPparent->_left = sub1;
		}
		sub1->_parent = PPparent;
	}
	parent->_bf = sub1->_bf = 0;
}

在代码这里我们需要注意几个点：
1.sub2是有可能存在为空的情况的，因此我们需要对sub2进行判断，否则很可能会出现空指针访问的情况
2.别忘了平衡因子
3.别忘了对新调整的sub1的parent进行处理，要让其指向的父亲节点和它对应好关系

2.新节点插入较高右子树的右侧—右右：左单旋
在这里插入图片描述
由于其本质和右单旋属于镜面对称的方式，因此我这里直接上代码，其需要注意的点和左单旋一样,我这里直接上代码了:

void RotateL(Node* parent)//左单旋旋转调整
{
	Node* sub1 = parent->_right;
	Node* sub2 = sub1->_left;
	Node* PPparent = parent->_parent;
	parent->_right = sub2;
	if (sub2)//注意这里，可能涉及到sub2为空的情况，比如h==0,此时要对sub2是否为空进行一次判断
	{
		sub2->_parent = parent;
	}
	sub1->_left = parent;
	parent->_parent = sub1;
	if (_root == parent)
	{
		_root = sub1;
		sub1->_parent = nullptr;
	}
	else
	{
		if (PPparent->_right == parent)
		{
			PPparent->_right = sub1;
		}
		else if (PPparent->_left == parent)
		{
			PPparent->_left = sub1;
		}
		sub1->_parent = PPparent;
	}
	parent->_bf = sub1->_bf = 0;
}

我们大致的调控方法如下：
在这里插入图片描述
3.新节点插入较高左子树的右侧—左右：先左单旋再右单旋
这种属于情况比较复杂的情况，大致的情况图示如下：

我们处理方式为：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新。
代码如下：

	void RotateLR(Node* parent)//左右双旋转
	{
		Node* sub1 = parent->_left;
		Node* sub2 = sub1->_right;
		int bf = sub2->_bf;
		RotateL(parent->_left);
		RotateR(parent);
		if (bf == 0)
		{
			parent->_bf = sub1->_bf = sub2->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			sub2->_bf = 0;
			sub1->_bf = -1;
		}
		else if (bf == -1)
		{
			sub2->_bf = 0;
			parent->_bf = 1;
			sub1->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

这种方法需要注意的就是，我们需要先存储sub2，即图中数值为60的节点的平衡因子数，即为代码中的bf，因此我们从图中可以得知，sub2的左右分别给了parent和sub1，因此我们就可以通过知道sub2左右的节点情况，对最后的parent sub1 sub2三个节点的平衡因子进行调整。

4.新节点插入较高右子树的左侧—右左：先右单旋再左单旋
在这里插入图片描述
代码如下：

void RotateRL(Node* parent)//右左双旋转
{
	Node* sub1 = parent->_right;
	Node* sub2 = sub1->_left;
	int bf = sub2->_bf;
	RotateR(parent->_right);
	RotateL(parent);
	if (bf == 0)
	{//即插入的点就是分解后的sub2，此时对应的平衡树两边层数相同
		parent->_bf = sub1->_bf = sub2->_bf = 0;
	}
	else if (bf == 1)
	{
		//sub2右子树新增
		sub2->_bf = 0;
		parent->_bf = -1;
		sub1->_bf = 0;
	}
	else if (bf == -1)
	{
		//sub2左子树新增
		sub2->_bf = 0;
		parent->_bf = 0;
		sub1->_bf = 1;
	}
	else
	{
		assert(false);//即平衡因子出现错误的点，直接报错检查出来
	}
}

需要注意的点和第三种情况类似，在这里我不过多赘述了，直接看代码即可。
以上便是我们旋转的四种情况，根据上面的四种情况，我们对应相应的方法即可，对应的代码为：

//旋转
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);
}
break;//调整一次后，对上面的根节点无影响了，恢复到插入前的高度了，不用再继续更新了，直接退出即可

AVL树的验证：

我们的AVL树构建好之后，接下来针对AVL树，我们需要进行一次关于AVL树的验证：
对于AVL树来说，其高度的平衡因子是我们最为关键的检验数据，因此我们的验证可以通过验证高度的方式来完成。
我们验证的方面主要有两个：
1.验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2. 验证其为平衡树
每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
节点的平衡因子是否计算正确
我们的代码如下：

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 leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);

	return leftHeight > rightHeight ? 1 + leftHeight : 1 + rightHeight;
}


bool _IsBalance(Node* root)//判断是否为AVL树的函数，利用求二叉树的高度来判断
{
	if (root == nullptr)
	{
		return true;
	}
	int leftheight = _Height(root->_left);
	int rightheight = _Height(root->_right);
	if (rightheight - leftheight != root->_bf)//顺便检查一下节点的平衡因子
	{
		cout << root->_kv.first << "平衡因子异常" << endl;
		return false;
	}
	return abs(leftheight - rightheight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
}

AVL树的性能分析：

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