在Python中从k-d树中删除根节点

Question

对于一个新手来说，我不明白如何在递归函数内部删除类的实例。

考虑这段 k-d Tree 的代码：

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 或我的方法都不起作用。

- greedsin

---

当你在节点中时，没有办法做到这一点。请参见我的答案：http://stackoverflow.com/questions/42972748/unable-to-remove-object-after-using-del-statement-in-python/42973978#42973978 - Elan

你看到这个了吗？https://dev59.com/fHVC5IYBdhLWcg3wcgqd - Matthias

“删除当前实例”是什么意思？您是指从内存/RAM中删除它吗？还是指从数据结构中删除它（例如“从树中删除节点”）？此外，“remove（）”是类的方法吗？目前，您的代码使其看起来像一个简单的函数，巧合地调用其第一个参数“self”，这是一件令人困惑的事情（如果它是一个方法，则“self”永远不会为none）。通常在Python中，您无法从其方法中“删除”实例，因为该方法本身持有对实例的引用，从而防止其被删除。 - daphtdazz

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)

- daphtdazz

Answer 2

在了解Python之前，请看下面的C/C++代码：

struct A {
   virtual void suicide() {
      delete this;
   }
};

int main() {
   A* a = new A();
   a->suicide();
   return 0;
}

首先，一个类型为A的对象被显式地创建。这归结于分配和初始化一个小片内存(对象中唯一存储的是指向suicide函数的指针)，并设置变量a指向该内存。

接下来，调用suicide函数，在内部通过调用delete this请求运行时释放对象的内存。虽然这在现实生活中通常不会做，但这是完全有效的操作。换句话说，在调用a->suicide()后，指针a变得无效，因为它继续指向的内存已经不存在了。例如，如果之后尝试再次调用a->suicide()，就会导致分段错误(因为为了调用a->suicide，需要在a指向的内存中查找方法suicide的指针，而这个内存已经失效)。

但是，无论是否有意义，你确实可以从任何地方（包括对象自己的方法）销毁一个C/C++对象（即释放其内存），前提是它是在堆上创建的。

现在让我们回到Python。在Python中，情况是不同的。虽然你像在C/C++中一样显式地创建对象，但你没有办法强制释放它们的内存。所有的内存都由垃圾回收器管理，它跟踪当前被引用和未被引用的对象，并在适当的时候清理不可达的对象（链接1）。

虽然Python语句del self在语法上与C/C++中的delete this相似，但它实际上是完全不同的东西。它不是一条指令，要求内存管理器清理内存。相反，它只是从“本地变量”字典中删除了键self。对应的值（即self引用的内存）仍然悬挂在堆中的某个位置。

当然，如果没有其他人指向那块内存，垃圾收集器很快就会释放它（尽管这也不能保证，因为它确实取决于使用的GC算法），但是由于执行了del self，所以仍有某个人指向内存，因为该人刚刚调用了该方法。

考虑将上述C/C++代码的“逐字翻译”转换为Python：

class A(object):
   def suicide(self):
      del self

a = A()
a.suicide()

这也是完全有效的Python代码，但是这里的del self什么也不做（除了禁止您在同一方法中稍后引用self，因为您从作用域中删除了该变量）。 只要存在一个指向创建的对象的变量a，其内存就不会被释放。就像这里不会释放内存一样，例如：

a = A()
b = a
del a

为了更好地理解，我建议您将Python中的del d[key]的意义与C / C ++中的delete d[key]进行比较。

- KT.