AVL 树的时间复杂度

什么是 AVL 树？

Adelson-Velskii 和 Landis 是发现它的人，所以这个名字来源于他们的名字，即 AVL。它通常被称为高度二叉树。AVL 树的每个节点都具有以下特征之一。

如果一个节点的左子树中最长路径比其右子树中最长路径长，则该节点被称为“左重”。

如果一个节点的右子树中最长路径比其左子树中最长路径长一个，则该节点被称为“右重”。

如果右子树和左子树中最长路径相等，则该节点被称为平衡。

AVL 树是一种高度平衡树，其中每个节点的右子树和左子树的高度差为 **-1、0 或 1**。一个称为平衡因子的因素将子树的高度差分开。因此，我们可以将 AVL 定义为一种平衡二叉搜索树，其中每个节点的平衡因子为 -1、0 或 +1。在这种情况下，计算平衡因子的公式如下：

AVL 树的旋转

如果树的任何节点失去平衡，将执行必要的旋转以纠正不平衡。有四种不同的旋转类型。如下：

1. LL 旋转：当新节点作为不平衡节点的左子树的左子节点添加时。
2. RR 旋转：当新节点被添加到失衡节点的右子树的右子节点时，这个过程称为 RR 旋转。
3. LR 旋转：当新节点被添加到失衡节点右子树的左子节点时。
4. RL 旋转：当新节点被添加到失衡节点左子树的右子节点时。

AVL 树时间复杂度

插入

要将元素插入到 AVL 树中，需要旋转、计算平衡因子以及插入后更新高度。如前所述，旋转是常数时间操作。更新高度和计算平衡因子都需要常数时间。因此，遍历树的高度（其高度为 O(log n)）需要很长时间。

最好的解决方案是当树不需要结构性更改并且新节点可以插入到其位置而无需重新平衡时。在这种情况下，由于我们遍历 AVL 树的高度，时间复杂度将是 O(log n)。

最坏的情况是当添加新节点后树失去平衡并且需要旋转时。在这种情况下，时间复杂度也是 O(log n)。

由于平均情况等于所有可能情况的平均值，因此在这种情况下插入的时间复杂度同样是 O(log n)。

删除

与插入类似，删除涉及遍历树、计算平衡因子以及每当删除特定节点时更新树的高度。

最好的解决方案是当不需要重新平衡并且删除节点不会影响树的平衡时。在这种情况下，时间复杂度将是 O(log n)，因为我们遍历 AVL 树的高度以到达需要删除的节点。由于遍历，在这种情况下，时间复杂度也是 O(log n)。

最坏的情况是当删除特定节点后树失去平衡并且需要旋转时。在这种情况下，由于遍历，时间复杂度也是 O(log n)。

删除的平均时间复杂度也是 O(log n)，因为它是所有可能情况或场景的平均值。

遍历和搜索

在 AVL 树中，遍历是应用于插入和删除的基本操作。在所有三种情况下（最佳情况、最坏情况和平均情况），遍历操作的时间复杂度都是 O(log n)。

在不同情况下搜索 AVL 树中元素的时间复杂度如下：

最好的解决方案是当要查找的元素是根元素时。因此，在第一次遍历时就找到了元素，无需遍历整个树。因此，时间复杂度变为 O(1)。

最坏的情况是当我们必须遍历树的叶节点，因为我们正在寻找的元素存在于那里。

概述