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