二叉搜索树和AVL树的区别

2025年4月19日 | 阅读 7 分钟

在了解二叉搜索树和AVL树的区别之前，我们应该分别了解二叉搜索树和AVL树。

什么是二叉搜索树？

二叉搜索树是一种遵循二叉树条件的树数据结构。我们知道，树可以有'n'个子节点，而二叉树最多只能包含两个子节点。因此，二叉搜索树也遵循二叉树的约束。二叉搜索树中的每个节点最多应该有两个子节点；换句话说，我们可以说二叉搜索树是二叉树的一个变体。

二叉搜索树也遵循二叉搜索的特性。在二叉搜索中，数组中的所有元素必须按排序顺序排列。我们计算二叉搜索中的中间元素，其中中间元素的左侧部分包含小于中间值的值，中间元素的右侧部分包含大于中间值的值。

在二叉搜索树中，中间元素成为根节点，右侧部分成为右子树，左侧部分成为左子树。因此，我们可以说二叉搜索树是二叉树和二叉搜索的组合。

注意：二叉搜索树可以定义为这样一种二叉树：其左子树的所有元素都小于根节点，其右子树的所有元素都大于根节点。

二叉搜索树的时间复杂度

如果二叉搜索树几乎是平衡的，那么所有操作的时间复杂度将是 O(logn)，因为搜索被分为左子树或右子树。

如果二叉搜索树是左偏或右偏的，那么所有操作的时间复杂度将是 O(n)，因为我们需要遍历 n 个元素。

什么是AVL树？

AVL树是一种自平衡二叉搜索树，其中左右子树的高度差不能大于一。这个差值被称为平衡因子。在AVL树中，平衡因子的值可以是-1、0或1。

二叉搜索树如何实现自平衡？

我们知道AVL树是一种自平衡二叉搜索树。如果二叉搜索树不平衡，可以通过一些重新排列来实现自平衡。这些重新排列可以通过一些旋转操作来完成。

让我们通过一个例子来理解自平衡。

假设我们想在AVL树中插入10, 20, 30。

以下是在AVL树中插入10, 20, 30的方法

如果插入顺序是30, 20, 10。

步骤1： 首先，我们创建一个二叉搜索树，如下图所示

步骤2： 在上图中，我们可以观察到树是不平衡的，因为节点30的平衡因子是2。为了使其成为AVL树，我们需要执行一些旋转操作。如果我们对节点20执行右旋转，那么节点30将向下移动，而节点20将向上移动，如下图所示

正如我们所观察到的，最终的树遵循二叉搜索树的属性并且是一个平衡树；因此，它是一个AVL树。

在这种情况下，树是左不平衡树，所以我们对节点执行右旋转。

如果插入顺序是10, 20, 30。

步骤1： 首先我们创建一个二叉搜索树，如下图所示

步骤2： 在上图中，我们可以观察到树是不平衡的，因为节点10的平衡因子是-2。为了使其成为AVL树，我们需要执行一些旋转操作。这是一个右不平衡树，所以我们将执行左旋转。如果我们对节点20执行左旋转，那么节点20将向上移动，节点10将向下移动，如下图所示

正如我们所观察到的，最终的树遵循二叉搜索树的属性和平衡树的属性；因此，它是一个AVL树。

如果插入顺序是30, 10, 20

步骤1： 首先我们创建二叉搜索树，如下图所示

步骤2： 在上图中，我们可以观察到树是不平衡的，因为根节点的平衡因子是2。为了使其成为AVL树，我们需要执行一些旋转操作。上述情况是左右不平衡的，因为一个节点是其父节点的左子节点，另一个节点是其父节点的右子节点。首先，我们将执行左旋转，旋转发生在节点10和20之间。左旋转后，20将向上移动，10将向下移动，如下图所示

树仍然不平衡，所以我们对树执行右旋转。一旦对树执行右旋转，树将变成如下图所示

正如我们在上图中观察到的，该树遵循二叉搜索树的属性和平衡树的属性；因此，它是一个AVL树。

如果插入顺序是10, 30, 20

步骤1： 首先，我们创建二叉搜索树，如下图所示

步骤2： 在上图中，我们可以观察到树是不平衡的，因为根节点的平衡因子是2。为了使其成为AVL树，我们需要执行一些旋转操作。上述情况是右左不平衡的，因为一个节点是其父节点的右子节点，另一个节点是其父节点的左子节点。首先，我们将执行右旋转，旋转发生在节点30和20之间。右旋转后，20将向上移动，30将向下移动，如下图所示

上图中的树仍然不平衡，所以我们需要对节点执行左旋转。一旦执行左旋转，节点20将向上移动，节点10将向下移动，如下图所示

正如我们在上图中观察到的，该树遵循二叉搜索树的属性和平衡树的属性；因此，它是一个AVL树。