2

我现在正在研究 AVL 树，除了删除节点方法外，我即将完成。我现在有点卡住了，需要一些帮助。我这样做的方法是找到要删除的节点并递归调用路径中每个节点上的余额，以便在删除所需节点后，一系列树余额将在树上完成工作。不幸的是，由于某些奇怪的原因，平衡并没有按预期工作——我打印了一些东西来测试发生了什么，并且由于某种原因，如果我们有这样的树，例如：

    6
   / \
 3      18 
  \    /  \
   5  9    74
          /  \
         50   99

并说我想删除9，所以会出现不平衡，平衡只会平衡6的根节点，而不是18的节点......

def deleteNode(self, val, root, previous):

        if (val==root.value):

            if (root.right is None and root.left is None):
                if (previous is not None and (previous.value>root.value)):
                    previous.left=None
                else:
                    if (previous is not None and (previous.value<root.value)):
                        previous.right=None
                    else:
                        if (previous is None):
                            self.root=None
                return

            if (root.right is None and root.left is not None):

                if (previous is not None and (previous.value>root.value)):
                    previous.left=root.left
                else:
                    if (previous is not None and (previous.value<root.value)):
                        previous.right=root.left
                    else:
                        if (previous is None):
                            self.root=root.left
                return

            if (root.left is None and root.right is not None):

                if (previous is not None and (previous.value>root.value)):
                    previous.left=root.right
                else:
                    if (previous is not None and (previous.value<root.value)):
                        previous.right=root.right
                    else:
                        if (previous is None):
                            self.root=root.right
                return

            if (root.left is not None and root.right is not None):

                rval=self.maxValue(root.left).value
                self.deleteNode(self.maxValue(root.left).value , self.root, None)
                root.value=rval

                return






        else:
            if (root.value<val):
                self.deleteNode(val, root.right, root)


                if (root.right is not None):
                    print root.value,
                    print root.right.value
                    self.balance(root.right, root)
            else:
                if (root.value>val):
                    self.deleteNode(val, root.left, root)

                    if (root.left is not None):
                        print root.value,
                        print root.left.value

                        self.balance(root.left, root)

解决了-我只是有一个不正确的平衡系统。

4

0 回答 0