数据结构&算法 AVL树

  • AVL树

    如果二叉搜索树的输入以排序(升序或降序)方式怎么办?然后看起来像这样-
    tree
    可以看出,BST的最坏情况性能最接近线性搜索算法,即Ο(n)。在实时数据中,我们无法预测数据模式及其频率。因此,需要平衡现有的BST。AVL树以其发明人Adelson,Velski&Landis的名字命名,是高度平衡的二叉搜索树。AVL树检查左和右子树的高度,并确保差异不超过1。该差异称为“平衡因子”。在这里我们看到第一棵树是平衡的,接下来的两棵树是不平衡的-
    tree
    在第二棵树中,C的左子树的高度为2,而右边子树的高度为0,所以差为2。在第三棵树中,A的右子树的高度为2,而左子树的高度为2,所以它为0。 ,并且相差再次为2。AVL树允许差异(平衡因子)仅为1。
    BalanceFactor = height(left-sutree) − height(right-sutree)
    如果左右子树的高度差大于1,则使用某些旋转技术来平衡树。
  • AVL旋转

    为了平衡自身,AVL树可以执行以下四种旋转-
    • 左旋
    • 右旋
    • 左右旋转
    • 右左旋转
    前两个旋转是单旋转,接下来的两个旋转是双旋转。要拥有一棵不平衡的树,我们至少需要一棵高度为2的树。通过这棵简单的树,让我们一一理解它们。
    左旋
    如果树变得不平衡,则在将节点插入到右子树的右子树中时,我们将执行一次左旋转-
    tree
    在我们的示例中,当节点插入到A的右子树的右子树中时,节点A变得不平衡。我们通过将A设为B的左子树来执行左旋转。
    右旋
    如果在左子树的左子树中插入节点,则AVL树可能变得不平衡。然后,树需要右旋转。
    tree
    如图所示,通过执行右旋转,不平衡节点成为其左子节点的右子节点。
    左右旋转
    两次旋转是已经解释过的旋转形式的稍微复杂的版本。为了更好地理解它们,我们应注意旋转时执行的每个动作。让我们首先检查如何执行左右旋转。左右旋转是左旋转与右旋转的组合。
    状态 描述
    tree 一个节点已插入到左子树的右子树中。这使C成为不平衡节点。这些方案使AVL树执行左右旋转。
    tree 左旋 - 我们首先在C的左子树上执行左旋转。这使A成为B的左子树。
    tree 左旋 - 节点C仍不平衡,但是现在是由于left-subtree的left-subtree。
    tree 右旋 - 现在,我们将树右旋转,使B成为该子树的新根节点。C现在成为其自己的左子树的右子树。
    tree 平衡树 - 现在树已平衡。
    右左旋转
    第二种双旋转是右旋转。它是向右旋转然后是向左旋转的组合。
    状态 描述
    tree 一个节点已插入到左子树的右子树中。这使C成为不平衡节点。这些方案使AVL树执行左右旋转。
    tree 左旋 - 我们首先在C的左子树上执行左旋转。这使A成为B的左子树。
    tree 左旋 - 节点C仍不平衡,但是现在是由于left-subtree的left-subtree。
    tree 右旋 - 现在,我们将树右旋转,使B成为该子树的新根节点。C现在成为其自己的左子树的右子树。
    tree 平衡树 - 现在树已平衡。