Java 数据结构 - AVL 树

如果二叉搜索树的输入以排序（升序或降序）的方式出现会怎样？它将如下所示：

可以观察到，BST 的最坏情况性能最接近线性搜索算法，即 O(n)。在实时数据中，我们无法预测数据模式及其频率。因此，需要对现有的 BST 进行平衡。

以其发明者 **Adelson、Velski 和 Landis** 的名字命名，**AVL 树**是高度平衡的二叉搜索树。AVL 树检查左右子树的高度，并确保差异不超过 1。此差异称为**平衡因子**。

在这里我们看到第一棵树是平衡的，而接下来的两棵树是不平衡的：

在第二棵树中，C 的左子树高度为 2，右子树高度为 0，因此差值为 2。在第三棵树中，A 的右子树高度为 2，而左子树缺失，因此为 0，差值再次为 2。AVL 树只允许差值（平衡因子）为 1。

BalanceFactor = height(left-sutree) − height(right-sutree)

如果左右子树高度的差异大于 1，则使用一些旋转技术来平衡树。

AVL 旋转 Java

为了平衡自身，AVL 树可以执行以下四种旋转：

• 左旋转
• 右旋转
• 左-右旋转
• 右-左旋转

前两种旋转是单旋转，后两种旋转是双旋转。要使树不平衡，我们至少需要高度为 2 的树。通过这棵简单的树，让我们逐一了解它们。

左旋转

如果在 A 节点的右子树的右子树中插入节点时树变得不平衡，则我们执行单左旋转：

在我们的示例中，由于在 A 的右子树的右子树中插入了一个节点，因此节点 **A** 已变得不平衡。我们通过使 **A** 成为 B 的左子树来执行左旋转。

右旋转

如果在左子树的左子树中插入节点，则 AVL 树可能变得不平衡。然后树需要右旋转。

如图所示，通过执行右旋转，不平衡节点成为其左子节点的右子节点。

左-右旋转

双旋转是已经解释过的旋转版本的稍微复杂一些的版本。为了更好地理解它们，我们应该注意旋转过程中执行的每个动作。让我们首先检查如何执行左-右旋转。左-右旋转是左旋转后紧接着右旋转的组合。

状态	动作
	已将节点 **A** 插入到左子树的右子树中。这使得 **C** 成为不平衡节点。这些情况导致 AVL 树执行左-右旋转。
	我们首先对 **C** 的左子树执行左旋转。这使得 **A** 成为 **B** 的左子树。
	节点 **C** 仍然不平衡，但是现在，这是由于左子树的左子树造成的。
	我们现在将对树进行右旋转，使 **B** 成为此子树的新根节点。**C** 现在成为其自身左子树的右子树。
	树现在已平衡。

右-左旋转

第二种双旋转是右-左旋转。它是右旋转后紧接着左旋转的组合。

状态	动作
	已将节点插入到右子树的左子树中。这使得 **A** 成为一个平衡因子为 2 的不平衡节点。
	首先，我们在 C 节点执行右旋转，使 C 成为其自身左子树 **B** 的右子树。现在，**B** 成为 **A** 的右子树。
	由于其右子树的右子树，节点 **A** 仍然不平衡，需要左旋转。
	通过使 **B** 成为子树的新根节点来执行左旋转。**A** 成为其右子树 **B** 的左子树。
	树现在已平衡。