Re: hacker challenge - traverse a list

On Sat, 01 Mar 2008 16:58:53 +0000, Richard Harter wrote:

On Sat, 01 Mar 2008 13:11:15 +0100, moi <root@xxxxxxxxxxxxxxxxxxx>
wrote:

On Fri, 29 Feb 2008 20:26:26 +0000, Richard Harter wrote:

On Fri, 29 Feb 2008 10:04:26 -0800, Ben Pfaff <blp@xxxxxxxxxxxxxxx>
wrote:

cri@xxxxxxxx (Richard Harter) writes:

Here is a little challenge - print the contents of a binary tree in
order only using O(1) additional memory.


My take is that you can modify the tree during the traversal provided
that it is in the original condition when you are done. The challenge
isn't explicit so I suppose that revising the tree counts.

O(n) is more elegant (!!?) and is what I had in mind, but a more
expensive method without modifying the tree is a fair solution.

Loosely speaking, this is about constructing an iterator for the
treewalk: given a certain node)or key), find the one that should be the
next to visit.


Well this smells like the XOR hack ...

I am still not sure if the XOR-hack works for this particular problem.


Here's the general idea. Suppose you have just arrived at a node. At
this point you know where you came from. What you are going to do next
is visit your children one after another. When you get done visiting
them you want to go back to where you came from. So what you want to do
is to somehow nondestructively store the information about where you
came from (a link to your parent) in the node.

Fortunately the link holding the address of the child you are going to
visit can be overwritten - we will know what it was when we return from
the visit because we know where we just came from. So, we can stick the
parent's address there while we are off visiting and restore the link
when we get back. There is a catch though; when we get back how do we
know whether we just came from visiting the left child or the right
child. We need somehow to save one additional bit of information. The
obvious way to do this is to use a tag bit to designate which child we
visited. This idea is the basis for the DSW algorithm; whether it is a
hack or not is, I suppose, a matter of perspective. It turns out that
you can do a clever trick with moving pointers around that implicitly
captures that bit of information; that's the Lindscott variation that
Gene mentioned. I thought there was an xor based hack to store the bit
but I can't get it to work.


I have tried this kind of construction yesterday. It seemed to work
reasonably, except for the root node, which has no parent, and makes it
impossible for it's children to find out weather they are on the left or
right side of the root.

Another idea I have, is to extend the "dancing links" principle to three
pointers:
Every node needs three pointers (parent,left,right), but has place for
only two. Rotating the pointervalues over the two locations + a temp
could do the trick, but again one needs to remember the "state" (number
of times a node has undergone rotation), which needs 1.5 (;-) bit per
node. Plus: there is again a null-pointer and termination-problem.
(storing the two bits in the lower bits of the pointers is obvious, but
forbidden by the rules of the game)

Yet another bit (maybe 1.5 ?) of information is present in the nodes, if
the "comparison" function is known by the treewalker.That could be
exploited to determine whether a node has been permuted or not.
(non-unique keys will probably ruin this trick). Null vs root's parent is
again a problem.


Back to the old drawing board,
AvK


.

Relevant Pages

  • Re: Creating and killing processes
    ... That will do the trick. ... > fork twice let the intermediate process terminate ... > Unix the parent is responsible to do that, ... > 2) Collect the exist status of the child. ...
    (comp.os.linux.development.apps)
  • Re: Function inheritance
    ... > I need a vector contains pointers to functions of types above. ... the 'parent' and 'child'. ... a reinterpret_cast (not just a static cast) though, ...
    (comp.lang.cpp)
  • Re: How to avoid zombie processes?
    ... Without the trick, if the child terminate, and at the moment, ... a little later, the parent calls wait, the child process is not ... a zombie any more and disappear in the ps command. ... With this trick, there is NO zombie, even for a short period of time. ...
    (comp.unix.programmer)
  • Re: Tree traversal algorithm
    ... This is pretty easy if you have a binary tree and child pointers you can follow. ... From an SQL point of view it would be far nicer to store trees as nested sets, where each node has a left and right index number indicating how many children it has. ... The parent pointer structure we have now makes it trivially easy to share parent trees - with the cost of making queries very hard/inefficient, ...
    (comp.graphics.algorithms)
  • Query of changes to parent or child
    ... I have a parent table with 3 children tables. ... Each of the child ... The client wants a query where any parent record where 1 or more of ... I was hoping for some pointers on the most efficient way to do this. ...
    (microsoft.public.access.queries)
Loading