从 Python 中的 k-d-Tree 中删除根

Question

对于 python 的新手，我不明白如何从递归函数中删除 class 的实例。

的这段代码

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 了。您要做的是从树中删除节点。但是，您没有树对象，只有节点。那么当没有树可以移除节点时，如何从树中移除节点呢？

大方一点，您可以通过说节点集合是一棵树来争辩说您是在没有显式树的情况下实现树 class。但是你有问题，空树是什么样子的？此外，树的客户端需要对树的引用（因此它可以添加和删除节点），但由于您没有树对象，它只能引用对节点的引用。因此，客户端是唯一具有清空树的能力的客户端，它必须通过删除它对节点的引用来做到这一点。 Python 中的对象不可能在不知道这些对象的情况下从其他对象中删除对自身的任意引用，因此您的根节点通常不能从 "tree"，这意味着删除对客户端持有的节点的引用。要实现这一点，需要在根节点和客户端之间定义一个接口，因此当客户端说 "delete this node" 时，根节点可以回复并说 "that's actually me, so delete me and you've got an empty tree"。但这会很痛苦。

此外，作为节点集合的隐式概念树违背了Zen of Python:

Explicit is better than implicit.

所以我建议您实现一个明确的简单树 class，它可以是空的并且您的客户可以持有对它的引用。如果你让它看起来有点像一个节点，它可以只是根节点的父节点，就根节点而言，它（根节点）是一个普通的子节点。像 （警告：未测试，假设上面的 remove() 函数实际上是节点 class 上的一个方法）:

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)

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为对象释放内存。这是一个完全有效的操作，尽管它在实际代码中是 not something you would normally do。即调用a->suicide()后，指针a失效，因为它继续指向的内存已经不存在了。例如，如果您之后再次尝试调用 a->suicide()，则会出现分段错误（因为为了调用 a->suicide，您需要在内存中查找指向方法 suicide 的指针由 a 指向，此内存不再有效。

但有意义与否，你真的可以从任何地方销毁一个C/C++对象（即释放它的内存），包括对象自己的方法（当然，假设它是在堆上创建的。

现在让我们回到Python。在Python，情况就不同了。尽管您在 Python 中显式创建对象，就像在 C/C++ 中一样，但您无法强制释放它们的内存。所有内存都由垃圾收集器管理，它会跟踪当前引用了哪些对象，哪些没有，并清理无法访问的对象at the moments it decides appropriate.

虽然 Python 语句 del self 在句法上看起来与 C/C++ 中的 delete this 相似，但实际上是 something completely different。不是内存管理器清理内存的命令。相反，它只是从 "local variables" 字典中删除键 self。相应的值（即内存 self 正在引用）仍然挂在堆上的某个地方。

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

将上面 C/C++ 代码的 "literal translation" 考虑为 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]的含义。

从 Python 中的 k-d-Tree 中删除根

Remove root from k-d-Tree in Python

python

kdtree