Table references

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Table references

Lenny Palozzi-3
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


Reply | Threaded
Open this post in threaded view
|

Re: Table references

Pedro Miller Rabinovitch-3
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

Reply | Threaded
Open this post in threaded view
|

Re: Table references

Luiz Henrique de Figueiredo
In reply to this post by Lenny Palozzi-3
>I have implemented a simple binary search tree

Why? Searching in Lua is almost always wrong, given that tables give you
direct, constant-time access to data. Or am I missing something?
--lhf

Reply | Threaded
Open this post in threaded view
|

Re: Table references

Lenny Palozzi-4
On Tue, Jan 16, 2001 at 08:54:44PM -0200, Luiz Henrique de Figueiredo wrote:
> >I have implemented a simple binary search tree
> 
> Why? Searching in Lua is almost always wrong, given that tables give you
> direct, constant-time access to data. Or am I missing something?
> --lhf

Why? Simply to give me something to do in Lua. Or, more interestingly, I could be writing a 3D engine in Lua that uses a BSP Tree.

I am aware that tables provide direct access to data, in fact I am using that very feature. 

Regardless of what my intentions are, any suggestions? (I'm waiting for another of those Lua life-saving one-liners that I'm sure someone will think of. Lua always seems to come through somehow. :) ) 

-Lenny.