Remove root from k-d-Tree in Python

Question

For someone who is new to python, I don't understand how to remove an instance of a class from inside a recursive function.

Consider this code of a 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)

The important part is this:

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

How can i delete the current instance? The del self or self=None or my approach is NOT working

Nuncio

There is no way to do it when you are in the node. See my answer here #42973248 – Saddlecloth

did you see this? #293931 – Vietcong

What do you mean by "delete the current instance"? Do you mean remove it from memory / RAM? Or do you mean remove it from your data structure (as in "remove a node from the tree")? Also, is remove() a method on a class? Currently your code makes it look like a simple function which coincidentally calls its first argument self, which is a confusing thing to do (if it's a method then self will never be none). In general in python you cannot "delete" the instance from within its method, because the method itself holds a reference to the instance preventing it from being deleted. – Briones

Answer 1

What you're trying to do doesn't make sense in words, let alone in Python. What you want to do is remove the node from the tree. However, you don't have a tree object, you only have nodes. So how can you remove the node from the tree when there is no tree to remove it from?

Being generous, you could argue that you're implementing the tree without an explicit tree class by saying that a collection of nodes is a tree. But then you have the problem, what does an empty tree look like? Also, the client of the tree needs a reference to the tree (so it can add and remove nodes), but since you don't have a tree object, it can only have a reference to a node. Therefore, the client is the only one with the capability of emptying the tree, which it must do by deleting its reference to the node. It is not possible for an object in Python to remove arbitrary references to itself from other objects without knowledge of those objects, so your root node cannot generally delete itself from the "tree", which would mean deleting the reference to the node the client holds. To implement this would require a defined interface between the root node and the client, so when the client says "delete this node" the root node can reply and say "that's actually me, so delete me and you've got an empty tree". But this would be a pain.

Also, an implicit conceptual tree that is a collection of nodes goes against the Zen of Python:

Explicit is better than implicit.

So what I suggest is that you implement an explicit simple tree class that can be empty and that your client can hold a reference to. If you make it look a bit like a node, it can just be the parent of the root node and as far as the root node is concerned it (the root node) is a normal sub-node. Something like (caveat: not tested, and assuming the remove() function above is really a method on a node 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)

Then the client does things like:

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

Briones

Answer 2

Before looking at Python, consider the following C/C++ code:

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

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

First, an object of type A is explicitly created. This boils down to allocating and initializing a small piece of memory (the only thing stored in the object is a pointer to the suicide function) and setting the variable a to point to that piece of memory.

Next, the suicide function is called, which internally asks the runtime to release the memory for the object by calling delete this. This is a totally valid operation, although it is not something you would normally do in real-life code. Namely, that after a->suicide() is called, the pointer a becomes invalid, because the memory it continues to point to is no longer there. For example, if you tried calling a->suicide() again afterwards, you would get a segmentation fault (because in order to call a->suicide you need to look up the pointer to the method suicide in the memory pointed to by a, and this memory is no longer valid).

But meaningful or not, you really can destroy a C/C++ object (i.e., release its memory) from any place, including the object's own method (assuming it was created on the heap, of course).

Now let us go back to Python. In Python, the situation is different. Although you create objects explicitly in Python, just like you do in C/C++, you have no way of forcefully releasing their memory. All the memory is managed by the garbage collector, which keeps track of which objects are currently referenced, which are not, and cleans the unreachable ones at the moments it decides appropriate.

Although the Python statement del self may seem syntactically similar to delete this in C/C++, it is really something completely different. It is not an order to the memory manager to clean the memory. Instead, it simply removes the key self from the "local variables" dictionary. The corresponding value (i.e. the memory self was referencing) still remains suspended somewhere on the heap.

Of course, if no one else points to that memory, chances are the garbage collector will release it soon (although not even this is guaranteed because it really depends on the GC algorithm used), but as you did a del self, someone is still pointing at the memory, because that someone just invoked the method.

Consider a "literal translation" of the C/C++ code above into Python:

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

a = A()
a.suicide()

It is also totally valid Python code, however del self here does nothing (except for prohibiting you to refer to self later along in the same method, because you deleted the variable from the scope). As long as there exists a variable a pointing to the created object from somewhere, its memory will not be released. Just as the memory would not be released here, for example:

a = A()
b = a
del a

For better understanding I suggest you also compare the meaning of del d[key] in Python with delete d[key] in C/C++.

Cyprinodont