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

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)