AVL旋转
为了平衡自身，AVL树可以执行以下四种旋转-
前两个旋转是单旋转，接下来的两个旋转是双旋转。要拥有一棵不平衡的树，我们至少需要一棵高度为2的树。通过这棵简单的树，让我们一一理解它们。
左旋
如果树变得不平衡，则在将节点插入到右子树的右子树中时，我们将执行一次左旋转-
在我们的示例中，当节点插入到A的右子树的右子树中时，节点A变得不平衡。我们通过将A设为B的左子树来执行左旋转。
右旋
如果在左子树的左子树中插入节点，则AVL树可能变得不平衡。然后，树需要右旋转。
如图所示，通过执行右旋转，不平衡节点成为其左子节点的右子节点。
左右旋转
两次旋转是已经解释过的旋转形式的稍微复杂的版本。为了更好地理解它们，我们应注意旋转时执行的每个动作。让我们首先检查如何执行左右旋转。左右旋转是左旋转与右旋转的组合。
| 状态 |
描述 |
 |
一个节点已插入到左子树的右子树中。这使C成为不平衡节点。这些方案使AVL树执行左右旋转。 |
 |
左旋 - 我们首先在C的左子树上执行左旋转。这使A成为B的左子树。 |
 |
左旋 - 节点C仍不平衡，但是现在是由于left-subtree的left-subtree。 |
 |
右旋 - 现在，我们将树右旋转，使B成为该子树的新根节点。C现在成为其自己的左子树的右子树。 |
 |
平衡树 - 现在树已平衡。 |
右左旋转
第二种双旋转是右旋转。它是向右旋转然后是向左旋转的组合。
| 状态 |
描述 |
 |
一个节点已插入到左子树的右子树中。这使C成为不平衡节点。这些方案使AVL树执行左右旋转。 |
 |
左旋 - 我们首先在C的左子树上执行左旋转。这使A成为B的左子树。 |
 |
左旋 - 节点C仍不平衡，但是现在是由于left-subtree的left-subtree。 |
 |
右旋 - 现在，我们将树右旋转，使B成为该子树的新根节点。C现在成为其自己的左子树的右子树。 |
 |
平衡树 - 现在树已平衡。 |
可以看出，BST的最坏情况性能最接近线性搜索算法，即Ο(n)。在实时数据中，我们无法预测数据模式及其频率。因此，需要平衡现有的BST。AVL树以其发明人Adelson，Velski＆Landis的名字命名，是高度平衡的二叉搜索树。AVL树检查左和右子树的高度，并确保差异不超过1。该差异称为“平衡因子”。在这里我们看到第一棵树是平衡的，接下来的两棵树是不平衡的-
在第二棵树中，C的左子树的高度为2，而右边子树的高度为0，所以差为2。在第三棵树中，A的右子树的高度为2，而左子树的高度为2，所以它为0。 ，并且相差再次为2。AVL树允许差异（平衡因子）仅为1。
在我们的示例中，当节点插入到A的右子树的右子树中时，节点A变得不平衡。我们通过将A设为B的左子树来执行左旋转。右旋如果在左子树的左子树中插入节点，则AVL树可能变得不平衡。然后，树需要右旋转。
如图所示，通过执行右旋转，不平衡节点成为其左子节点的右子节点。左右旋转两次旋转是已经解释过的旋转形式的稍微复杂的版本。为了更好地理解它们，我们应注意旋转时执行的每个动作。让我们首先检查如何执行左右旋转。左右旋转是左旋转与右旋转的组合。