数据结构和算法AVL树


如果二叉搜索树的输入以排序(升序或降序)方式出现怎么办?它会看起来像这样 -

BST不平衡

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

以他们的发明者 AdelsonVelskiLandis 命名, AVL树 是高度平衡二元搜索树。AVL树检查左侧和右侧子树的高度,并确保差异不大于1.这种差异称为 平衡因子

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

不平衡的AVL树

在第二个树中, C 的左子树具有高度2,右子树具有高度0,因此差异为2.在第三个树中, A 的右子树具有高度2而左侧缺失,因此它为0 ,差异又是2。AVL树允许差异(平衡因子)仅为1。

_ **BalanceFactor**_ = height(left-sutree)  height(right-sutree)

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

AVL轮换

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

  • 左转
  • 正确的旋转
  • 左右旋转
  • 左右旋转

前两个旋转是单旋转,接下来的两个旋转是双旋转。要拥有一棵不平衡的树,我们至少需要一棵高度为2的树。通过这棵简单的树,让我们逐一理解它们。

左转

如果树变得不平衡,当一个节点插入到右子树的右子树中时,我们执行一个左旋转 -

左转

在我们的示例中,节点 A 变得不平衡,因为节点插入到A右子树的右子树中。我们通过使 A 为B的左子树来执行左旋转。

右转

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

右转

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

左右旋转

双旋转是已经解释的旋转版本的略微复杂版本。为了更好地理解它们,我们应该注意旋转时执行的每个动作。我们先来看看如何进行左右旋转。左右旋转是左旋转然后右旋转的组合。

行动
右转 已将节点插入左子树的右子树中。这使得 **C** 成为不平衡节点。这些场景导致AVL树执行左右旋转。
左转 我们首先在 **C** 的左子树上执行左旋转。这使得 **A** 成为 **B** 的左子树。
左转 节点 **C** 仍然是不平衡的,但是现在,这是因为左子树的左子树。
右转 我们现在将右旋转树,使 **B** 成为此子树的新根节点。 **C** 现在成为其左子树的右子树。
平衡的Avl树 树现在平衡了。

左右旋转

第二种类型的双旋转是右 - 左旋转。它是右旋转然后左旋转的组合。

行动
右子树的左子树 已将节点插入右子树的左子树中。这使得 **A** 是一个平衡因子为2的不平衡节点。
子树右旋转 首先,我们沿着 **C** 节点执行正确的旋转,使 **C** 成为其自己的左子树 **B** 的右子树。现在, **B** 成为 **A** 的正确子树。
右不平衡树 由于右子树的右子树并且需要左旋转,节点 **A** 仍然是不平衡的。
左转 通过使 **B** 成为子树的新根节点来执行左旋转。 **A** 成为其右子树 **B** 的左子树。
平衡的AVL树 树现在平衡了。