Javascript 中的 AVL 旋转

web developmentfront end technologyjavascript

为了保持自身平衡，AVL 树可以执行以下四种旋转 −

前两次旋转是单旋转，后两次旋转是双旋转。要拥有一棵不平衡的树，我们至少需要一棵高度为 2 的树。通过这棵简单的树，让我们逐一了解它们。

左旋转

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

左旋转

在我们的示例中，节点 A 已变得不平衡，因为一个节点插入到 A 的右子树的右子树中。我们通过将 A 设为 B 的左子树来执行左旋转。此旋转也称为 LL 旋转。让我们看看如何实现它 −

function rotationLL(node) {
let tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
}

如果在左子树的左子树中插入节点，AVL 树可能会变得不平衡。然后树需要右旋转。

右旋转

如图所示，不平衡节点通过执行右旋转成为其左子节点的右子节点。这也称为 RR 旋转。让我们看看它在代码中的样子 −

function rotationRR(node) {
let tmp = node.right;
node.right = tmp.left;
tmp.left = node;
return tmp;
}

双重旋转是已经解释过的旋转版本的一个稍微复杂的版本。为了更好地理解它们，我们应该注意旋转时执行的每个动作。让我们首先检查如何执行左右旋转。左右旋转是左旋转和右旋转的组合。

状态	动作
	已将节点插入左子树的右子树。这使 C 成为不平衡节点。这些情况导致 AVL 树执行左右旋转。
	我们首先对 C 的左子树进行左旋转。这使得 A 成为 B 的左子树。
	节点 C 仍然不平衡，但是现在，这是因为左子树的左子树。
	我们现在将右旋转树，使 B 成为该子树的新根节点。 C 现在成为其自身左子树的右子树。
	树现在已平衡。

这也称为 LR 旋转，因为我们首先执行左旋转，然后执行右旋转。这可以使用前 2 种方法实现，如下所示 −

function rotationLR(node) {
node.left = rotationRR(node.left);
return rotationLL(node);
}

第二种双旋转是右-左旋转。它是右旋转和左旋转的组合。

状态	动作
	已将节点插入右子树的左子树。这使得 A 成为一个不平衡节点，平衡因子为 2。
	首先，我们沿 C 节点执行右旋转，使 C 成为其自身左子树 B 的右子树。现在，B 成为 A 的右子树。
	节点 A 仍然不平衡，因为它的右子树的右子树，需要左旋转。
	通过使 B 成为子树的新根节点来执行左旋转。A 成为其右子树 B 的左子树。
	树现在平衡了。

这也称为 RL 旋转，因为我们首先执行右旋转，然后执行左旋转。可以使用前两种方法实现，如下所示 −

function rotationRL(node) {
node.right = rotationLL(node.right);
return rotationRR(node);
}