Я написал код для поворота дерева AVL, но получил ошибку в нем - PullRequest
Новая
       8

Я написал код для поворота дерева AVL, но получил ошибку в нем

0 голосов
/ 09 апреля 2020

Это мой код, но он дает ошибку в повороте дерева AVL. Где я ошибся? Это Python дерево AVL, связанное с кодом. 

class MyAVL(MyBST):
    def __init__(self, data):
        # Initialize this node, and store data in it
        super().__init__(data)


    def getBalanceFactor(self):
        # Return the balance factor of this node
        if self.left:
            left_subtree_height = self.left.getHeight()
        else:
            left_subtree_height = -1

        if self.right:
            right_subtree_height = self.right.getHeight()
        else:
            right_subtree_height = -1

        return left_subtree_height - right_subtree_height

    def insert(self, data):
        # Insert data into the tree, descending from this node
        # Ensure that the tree remains a valid AVL tree
        # Return the node in this node's position after data has been inserted
        if data < self.data:
            if self.left:
                self.left = self.left.insert(data)
            else:
                self.left = self.__class__(data)
        elif data > self.data:
            if self.right:
                self.right = self.right.insert(data)
            else:
                self.right = self.__class__(data)
        else:
            return self

        node_balance = self.getBalanceFactor()

        # LL
        if node_balance > 1 and data < self.left.data:
            return self.rightRotate()

        # RR
        if node_balance < -1 and data > self.right.data:
            return self.leftRotate()

        # LR
        if node_balance > 1 and data > self.left.data:
            self.left = self.left.leftRotate()
            return self.rightRotate()

        # RL
        if node_balance < -1 and data < self.right.data:
            self.right = self.right.rightRotate()
            return self.leftRotate()

        return self

    def leftRotate(self):
        # Perform a left rotation on this node and return the new node in its spot
        new_root = self.right
        sub_tree = new_root.left
        new_root.left = self

        self.right = sub_tree

        return new_root

    def rightRotate(self):
        # Perform a right rotation on this node and return the new node in its spot
        new_root = self.left
        sub_tree = new_root.right
        new_root.right = self
        self.left = sub_tree


        return new_root

Код показывает ошибку для этой части. Этот тест не пройден; Я не знаю, почему это происходит, но код выглядит правильно. 

if not (first is avl.getRight().getLeft().getRight()):
        if verbose:
            print("Error: AVL Rotation incorrect #3")
        return False

    if verbose:
        print("AVL Double Rotation test complete")
    yield True # Rotation test complete
...