AVL 树的平衡因子是什么？

AVL 树

1962 年，GM Adelson-Velsky 和 EM Landis 创建了 AVL 树。为了纪念创造者，这棵树被称为 AVL。

AVL 树的定义是高度平衡的二叉搜索树，其中每个节点都有一个平衡因子，该平衡因子是通过从左子树的高度中减去右子树的高度来确定的。

为什么要使用 AVL 树？

大多数 BST 操作，包括搜索、最大值、最小值、插入、删除等，都需要 O(h) 时间，其中 h 是 BST 的高度。对于倾斜的二叉树，这些操作的成本可能会增加到 O(n)。如果我们确保在每次插入和删除后树的高度保持 O(log(n))，我们可以为所有这些操作提供 O(log(n)) 的上限。AVL 树的高度始终为 O(log(n))，其中 n 是树的节点数。

AVL 树

由于 AVL 树也是二叉搜索树，因此所有操作的执行方式与二叉搜索树中的操作相同。搜索和遍历不会导致 AVL 树属性的违反。然而，可能破坏此条件的动作是插入和删除；因此，需要对其进行审查。

• 插入
• 删除

AVL 树的插入

为了确保在每次插入后提供的树保持 AVL，我们必须在典型的 BST 插入过程中添加一些重新平衡。

以下两个简单的操作（键（左） 键（根） 键（右））可以在不违反 BST 属性的情况下用于平衡 BST。

• 左旋
• 右旋

平衡因子

• 如果任何节点的平衡因子为 1，则左子树比右子树高一个级别。
• 平衡因子为零的任何节点都表示左子树和右子树的高度相等。
• 如果节点的平衡因子为负一，则左子树比右子树低一个级别。
• 下图展示了一棵 AVL 树。我们可以看到每个节点的平衡因子都在 -1 到 +1 之间。因此，这是 AVL 树的一个例子。
• 今天我们将讨论 AVL 树及其用途。BST 的最坏情况性能接近线性搜索算法，即 O (n)。我们无法实时预测实时数据中的数据模式和频率。因此，平衡当前 BST 的需求应运而生。
• AVL 树，代表 Adelson、Velski 和 Landis，是高度平衡的二叉搜索树。AVL 树确保左右子树的高度差不超过 1。这被称为平衡因子。
• 为了更好地理解平衡和不平衡树的区别，让我们看一些例子
  
• 由于上例中根节点的左右高度相同，我们可以看到第一棵树是平衡的。而另外两棵则不是这样，中间图中的树在节点左侧是倾斜的。类似地，最后一幅图右侧的树在根节点右侧是倾斜的，导致其不平衡。

AVL 树的应用

• 大多数内存中的集合和字典都使用 AVL 树进行存储。
• 数据库应用程序，其中插入和删除不频繁，但数据查找频繁，也经常使用 AVL 树。
• 除了数据库应用程序，它还被用于其他需要更好搜索的应用程序中。
• AVL 树是一种平衡二叉搜索树，它使用旋转来保持平衡。
• 它也可以用于有情节的游戏中。
• 它主要用于需要记录员工及其换班情况的商业领域。