两个不满意解之间BST无限环的左/右旋转？

Question

我不太了解我的算法，所以我可能遗漏了一些非常基本的东西。在我看来，这个树上的标准rotate left/rotate right实现（我在看交互式Python中的this link）将进入一个无限循环，因为平衡因子总是-2或+2。是我遗漏了什么还是这是正确的结论？我在底部粘贴示例代码，显示在粘贴的链接中实现的rotateLeft

def rotateLeft(self,rotRoot):
    newRoot = rotRoot.rightChild
    rotRoot.rightChild = newRoot.leftChild
    if newRoot.leftChild != None:
        newRoot.leftChild.parent = rotRoot
    newRoot.parent = rotRoot.parent
    if rotRoot.isRoot():
        self.root = newRoot
    else:
        if rotRoot.isLeftChild():
                rotRoot.parent.leftChild = newRoot
        else:
            rotRoot.parent.rightChild = newRoot
    newRoot.leftChild = rotRoot
    rotRoot.parent = newRoot
    rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)
    newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)

这是否避免了一个无限循环（与其互补的rotateRight），如果是，如何避免？在

Answer 1

根据我对平衡BST的理解，你不仅有左/右旋转，而且你有4种类型的轮班。左、左旋转（类似于右-右）和右-左旋转（类似于左-右）。 我可能错了至少这是我写的算法。其中，左和右的方向表示树的最后两个步骤是在哪里找到插入点的。 你可能想看看AVL树的，因为这似乎是你试图解决的问题类型。在