lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


Hi Lenny,

if you never re-use your nodes, you could add a 'parent' field to each of them. This way, removal could be executed simply by setting 'self.parent[child]' to be nil. Of course, you'd still have to find out which child you are of your parent -- but that could be easily done with an '==' comparison.

Of course, if you don't want to add parent information to your nodes (e.g., if you're actually using a sparse directed graph instead of an actual tree), you'll have to use another solution.

  Regards,

		Pedro.



I have implemented a simple binary search tree that uses recursive calls for
traversal, insertion and deletion, as most trees would. I'll simplify my
problem of deletion to leaf nodes only. My problem is that Lua variables
store references to tables, and when modifying the variable, like setting it
to nil, only affects the variable. So I was surprised, when I really
shouldn't have been, when my deletion did not work.

Here is my deletion code:

_remove = function(self, node, obj)
  if node then
    local r = self:compare_func(obj, node.data)
    if r < 0 then
      self:_remove(node.left, obj)
    elseif r > 0 then
      self:_remove(node.right, obj)
    else
       if not node.left and not node.right then
        node = nil  -- delete the node, but it really does not "delete" the
node
      end
    end
  end --end "if node then"
end

node is a table and a leaf node would look like { data = obj, left = nil,
right = nil }

Skirting around the problem,  I decided to pass an additional parameter to
my _remove function, the parent node and a flag, indicating that the current
node is on the left or right of the parent.

  self:_remove(node.right, {parent = node, child = "right"}, obj);

and then delete the node with

  pnode.parent[pnode.child] = nil

I don't like this solution, is there a better way to do this that I'm not
seeing?

Thanks,
-Lenny

--
Pedro Miller Rabinovitch
Gerente Geral de Tecnologia
Cipher Technology
www.cipher.com.br