数据结构？AVL树！！！-EW帮帮网

一、引言

众所周知，常见的数据结构有两类，分别称为线性数据结构，比如顺序表、链表；还有非线性数据结构，比如堆、搜索树等等，它们的区别主要是前者一般只用于存储数据，而后者一般还具有一些特殊的功能，今天我们将一起认识并实现一种高级的非线性数据结构---AVL树，如果对于这种数据结构的概念、功能、实现还有一些问题的话，那么就请看下去吧！

二、AVL树的相关概念

1、什么是二叉搜索树？

二叉搜索树是一种非线性数据结构，首先二叉搜索树是一颗二叉树，对于搜索树的每一棵子树都满足左子树的所有权值<根节点的权值<右子树的所有权值，顾名思义，搜索树在查找时非常的高效，当需要查找某一个值是否在搜索树中时，只需要从根节点开始将树中的节点权值一一与需要查找的值(下面称为目标值)进行比对，如果目标值较小接下来就与左子树节点进行比对，反之则与右子树节点进行比对，直到找到目标值或者把树走空，就可以判断目标值是否在树中，很明显，这个查找过程最多只需要进行树高次

2、二叉搜索树的缺点

经过上面对于二叉搜索树的说明，我们主观上认为这是一个完美的数据结构，但事实上在上面我们只提到了查找最多执行树高次，但是树高并不能保证是logN级别的，如果插入数据时的顺序是有序的或者是基本有序的话，那么这颗树最终会退化成链表，此时它查找时的时间复杂度就几乎没有得到优化

3、什么是AVL树？

AVL树又叫平衡搜索树，顾名思义，如果一棵树要构成AVL树，当且仅当这棵树既是一棵二叉搜索树，又满足这棵树每一颗子树的平衡因子的绝对值都小于2，平衡因子是指这棵树右子树的高度与左子树高度的差值

4、为什么会有AVL树？

我们在上文已经讨论过了二叉搜索树的缺点，那么优化的方案是什么呢？很明显就是让这棵树趋于一棵完全二叉树甚至一棵满二叉树，这时候AVL树就应运而生了，它平衡因子绝对值小于2的限制就决定了这颗树一定不会退化成一个类似于链表的结构，相反的，它一定会是一棵趋于平衡的树

5、简述K模型和K-V模型

(1).K模型

K模型是Key模型的简称，指树中的每一个节点只有一个关键值，在该模型下我们一般只关心某一个值是否在树中，实际的应用场景比如说：小区的私有停车场，在车辆进出时只需要查找这个车牌是否在树中，在就放行，反之则不放行

(2).K-V模型

K-V模型是Key-Value模型的简化，指数的每一个节点存储了两个值，前者为关键值，后者为该关键值所对应的权值，在该模型下我们一般不仅关注某一个值是否在一棵树中，还关心这个值所对应的某一些属性，实际的应用场景比如说：公共的停车场，在车辆进入时记录车牌号以及进入时间，在出库时用车牌检索到它的入库时间，配合出库时间以及计费系统计算如何收费，在付费后进行放行，反之则不放行

三、AVL树是如何保证既能搜索又平衡的？

说明：在这一板块以及下面实现的板块我们都只讨论插入相关的部分，也就是说我们的目的都是只讨论和实现一棵较为简陋的AVL树，主要还是为了了解这样一个数据结构的底层工作原理，事实上在实际应用中C++库中提供的相关结构就已经够用了

1、保证可以高效搜索

在插入时我们需要保证该树是一个二叉搜索树，对于一个新值插入时(下面称为目标值)，我们需要从根节点开始将每个节点的关键值与目标值进行比对，如果目标值较小接下来与左子树的节点关键值比对，反之如果目标值较大，接下来则与右子树的节点关键值比对，如果遇到与目标值相同的关键值，则返回插入失败(这种做法可以给AVL树赋予去重的功能，如果不想去重也可以实现，在后面实现红黑树时将会提到)

2、保证该树是平衡的

在一个节点成功插入时我们将会维护插入点祖先的平衡因子，随后根据平衡因子的值来判断接下来将要停止、继续更新还是进行旋转

3、旋转是什么？

当更新平衡因子的过程中，如果有节点的平衡因子的绝对值大于1时，这时候我们需要调整以该节点为根的子树的左右子树的高度，使得它的平衡因子绝对值小于1，这种调整的方式就是旋转，在下面实现的过程中我将详细解释该如何旋转

四、实现AVL树

1、AVL树实现前的准备

(1).模型的选取

事实上，K模型和K-V模型在实现难度的层面上是完全相同的，本次我们选择实现K-V模型

(2).树的节点

作为一棵树，它的节点我们需要进行封装，需要注意的是，这棵树除了要存储左右节点的指针，还需要存储父节点的指针，这是由于我们在插入节点后需要依次更新新插入节点祖先的平衡因子

经过以上的分析，我们为AVL树做的准备工作就结束了，代码如下：

namespace bea
{
	template <class K, class V>
	struct AVLTreeNode
	{
		typedef AVLTreeNode<K, V> Node;
		AVLTreeNode(pair<K, V> val)
			:_val(val)
		{}
		pair<K, V> _val;
        int _bf = 0;
		Node* _parent = nullptr;
		Node* _left = nullptr;
		Node* _right = nullptr;
	};

	template <class K,class V>
	class AVLTree
	{
		typedef AVLTreeNode<K, V> Node;
	private:
		Node* _root = nullptr;
	};
}

2、插入函数的实现

(1).插入逻辑

插入逻辑在上面已经提到过了，也就是从根节点开始将目标值与各个关键值进行比对，如果目标值较小，那么接下来将目标值与左子树节点的关键值进行比对，反之如果目标值较大，那么接下来将目标值与右子树的关键值进行比对，直到遍历到空节点，执行插入操作，如果右节点的关键值与目标值相同，那么返回插入失败，代码如下：

bool insert(pair<K, V> val)
{
	if (_root == nullptr)
	{
		_root = new Node(val);
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	//查找
	while (cur)
	{
		K x = val.first , k = cur->_val.first;
		if (x < k)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (x > k)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (x == k)
		{
			return false;
		}
	}
	//插入
	cur = new Node(val);
	if (x > parent->_val.first)
	{
		parent->_right = cur;
	}
	else if (x < parent->_val.first)
	{
		parent->_left = cur;
	}
	else
	{
		assert(0);
	}
	cur->_parent = parent;

}

(2).修改平衡因子逻辑

由于插入一个节点影响的是该节点的父节点的平衡因子，又因为平衡因子是右子树高度与左子树高度之差，所以当新插入的节点在父节点右子树时，父节点的平衡因子加一，反之则减一，代码如下：

//向上修改平衡因子并根据父节点平衡因子的值决定下一步该如何处理
while (parent)
{
	if (parent->_left == cur)
	{
		parent->_bf--;
	}
	else if (parent->_right == cur)
	{
		parent->_bf++;
	}

}

(3).根据父节点修改后的平衡因子的值来确定下一步该如何处理的逻辑

分析：

①.修改后父节点的平衡因子变为了1/-1

如果修改后变为了1/-1，这就意味着左子树或右子树比另一边的子树高1个单位，这是AVL树的概念所允许的，但是由于1/-1一定是由0变来的，这也就意味着以父节点为根的子树高度加一，所以我们对本层不做额外处理，继续向上一层更新

②.修改后父节点的平衡因子变为了0

如果修改后变为了0，那么之前一定为1/-1，这就意味着以父节点为根节点的子树原本是左子树或右子树比另一边的子树高一个单位，修改之后该子树高度没有改变，而是比之前变得平衡了，所以这时候我们应该跳出循环，停止更新

③.修改后父节点的平衡因子变为了2/-2

如果修改后变为了2/-2，此时就是AVL树的规则不允许的情况，这时候我们需要执行旋转操作，借助旋转操作降低较高一边子树高度的同时还要保证该树仍然是平衡搜索树，我们首先实现主干部分，旋转的原理在下一部分解释，简单来理解，如何旋转只和新插入的节点在修改后平衡因子变为2/-2的祖先的哪一棵子树有关系，分为四种情况：右子树的右子树、左子树的左子树、右子树的左子树、左子树的右子树，这四种情况事实上实在讲：祖先的右子树高、祖先的左子树高、祖先右子树的左子树高、祖先左子树的右子树高，所以对应这四种情况我们的处理是：左单旋、右单旋、右左双旋、左右双旋，具体它们如何旋转、会产生怎样的效果在后面实现这几个接口时一一解释，现在暂时先记住这几种情况对应了哪一种旋转，事实上上面的记忆方式是一种不错的方法，同时由于旋转会降低子树的高度，所以插入后导致的子树生高效应就被抵消掉了，所以也可以跳出循环，停止更新

④.修改后父节点的平衡因子可能会是3/-3甚至更高吗？

事实上一棵正常的AVl树不会出现这种情况，这是由于我们实现的AVL树的平衡因子在修改时每次只会加一或者减一，假设变成了3/-3，那么在这之前就已经是2/-2了，那时候我们就已经借助旋转操作降低了子树的高度，所以不会出现修改后变成3/-3的情况，如果出现了这种情况，就意味着旋转代码出现了问题

代码如下：

while (parent)
{
	if (parent->_left == cur)
	{
		parent->_bf--;
	}
	else if (parent->_right == cur)
	{
		parent->_bf++;
	}
	//检查平衡因子的变化并做出对应的处理
	if (parent->_bf == 0)
	{
		break;
	}
	else if (parent->_bf == 1 || parent->_bf == -1)
	{
		cur = parent;
		parent = parent->_parent;
	}
	else if (parent->_bf == 2 || parent->_bf == -2)
	{
		int pbf = parent->_bf, cbf = cur->_bf;
		if (pbf == 2 && cbf == 1)
		{
			reverseL(parent);
		}
		else if (pbf == -2 && cbf == -1)
		{
			reverseR(parent);
		}
		else if (pbf == 2 && cbf == -1)
		{
			reverseRL(parent);
		}
		else if (pbf == -2 && cbf == 1)
		{
			reverseLR(parent);
		}
		break;
	}
}

(4).理解并实现四个旋转接口

说明：很明显左单旋和右单旋是类似的，同理右左双旋和左右双旋是类似的，所以接下来只重点说明其中两种的原理，剩下的直接给出代码

①.左单旋/右单旋(以左单旋为例)

旋转的分析、说明、代码如下：

//左单旋
void reverseL(Node* parent)
{
	Node* cur = parent->_right;
	Node* curLeft = cur->_left;
	Node* ppNode = parent->_parent;
	cur->_left = parent;
	parent->_parent = cur;
	if (curLeft)
	{
		parent->_right = curLeft;
		curLeft->_parent = parent;
	}
	ppNode->_right = cur;
	cur->_parent = ppNode;
	parent->_bf = cur->_bf = 0;
}
//右单旋
void reverseR(Node* parent)
{
	Node* cur = parent->_left;
	Node* curRight = cur->_right;
	Node* ppNode = parent->_parent;
	cur->_right = parent;
	parent->_parent = cur;
	if (curRight)
	{
		parent->_left = curRight;
		curRight->_parent = parent;
	}
	ppNode->_left = cur;
	cur->_parent = ppNode;
	parent->_bf = cur->_bf = 0;
}

②.右左双旋/左右双旋(以右左双旋为例)