AVL Tree не обновляет Высота - PullRequest
Новая
       14

AVL Tree не обновляет Высота

0 голосов
/ 12 марта 2019

Я пытаюсь реализовать дерево AVL в Python, но по какой-то причине не выполняется правильное вращение, когда я реализую большое дерево (я использовал деревья размером три для моих тестовых случаев, но для чего-то большего, чем три, нет)вращаться правильно).Я считаю, что проблема в том, что он не обновляет высоту должным образом, но я не могу понять, почему.
Это то, что у меня есть: 

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()

Любая помощь очень ценится

...