告别死记硬背！图解AVL树的四种旋转，代码实现也不难

前言

在《一文彻底掌握二叉查找树，非史上最全总结（多图，附代码）》我们讲了二叉查找树，在文章的最后我们也提到了，二叉查找树查找的效率受到树的深度的影响，最坏情况是O(N)。而二叉查找树的深度是根据数据插入的顺序不同而表现出不同的。那么有没有可能让树的深度尽可能低，从而提高我们查询的效率呢？答案就是今天要讲的平衡二叉树（AVL树）。

定义

AVL树是二叉查找树的一个特例，所以上一篇文章说到的二叉查找树的定义是AVL树定义的前提。在这个前提之下，AVL树再提出了写更加严格的定义。那就是，树的任意节点的子树的高度差都小于等于1。

树的操作

由于AVL树比普通的二叉查找树有个更加苛刻的要求，要求子树的高度差小于等于1。那么在树的插入、删除等操作时将会比普通的二叉查找树更加麻烦。

插入

AVL树插入的第一步其实跟二叉查找树一样，但是插入数据后，可能会导致树失去平衡，那么这时就需要对子树进行旋转了。通过选择来使得树继续保持平衡。

树失去平衡会有四种情况：

1. 节点的左儿子的左子树插入节点，导致左子树比右子树高（LL），如下图树插入节点1之后，6的左子树高度比右子树高2。

2. 节点的右儿子的右子树插入节点，导致右子树比左子树高（RR）

3. 节点的左儿子的右子树插入节点，导致左子树比右子树高（LR）

4. 节点的右儿子的左子树插入节点，导致左子树比右子树高（RL）

AVL树失去平衡之后，可以通过旋转使其恢复平衡。四种失去平衡的情况下对应的旋转方法分别如下：

LL的旋转，步骤如下：

1. 将根节点的左孩子作为新根节点。

2. 将新根节点的右孩子作为原根节点的左孩子。

3. 将原根节点作为新根节点的右孩子。

伪代码：

// 要旋转的节点为node，其父节点是parent Node temp = node.left; node.left = temp.right; temp.right = node; parent.left = temp;

LL 旋转示意图如下：