从BST递归删除

问题描述 投票:0回答:1

我完成了我要删除的节点是根节点或叶节点的情况,但是当它有兄弟姐妹或孩子时我也需要能够删除,我发现这很难。

class Node:
    def __init__(self, key=None, data=None):
        self.key = key
        self.data = data
        self.left = None
        self.right = None


class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def remove(self, key):
        self.root = self._remove(key, self.root)

    def insert(self, key, data):
        self.root = self._insert(self.root, key, data)

    def _insert(self, root, key, data):
        if root == None:
            self.size += 1
            return Node(key, data)
        if root.key == key:
            return root
        elif root.key > key:
            root.left = self._insert(root.left, key, data)
        else:
            root.right = self._insert(root.right, key, data)
        return root

    def _remove(self, key, node):
        if node == None:
            return None
        if key == node.key:
            if node.left != None and node.right == None:  # if trying to remove root and right side is empty
                return node.left
            elif node.left == None and node.right != None:  # if trying to remove root and left side is empty
                return node.right
            elif node.left == None and node.right == None:  # if trying to remove leaf
                return node
            # two more cases to check when it has siblings

        # iterates recursively in the bst
        elif key <= node.key:
            node.left = self._remove(key, node.left)
        else:
            node.right = self._remove(key, node.right)

        return node

我发布了整个代码,所以如果有人想在他们的机器上测试,欢迎这样做,或者有人可以将它用于教育目的。

python recursion binary-search-tree
1个回答
0
投票

将来尝试执行一些调试并提供一些示例输出和预期输出。

考虑下面

def _remove(self, key, node):
        if node == None:
            return None
        if key == node.key:
            if node.left and not node.right:  # only left
                return node.left
            elif node.right and not node.left: # only right
                return node.right
            elif not node.right and not node.left: # neither
                return None
            else : # both
                inorder_successor = node.right
                while inorder_successor.left:
                    inorder_successor = inorder_successor.left
                # remember to replace inorder_successor with it's right child
                ...
                ...
                return inorder_successor

        # iterates recursively in the bst
        elif key <= node.key:
            node.left = self._remove(key, node.left)
        else:
            node.right = self._remove(key, node.right)

        return node

关于改变了什么的一些观察

  1. 你检查None使用,is != None这是一种非常非Pythonic的方式。请检查isis not
  2. 替换具有两个子节点的BST中的节点的正确方法是使用inorder后继节点(已删除节点的右子节点的最左侧后代)
© www.soinside.com 2019 - 2024. All rights reserved.