我正在处理一个AVL树，这样每个节点都拥有它下面最深的子树。下面是一个树的例子，其中表示为value：高度。
0: 2
\
1: 1
\
2: 0为了检查余额，我使用了下面的函数，给定一个AVL树节点或undefined。下面的代码片段是用TypeScript编写的。使用的公式是left - right深度，未定义的子节点返回-1。
private balanceFactor(currentNode: AVLTreeNode<E> | undefined): number {
if (currentNode === undefined) {
return -1;
}
let leftHeight = currentNode.hasLeft() ? currentNode.getLeft().getHeight() : -1;
let rightHeight = currentNode.getRight() ? currentNode.getRight().getHeight() : -1;
return leftHeight - rightHeight
}为了实现旋转的逻辑代码，我找到了之前的堆栈帖子：https://stackoverflow.com/a/19281663/10448256
这篇文章处理了以下双重旋转的逻辑：
balance(N) = Depth(Nleft) - Depth(Nright)
if (balance(P) > 1) {
if (balance(L) < 0) {
rotate_left(L);
}
rotate_right(P);
}
else if (balance(P) < -1) {
if (balance(R) > 0) {
rotate_right(R);
}
rotate_left(P);
}考虑以下双旋转场景：
2: 2
/
1: 1
\
0: 0当在节点2上调用平衡因子时，它创建BF为2（2 - 0），并且由于右未定义，因此右的平衡因子为-1。这将导致双重旋转，正确创建以下树：
1: 1
/ \
0: 0 2: 0当双旋转工作时，它不允许单旋转。如果再次尝试第一个示例：
2: 2
\
1: 1
\
0: 0它在值2处创建了一个平衡因子2，其中左节点是-1，因为它是未定义的，错误地导致了双旋转检测。
我应该使用什么逻辑来确定双旋转和单旋转之间的区别？
1条答案
按热度按时间k2arahey1#
在相关问题中找到的代码中实现的逻辑是正确的。
当双旋转工作时，它不允许单旋转。
引用的代码中的内部
if条件确定应该发生双旋转还是单旋转。如果再次尝试第一个示例：
它在值2处创建了一个平衡因子2，其中左节点是-1，因为它是未定义的，错误地导致了双旋转检测。
这是由于
balanceFactor函数中的错误。当一个节点不存在时，你有一个“空”树。这样的树是平衡的。在这种情况下，没有很好的理由返回-1，就好像那个空树失去了平衡。返回0：**备注：**在确定平衡系数的过程中，调用
getHeight效率不高。这可以在不需要知道节点的高度的情况下递增地完成。例如，参见this implementation，它使用查找表（矩阵）查找参与旋转的两个节点中的平衡因子，从而为这些节点提供新的平衡因子。