来降低二叉搜索树的高度，使得二叉搜索树趋近于一个完美二叉树（如下图），从而提高二叉搜索树的性能，今天我们就介绍AVL树。

1. AVL树

1.1. AVL树的概念

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

一颗AVL树有下面的性质：

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

通过这样的平衡规则，使得二叉搜索树高度平衡，那么此时如果它有n个节点，其高度可保持在O(log N)，搜索时间复杂度为O(logN)。

2. AVL树节点的定义

我们这里实现K-V模型的AVL树，K模型的比较简单，大家可以自己实现：

代码语言：javascript

AI代码解释

template<class K, class V>
struct AVLTreeNode
{
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
 
	// 右子树-左子树  的高度差
	int _bf; // balance factor 
 
	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
 
	// AVL树并没有规定必须要设计平衡因子
	// 只是一个实现的选择，方便控制平衡
};

从节点的定义我们可以看出，有普通的二叉搜树不同的是，AVL树中节点的设置添加了节点的parent节点，此处也是为了方便后续功能的实现（接着往下看就明白了）。除此之外，节点也定义了一个控制平衡因子_bf，用来表示当前节点右子树与左子树的高度差。

3. AVL树的插入和旋转

AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

AVL树在插入的过程中，如果插入新节点后导致AVL树中某些节点的平衡因子的绝对值大于等于1时，要进行旋转操作，根据节点插入位置的不同，AVL树的旋转分为四种。接下来我们逐一分析可能出现的情况与解决该问题的旋转方法。

3.1. 左单旋

什么时候需要进行左单旋？当新节点插入在高度较高的右子树的右侧时，我们先看一个比较简单的情况，如下图我们要插入90，此时根节点的平衡因子会变成2，不满足AVL树的规则，所以我们应该进行旋转。

下面这种情况就是，新结点插在较高右子树的右侧，因此需要进行左单旋。

左单旋步骤如下：

• 让插入节点的父节点，也就是这里的60的左子树变成节点30的右子树，30这颗子树成为60的左子树。
• 调整改变节点的平衡因子。

然后我们来看更复杂的情况，在下图中，无论在b还是c树下插入新节点，都是在30的右树下插入新节点，因此这里将有4中可能性（分别是b的左右孩子，c的左右孩子处），这里以c的孩子为例。但是情况均为左单旋情况。

左单旋步骤如下：

• 将60的左树变为30的右树
• 再让30成为60的左树
• 最后更改旋转因子

这里我们还需要考虑一些特殊情况：

1. 60可能存在右子树也可能不存在。
2. 30可能是根节点，也可能是子树，如果是根节点，那我需要更新根节点，如果是是子树，要考虑是左子树还是右子树。

代码实现左单旋：

代码语言：javascript

AI代码解释

void RotateL(Node* parent)
	{
		//左旋
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
 
		Node* ppNode = parent->_parent;
 
		subR->_left = parent;
		parent->_parent = subR;
 
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
 
			subR->_parent = ppNode;
		}
 
		//更新平衡因子
		parent->_bf = 0;
		subR->_bf = 0;
	}

这个地方可以比较形象地解释一下代码，我们抽离出原型：

代码语言：javascript

AI代码解释

旋转前：     
     parent
    /     \
   A      subR
          /   \
       subRL   C

旋转后：
      subR
     /    \
  parent   C
  /   \
 A   subRL

特殊的情况，parent不是根节点：

代码语言：javascript

AI代码解释

旋转前：
      ppNode
      /    \
  parent    D     ← parent是ppNode的左孩子
   /   \
  A    subR
       /   \
    subRL   C

旋转后：
      ppNode  
      /    \
    subR    D     ← subR接替parent的位置
    /   \
 parent  C
  /   \
 A   subRL

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

旋转前：
      ppNode
      /    \
     D    parent   ← parent是ppNode的右孩子
          /   \
        subR   A
        /   \
       B   subRL

旋转后：
      ppNode
      /    \
     D    subR    ← subR接替parent的位置
          /   \
        parent  A
        /   \
       B   subRL

3.2. 右单旋

右单旋的情况与左单旋的情况正好相反，当节点插入到更高左子树的左侧时，需要右单旋。

我们先举一个最简单的例子，在下图中，我们需要插入节点10，这导致60（根节点）的平衡因子不满足AVL树规则，那我们要想重新平衡，就需要将60的左子树较少一层即可，右子树增加一层，即将左子树提上来即可。

右单旋步骤：

• 将30的右子树变成60的左子树
• 再让60变成30的左子树
• 最后更新节点的平衡因子

我们再来讨论一下较为复杂的情况：

同样我们需要考虑一些特殊的情况：

1. 30可能不存在右子树
2. 60可能是根节点，也可能不是，如果不是，就可能是右子树，也可能是左子树