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现在成为其自己的左子树的右子树。 |
|
平衡树 - 现在树已平衡。 |