Re: Table references

[Pedro Miller Rabinovitch <pedro@...>]

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