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

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

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

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

实现AVL树

构造节点和空数

平衡因子起名为_bf，因为它是balance factor的缩写

template
struct AVLTreeNode
{
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	pair _kv;
	int _bf;//平衡因子 balance factor

	AVLTreeNode(const pair& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
};

template
class AVLTree
{
	typedef AVLTreeNode Node;
public:
	AVLTree()
		:_root(nullptr)
	{}
private:
    Node* _root;
};

插入
插入的思路就是先插入再平衡。那么具体思路：

插入的过程和搜索二叉树一样，因为要在空节点插入数值，并且要对新节点进行三叉链的链接关心更新，所以要记录当前节点位置cur和它的父节点的位置parent。

如果要插入的值比当前节点值大，就更新：先讲父节点更新到cur当前节点，防止cur更新后，父节点找不到更新位置。cur更新到cur的右节点；如果插入的值kv比当前节点小，更新parent和cur，cur更新到cur的左节点。如果值一样那么直接返回false，AVL树的本质是二叉搜索树，不能有重复的值。当cur节点走到空，说明有一个可以插入新节点的位置，我们建立新节点，并链接好三叉链表的关系。新节点的父节点要更新一下。

在插入好新节点后，插入节点的父节点的所有路径的根节点都会受到影响，而兄弟节点是没有影响的，所以我们要对各个根节点的平衡因子进行更新，平衡因子是为了检查这个AVL树是否为一个平衡的二叉搜索树，也就是左右子树的高度差小于等于1。新插入的节点的平衡因子在构造的时候，就已经为0。所以我们要更新父节点的平衡因子。

平衡因子的更新有以下五种情况（这里的平衡因子=右子树高度-左子树高度）：

当插入在父节点的右边，父节点平衡因子加1，parent->_bf++;
当插入在父节点的左边，父节点平衡因子减1，parent->_bf--;
这时候父节点更新完会有三种情况：
如果父节点更新后为0，说明更新前parent->_bf是1/-1,现在变成0，说明填上矮的那边。填上后它左右子树高度相同，让这颗子树平衡了。所在跟节点路径节点的平衡因子就不用更新，直接跳出循环
如果父节点更新后为-1/1，说明更新节点前parent->_bf是0，有一边子树变高了，parent所在子树高度变了。说明新插入节点影响了左右子树的高度差，继续循环更新父节点的父亲的平衡因子
当父节点的父亲改变，就有可能从1变成2，那么当节点的平衡因子是2/-2的时候，就没必要继续向上面更新，这时候需要平衡这颗子树。

像左边这个图中，出现2的平衡因子，此时不需要继续向上更新，需要旋转这颗子树，而旋转方法就是左单旋，下面我们讲解各个旋转方法。

旋转处理的四种方法：

【左单旋】：

当平衡因子出现2的时候，说明已经出现了问题，我们就需要旋转将子树的高度降下来。降下来之后这棵树也平衡了。左旋的情况在于parent的平衡因子是2，右子树的跟的bf是1，因为右边高，所以要左旋，将右边子树高度降低，它的不平衡因素都出现在右子树，所以平衡因子都是正数。

左旋的方法：将bf为2的的节点定义为parent,将右子树根节点定义为subR,当我们左旋的时候，parent节点要左subR的左子树，因为subR是parent右边，比parent要大，这就证明了，parent节点一定比subR要小，作为一个搜索树，那么它的顺序一定是左子树比根节点小，右子树比根节点大。当parent成为subR的左子树时，subR的右子树就会多于出来，因为subR的左子树也是parent的右子树的一部分，要比parent大，所以subR的左子树成为了parent的右子树。这样parent的高度降了两级，从2变成0，而subR高度因为左右平衡了变成0。

//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		//更新subRL节点
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		//更新subR根节点
		Node* parentParent = parent->_parent;
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
				parentParent->_left = subR;
			else
				parentParent->_right = subR;

			subR->_parent = parentParent;
		}
		//更新parent
		subR->_left = parent;
		parent->_parent = subR;
		//更新平衡因子
		subR->_bf = parent->_bf = 0;
	}

【右单旋】：

右单旋和左单旋同理。右单旋是因为左子树太高，parent节点平衡因子是-2，parent左子树跟节点subL的平衡因子是-1，有这两个条件了，才能构成右单旋条件。开始旋转：记录parent的左子树根节点subL,和subL的右子树subLR（因为parent节点要变成subL的右子树）。将subLR变成parent的左节点，并链接好三叉链关系。记录parent的父节点parentParent，因为parent节点变成subL的右子树后就不再是这棵树的根节点了，这棵树的根节点变成了subL,subL变成根节点要改变原来的三叉链关系。最后更改parent节点的链接关系，变成subL的右子树。

下面是一个抽象图，这里的矩形子树抽象图代表了不同高度的子树，h有可能是0，就是上面例子这张图，也可能是1或2，我们统称为高度为h。

【那么为什么parentParent的平衡因子不用改变呢？】（也就是平衡因子为2/-2的的节点的父节点）当我们遇到bf==2/-2的节点就会停止更新平衡因子，转而去旋转这颗子树。在插入新节点之前这颗parent子树的高度是h+2,在subL的左子树插上新节点，它的总高度变成了h+3,我们将它旋转之后，subL是30变成根节点，可以看作将60这个节点去除，少了一个节点，那么总体高度降1，使总体高度又变回原来的h+2。所以这颗子树高度增加节点之后也没有变，parentParent节点也就没必要改变平衡因子。

//右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		//更新新的子树根节点
		Node* parentParent = parent->_parent;
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
				parentParent->_left = subL;
			else
				parentParent->_right = subL;

			subL->_parent = parentParent;
		}
		//更新跟的右子树，链接parent
		subL->_right = parent;
		parent->_parent = subL;

		//更新bf
		subL->_bf = 0;
		parent->_bf = 0;
	}

【双旋】

【左右双旋：parent->_bf==-2;cur->_bf==1】

左右双旋就是先左旋再右旋，这是出现在bf为-2和1的情况下。双旋并不是单纯的一边高，如果使用单旋来旋转这个情况的AVL树，只会造成拆东墙补西墙的效果。

双旋就是先旋30这个节点，通过将30节点左旋，60的左边变成30的右边，60变成新的根，将节点旋转到一边。这时这种情况就变成了左边高，再进行右旋：60的右边变成90的左边，60变成新的根。最后达到AVL树平衡的效果。

总结来说：1、30这个节点为轴点，进行左单旋；2、90这个节点为轴点，进行右单旋。

【右左双旋：parent->_bf==2;cur->_bf==-1】

1、90这个节点为轴点，进行右单旋；2、30这个节点为轴点，进行左单旋。

以上两种双旋方法我们可以复用单旋的代码

	void RotateLR(Node* parent)
	{
		RotateL(parent->_left);
		RotateR(parent);
	}
	void RotateRL(Node* parent)
	{
		RotateR(parent->_right);
		RotateL(parent);
	}

插入的代码：

    bool Insert(const pair& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else//相等返回false
				return false;
		}

		//插入新节点
		cur = new Node(kv);
		if (kv.first > parent->_kv.first)
		{
			parent->_right=cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left=cur;
			cur->_parent = parent;
		}

		while (parent)
		{
			if (cur == parent->_left)
				parent->_bf--;
			else //if (cur == parent->_right)
				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)
			{
				//开始旋转
				if (parent->_bf == -2 && cur->_bf == -1)//左边高，右单旋
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)//右边高，左单旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)//parent左边高，cur右边高，先左旋cur，再右旋parent
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}
				break;
			}
			else//出错了，直接断死
				assert(false);
		}

		return true;
	}

遍历AVL树

如果单纯的调用类函数，遍历AVL树需要传入root根节点，但是root是私有成员变量，类外面访问不到。所以我们可以写一个子函数_InOrder，在类内部调用这个子函数；类外面调用InOrder函数，就能遍历AVL树了。

	void InOrder()
	{
		_InOrder(_root);
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root -> _right);
	}

判断AVL树平衡性

我们写的AVL树中有一个bf平衡因子的成员变量，它是用来控制AVL树是否平衡。但是并不能成为评判AVL树平衡的根本依据，如果bf平衡因子本身就错了怎么办呢？所以要判断AVL树平衡，可以通过计算左树和右树的高度，这个需要递归来实现。

在AVL树里，根节点判断平衡结束了，还要判断左右子树的根节点的平衡性。所以在_IsBlance函数中，除了判断当前节点的左右子树高度差不超过2，还要判断左右子树的平衡性，也就是左右子树的左右子树的高度差不超过2。

算二叉树的高度，我们可以自己写一个函数Height,用递归方式来写。这样一层层返回子树的高度，如果左树高，在左树的基础上增加自己的高度；相反如果右树高，就在右树的基础上增加自己的高度，也就是+1。

这里还有一点，因为平衡因子有时候会出错，所以我们判断左右子树高度差是否等于平衡因子，来判断平衡因子的正确性。

	bool IsBlance(Node* root)
	{
		_IsBlance(_root);
	}
	int Height(Node* root)
	{
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

	bool _IsBlance(Node* root)
	{
		if (root == NULL)
			return;

		//对当前树进行检查
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		if (rightHeight - leftHeight != root->_bf)//如果高度差和平衡因子不相同，那么直接返回false
		{
			cout << root->_kv.first << "现在是:" << root->_kv.second<_kv.first << "应该是:" << rightHeight - leftHeight << endl;
			return false;
		}

		return abs(leftHeight - rightHeight) < 2
			&& _IsBlance(root->_left)
			&& _IsBlance(root->_right);
	}

通过以上的代码，我们对这些代码进行一个测试：

在我们测试的过程中发现，6的平衡因子bf有错误。导致6的平衡因子错误可能是因为自身插入错误，也有可能是因为6的孩子节点有错误导致的6平衡因子更新错误。而InOrder函数中序遍历整个AVL树只能判断它是不是一个搜索二叉树，不能判断树的平衡性。

【查找错误】

对于这种错误的解决方法，我们可以采用一个笨方法：直接调试并自己画图，来一一查找到底在哪个节点插入出现的错误。第二种方法：我们可以打一个日志，通过在插入的时候就判断整棵树是否平衡。通过下图可以发现，a这个数组中的依次插入，最终在插入14后导致的AVL树的平衡因子有误。

【解决错误】：

出现这个错误的原因就在于双旋后的平衡因子并不是单旋那样，在单旋中右旋的parent和subL改变之后的平衡因子都会变成0，左旋之后parent和subR的平衡因子都会变成0。

而在双旋中，以右左双旋为例，60新增节点后，无论是在b上增加节点，还是在c上增加节点，旋转之后，b会成为30节点的右子树，c会成为90节点的左子树，30和90分别成为60的左右子树。但是如果在b上增加节点，那么它的高度从h-1变成h，那么旋转后30的平衡因子是0，而90的平衡因子是-1。在单旋中parent和subL、subR都要变成0的，双旋中，有一个平衡因子不是0。同理，如果在c增加新节点，双旋之后30的平衡因子是-1，90的平衡因子是0。还有一种特殊情况就是，60节点就是新增，那么最后的平衡因子都是0。

同样左右双旋也分为这三种情况。

所以对于以上三种情况我们怎么区分呢？在更新平衡因子之后，通过60的平衡因子的情况来识别这三种情况。如果b增加节点，那么60平衡因子在旋转之前由0变-1；在c上新增，60的平衡因子在旋转前由0变1；60自己就是新增，在旋转前就是0。

所以在旋转之前将60节点的平衡因子保存下来，旋转之后，通过判断60平衡因子大小，对旋转节点的平衡因子做出相应的改变。

在第三种情况，旋转因子和单旋的结果一样，可以不写，但是为了代码的完整性，再写一边是最好的。最后如果双旋还是出错，那么我们断言给断死，直接assert(false)。

【右左双旋】

    void RotateRL(Node* parent)//右左双旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else
			assert(false);
	}

【左右双旋】：

左右双旋和右左双旋同理（这里不想画图了呜呜）

	void RotateLR(Node* parent)//左右双旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		
		RotateL(parent->_left);
		RotateR(parent);

		if (bf == -1)//左边增加节点
		{
			subL->_bf = 0;
			parent->_bf = 1;
			subLR->_bf = 0;
		}
		else if (bf == 1)//右边增加节点
		{
			subL->_bf = -1;
			parent->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 0)
		{
			subL->_bf = parent->_bf = subLR->_bf = 0;
		}
		else
			assert(false);
	}

C++中AVL树的插入实现

实现AVL树

旋转处理的四种方法：

C/C++/C#相关栏目本月热门文章