在Python中从kd-Tree中删除root

Question

对于刚接触python的人,我不明白如何从递归函数中删除类的实例.

考虑一下kd树的代码:

def remove(self, bin, targetAxis=0, parent=None):
  if not self:
    return None
  elif self.data.x == bin.x and self.data.y == bin.y: 
    if self.rightNode:
      self.data = self.rightNode.findMin((targetAxis+1)% KdSearch.DIMENSION)
      self.rightNode = self.rightNode.remove(self.data, (targetAxis+1)% KdSearch.DIMENSION,self)
    elif self.leftNode:
      self.data = self.leftNode.findMin((targetAxis+1)% KdSearch.DIMENSION)
      self.rightNode = self.leftNode.remove(self.data, (targetAxis+1)% KdSearch.DIMENSION,self)
    else:
      if not parent is None:
        #get direction if child....
        if not parent.leftNode is None:
          if parent.leftNode.data.x == bin.x and parent.leftNode.data.y == bin.y:
            parent.leftNode=None

        if not parent.rightNode is None:
          if parent.rightNode.data.x == bin.x and parent.rightNode.data.y == bin.y:
            parent.rightNode=None

      else:
        print("Trying to delete self")
        del self.data
        del self.leftNode
        del self.rightNode
        del self.splittingAxis


  else:
    axis = self.splittingAxis  % KdSearch.DIMENSION
    if axis==0:
      if bin.x <= self.data.x :
        if self.leftNode:
          self.leftNode.remove(bin,(targetAxis+1)% KdSearch.DIMENSION,self)
      else:
        if self.rightNode:
          self.rightNode.remove(bin,(targetAxis+1)% KdSearch.DIMENSION,self)
    else:
      if bin.y <= self.data.y:
        if self.leftNode:
          self.leftNode.remove(bin,(targetAxis+1)% KdSearch.DIMENSION,self)

      else:
        if self.rightNode:
          self.rightNode.remove(bin,(targetAxis+1)% KdSearch.DIMENSION,self)

重要的是这个:

        del self.data
        del self.leftNode
        del self.rightNode
        del self.splittingAxis

如何删除当前实例？该del self或self=None或我的做法是行不通的

Answer 1

你想要做的事情在语言中没有意义，更不用说在Python中了。您要做的就是从树中删除该节点。但是，您没有树对象，只有节点。那么，当没有树可以删除节点时，如何从树中删除该节点呢？

慷慨地说，您可以说您是在没有显式树类的情况下实现树，将节点的集合称为树。但问题来了，一棵空树是什么样子的？另外，树的客户端需要对树的引用（因此它可以添加和删除节点），但由于您没有树对象，所以它只能有对节点的引用。因此，客户端是唯一具有清空树能力的客户端，它必须通过删除对节点的引用来完成此操作。Python 中的对象不可能在不了解其他对象的情况下从其他对象中删除对自身的任意引用，因此您的根节点通常无法从“树”中删除自身，这意味着删除对客户端持有的节点的引用。要实现这一点，需要在根节点和客户端之间定义一个接口，因此当客户端说“删除这个节点”时，根节点可以回复并说“那实际上是我，所以删除我，你就会得到一棵空树” 。但这会很痛苦。

此外，作为节点集合的隐式概念树违背了Python 的禅宗：

显式的比隐式的好。

因此，我建议您实现一个显式的简单树类，该树类可以为空，并且您的客户端可以保存对它的引用。如果你让它看起来有点像一个节点，它可以只是根节点的父节点，而就根节点而言，它（根节点）是一个普通的子节点。类似于（警告：未测试，并假设remove()上面的函数实际上是节点类上的方法）：

class Tree:

    def __init__(self):
        self.leftNode = None
        # need a rightNode to look like a node, but otherwise unused.
        self.rightNode = None

    # This will probably be useful.
    @property
    def isEmpty(self):
        return self.leftNode is None

    def addNode(self, node):
        if self.leftNode is not None:
            self.leftNode = node
            return
        self.leftNode.add(node, parent=self)

    def removeNode(self, node):
        # the node will remove itself from us, the parent, if needed
        self.leftNode.remove(node, parent=self)

然后客户端会执行以下操作：

tree = Tree()
tree.isEmpty
tree.addNode(node)
tree.removeNode(node)