AVL 树的优点17 Mar 2025 | 6 分钟阅读 什么是 AVL 树？Adelson-Velskii 和 Landis 是发现它的人，所以这个名字来源于他们的名字，即 AVL。它通常被称为高度平衡二叉树。AVL 树在每个节点都具有以下特征之一。 如果一个节点的左子树的最长路径比其右子树的最长路径长，则该节点被称为“左重”。 如果一个节点的右子树的最长路径比其左子树的最长路径长，则该节点被称为“右重”。 如果一个节点的左右子树的最长路径相等，则该节点被认为是平衡的。  AVL 树是一种高度平衡树，其中每个节点的左右子树的高度差为 -1、0 或 1。一个称为平衡因子的值保持了子树的高度差。因此，我们可以将 AVL 定义为平衡二叉搜索树，其中每个节点的平衡因子为 -1、0 或 +1。在这种情况下，以下公式用于确定平衡因子。 平衡因子属性 -
AVL 树的旋转如果任何树节点失衡，则进行必要的旋转来纠正不平衡。有四种不同的旋转类型，它们在各种情况下使用，如下所示： LL 旋转：当新节点被添加为失衡节点左子树的左子节点时。 RR 旋转：当新节点被添加到失衡节点的右子树的右子节点时，这个过程称为 RR 旋转。 LR 旋转：当新节点被添加到失衡节点右子树的左子节点时。 RL 旋转：当新节点被添加到失衡节点左子树的右子节点时。 二叉搜索树和 AVL 树AVL 树是一种二叉搜索树。它具有一些很好的复杂性保证，例如 O (log n) 的搜索、插入和删除。在结构上，它只是一个二叉搜索树，仅使用一些算法（和一个额外的字段）来保证复杂性。 二叉搜索树是一种二叉树。它们都有最多有两个子节点的节点。在二叉搜索树中，一个节点可以有两个子节点，通常称为左子节点和右子节点，其中左子节点存储的值小于（或可能等于）右子节点的值。这意味着左子树中的所有值都小于或等于右子树中的值。 AVL 树的重要性AVL 树是自平衡二叉搜索树 (BST)。普通的 BST 可能会向任一侧倾斜，这将导致搜索键需要更大的努力（阶数将远大于 O (log2n)，有时等于 O(n)，在最坏情况下结果与顺序搜索相同）。这使得 BST 作为一种实际有效的数据结构变得无用。 类似 AVL 树的自平衡二叉树版本是解决方案。树会确定其左右子树之间是否存在深度差异，并通过将一些枢轴节点向左、向右或向两边旋转来纠正，从而将深度差异保持在 1。每次插入都会进行平衡，以保持恒定的插入复杂度。但是，由于每个节点现在都将携带一些深度信息，因此所需的空间会进一步增加。考虑数据的检索速度以及实际实现的效率。通常，复杂性为 O(log2n)。 可以通过二叉搜索树 (BST) 进行搜索，但如果元素已经排序，BST 将变成链状，时间复杂度为 O(n)。为了解决这个问题，引入了 AVL 树。 在平均和最坏情况下，查找、插入和删除需要 O (log n) 的时间，其中 n 是操作前树中的节点数。插入和删除后，树可能需要进行一次或多次树旋转以恢复平衡。 红黑树和 AVL 树支持相同的操作集，并且基本操作时间为 O (log n)，因此它们经常被进行比较。由于它们比红黑树更严格地平衡，因此 AVL 树在查找密集型应用中更快。AVL 树和红黑树一样是高度平衡的。 由于平衡因子，AVL 树永远不会变成链状，它是一棵近似满的二叉树。 树中的插入、删除和搜索等操作在最坏情况和平均情况下的时间复杂度均为 O (log n)。 示例 考虑以下树  图 1：BST  图 2：AVL 树 为了在二叉树中插入一个键为 Q 的节点，算法需要 7 次比较；但如果你在 AVL 树（上图 2 所示）中插入相同的键，算法只需要 3 次比较。 即使是搜索和删除，BST 的时间也比 AVL 长。
当节点按升序或降序排列时，BST 的高度为 O(n)。因此，所有操作都需要 O(n) 的时间，这是最坏情况。 AVL 树通过防止倾斜来自我平衡，使其高度始终为 O(log n)，从而确保所有操作（无论是插入、删除还是搜索）的上限均为 O (log n)。 时间复杂度（最坏情况）
AVL 树的优点
AVL 树应用
下一主题# |
我们请求您订阅我们的新闻通讯以获取最新更新。
我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题
G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India
Python
Java
JavaScript
SQL
C
C++
HTML
CSS
React
Node.js
Spring Boot
C#
PHP
MySQL
MongoDB
AI
ML
DSA
DBMS
OS
Aptitude
Reasoning