lua-users home
lua-l archive

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


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