python - AVL 树不更新高度

Question

我正在尝试在 Python 中实现 AVL 树，但由于某种原因，当我实现一棵大树时它没有进行正确的旋转（我一直使用大小为 3 的树作为我的测试用例，但任何大于 3 的树都不能正确旋转) . 我认为问题在于它没有正确更新高度，但我不知道为什么。
这是我到目前为止所拥有的：

class AVLTreeMap:

def __init__(self, key, value):
    self.key = key
    self.value = value
    self.left = None
    self.right = None
    self.height = 1


def updateHeight(self):
    if self.right is None:
        right = -1
    else:
        right = self.right.height
    if self.left is None:
        left = -1
    else:
        left = self.left.height
    self.height = (1 + max(left, right))


def getBalance(self):
    if self is None:
        return 0
    if self.right is None:
        right = -1
    else:
        right = self.right.height
    if self.left is None:
        left = -1
    else:
        left = self.left.height
    return right - left

def put(self, key, value):
    if self is None:
        return AVLTreeMap(key, value)
    elif key < self.key:
        if self.left is None:
            self.left = AVLTreeMap(key, value)
        else:
            self.left.put(key, value)
            self.updateHeight()
            balance = self.getBalance()
            if balance <= -2:
                if key < self.left.key:
                    self.leftLeft()
                else:
                    self.leftRight()
    elif key == self.key:
        self.value = value
    elif key > self.key:
        if self.right is None:
            self.right = AVLTreeMap(key, value)
        else:
            self.right.put(key, value)
            self.updateHeight()

            balance = self.getBalance()
            if balance >= 2:
                if key < self.right.key:
                    self.rightLeft()
                else:
                    self.rightRight()

def rightRight(self):
    pivot = self.right
    pivot.left = self
    self = pivot
    self.right.updateHeight()
    self.updateHeight()

def leftLeft(self):
    pivot =self.left
    pivot.right = self
    self = pivot
    self.left.updateHeight()
    self.updateHeight()

def leftRight(self):
    pivot1 = self.left
    pivot2 = pivot1.right
    pivot3 = self
    self = pivot2
    self.left = pivot1
    self.right = pivot3
    self.left.updateHeight()
    self.right.updateHeight()
    self.updateHeight()

def rightLeft(self):
    pivot1 = self.right
    pivot2 = pivot1.left
    pivot3 = self
    self = pivot2
    self.left = pivot3
    self.right = pivot1
    self.left.updateHeight()
    self.right.updateHeight()
    self.updateHeight()

任何帮助深表感谢

标签： pythonpython-3.xavl-tree