Lasse Reichstein Nielsen wrote:

"Csaba Gabor" <da*****@gmail.com> writes:

[traversal by pointer reversal]

I never saw this before - it's interesting, reminding me of splay trees

- would you be a little more specific, please.

I *wish* I could find a reference for this on the web (or in any of my

books). It was just something my advisor mentioned to me at some point,

as a well known method for traversing trees.

Assume that we have some node structure with the operations of DOM

nodes, but without the HTML structure requirements. Then the following

algorithm will traverse all nodes (sadly not necessarily visiting each

just once):

In fact, it will visit each node (1 + #-of-node's-children) times

.... very nice code details ...

By putting the parent as the last child of its first child, do you

also mean that the parent should disconnect that first child as its

child?

It should, yes.

And where does the action come in?

That is a problem, since some nodes are traversed more than once,

and the algorithm doesn't store information about where it came

from or what nodes are really pointer-reversed parent nodes.

So for the purpose of the OP, it's not very usable. I do think it's

a neat algorithm, though :)

Indeed, if we are not allowed to mark nodes as visited, then it becomes

an interesting problem. What I puzzled out was that to do a DFS, the

action should be taken whenever the original root node is contained in

the right child of the current root (plus at the beginning of the

initial call). To get a pseudo intuitive feeling for this, consider

that the nodes underneath a given top level node (because all nodes

become top level, eventually) are being barrel rotated, so at most one

of these rotations should be used for an action - the first one, which

is when the original root is in its rightmost subtree.

Hmmm, how to find out whether a given node is in a subtree? Well,

maybe we could just make use of the same algorithm. But is it

reentrant? ... Yes! However, you must walk the entire subtree (even if

you find the answer to be yes right away) otherwise your tree will be

corrupted. So this single requirement imposes a quite a high time

overhead, but if marking is allowed, then there will be exactly n+m

node visits (same as traversal, number of nodes plus number of edges),

since each node is visited once for itself, and its parent receives a

corresponding visit, too.

As an example, I programmed up the non marking variant as traversal and

as a DFS, leveraging off the code you provided. The complete cut and

paste example is below. The central engine is:

function funkyTraverse (elem, action) {

var rootCt = elem.childNodes.length, startNode = elem;

var fakeParent = !elem.parentNode;

if (fakeParent) elem.parentNode = elem; // for .replaceNode on root

for (action.apply(elem); rootCt;

(rootCt-=((elem=elem.parentNode)==startNode))

? action.apply(elem): "")

elem.firstChild.appendChild(

elem.parentNode.replaceChild(

elem.removeChild(elem.firstChild),elem));

if (fakeParent) delete (elem.parentNode);

}

The business with the fakeroot is so that either a subtree or original

tree may be passed in. The one line body of the for does the tree

rotation. Only then elem is the child of the new root, so that is what

the elem=elem.parentNode is for. The way we figure out when we're done

is that on entry, we count the number of children the root has. When

the original root has surfaced that many times, we're done. On the

very last pass, when we get the original tree back, we don't want to

take an action on it (since we've already seen it) - the ? ... : form

is because javascript doesn't want an if within the for (...)

declaration.

I've also added p=parent and fc=first child to the string

representation of a node, because debugging this can be a bear. Make

one teeny tiny little mistake and your tree is blown to pieces - you

will have not the slightest clue about the source of the mistake. Add

reentrancy into the mix and it's a real party.

If you would give the recursive form of the function, at least in

some pseudo code, that would be great.

The point is to not be recursive, and not use extra space for a stack.

I believe (without knowing for sure) that a similar method is used by

garbage collectors to traverse a tree without using more than constant

extra space.

My bad. I meant to put functional form of the algorithm. I've seen

tree rotations before, but never like this. Thanks for sharing a very

interesting approach.

Complete code example below,

Csaba Gabor from Vienna

<html><head><title>funky traversals with tree rotations</title></head>

<body onload="test()">

<script type='text/javascript'>

function funkyTraverse (elem, action) {

var rootCt = elem.childNodes.length, startNode = elem;

var fakeParent = !elem.parentNode;

if (fakeParent) elem.parentNode = elem; // for .replaceNode on root

for (action.apply(elem); rootCt;

(rootCt-=((elem=elem.parentNode)==startNode))

? action.apply(elem): "")

elem.firstChild.appendChild(

elem.parentNode.replaceChild(

elem.removeChild(elem.firstChild),elem));

if (fakeParent) delete (elem.parentNode); }

function test() {

var root = initTree();

alert("Depth First Search (DFS):");

funkyTraverse(root, function (oRoot, fcoRoot) { return function() {

// 1st half of if for root; 2nd part for all others

if ((this==oRoot && this.firstChild==fcoRoot) ||

inTree(this.childNodes[this.childNodes.length-1], oRoot))

alert("Step: "+this); } }(root, root.firstChild));

alert("<br>Full traverse details:");

funkyTraverse(root, function () { alert("Step: " + this) } ); }

function inTree(root, node) {

// returns true iff node is in the subtree rooted at root

inTree.res = false;

funkyTraverse(root, function(nod) { return function() {

if (!inTree.res) inTree.res = (this==nod); } }(node));

return inTree.res; }

function alert(item) {

// writes a new line to the div instead of popping up

document.getElementById('log').innerHTML += item + "<br>"; }

Node.prototype.appendChild = function(childNode) {

this.childNodes.push(childNode);

childNode.parentNode = this;

if (this.childNodes.length == 1) this.firstChild = childNode;

return childNode; }

Node.prototype.removeChild = function(childNode) {

for (var i=this.childNodes.length;i--;)

if (this.childNodes[i]==childNode) {

if (!i) {

if (this.childNodes.length>1) this.firstChild =

this.childNodes[1];

else delete (this.firstChild); }

delete (childNode.parentNode);

return this.childNodes.splice(i,1).pop(); } }

Node.prototype.replaceChild = function (newChild, oldChild) {

delete (oldChild.parentNode);

for (var i=this.childNodes.length;i--;)

if (this.childNodes[i]==oldChild) {

if (!i) this.firstChild = newChild;

newChild.parentNode = this;

return this.childNodes.splice(i, 1, newChild).pop(); }

newChild.parentNode = newChild; // fake roots section

return oldChild; }

Node.prototype.toString = function() { // show tree structure

for (var i = 0, cs=[]; i < this.childNodes.length; i++) {

cs[i] = this.childNodes[i].toString(); }

return this.name +

(this.parentNode ? " p="+this.parentNode.name : "") +

(this.firstChild ? " fc="+this.firstChild.name : "") +

((cs.length > 0) ? ": [" + cs + "]" : ""); };

function Node(name) { // create a new node

this.name = name; this.childNodes = []; }

function initTree() {

var A = new Node("A");

var B = new Node("B");

var C = new Node("C");

var D = new Node("D");

var E = new Node("E");

var F = new Node("F");

var G = new Node("G");

var H = new Node("H");

A.appendChild(B);

B.appendChild(C);

B.appendChild(D);

D.appendChild(E);

D.appendChild(F);

B.appendChild(G);

A.appendChild(H);

return A;

}

</script>

<div id=log>Tree Rotations<br><br></div>

</body>

</html>