For each n-dimensional link replace node with its (n-1)-dimensional local yield, the node's (n-1)-dimensional successor is now the (n-1)-dimensional successor of the maximal node in (n-1)-dimensional spine of the yield. Because it is the maximal node in the (n-1)-dimensional spine it cannot have an (n-1)-dimensional successor and it is safe to append nodes below it. However, we are still permitted to add an (n-1)-dimensional successor to it because we are simply extending the (n-1)-dimensional spine by appending an (n-2)-dimensional yield. This is permitted to be a (n-1)-dimensional successor because it is an (n-1)-dimensional successor prior to moving it.
All other successors (less than (n-1)-dimensional) of the node become successors of the root of the (n-1)-yield. Since it is the root of an (n-1)-dimensional yield it doesn't already have any j dimensional successors for j < n-1. Also, after replacing its predecessor node it will be the same type of successor that its predecessor was, and because of this it is valid to move the successors from the node to the root of the yield.
When we replace a node with its n-dimensional link, the new node, which was an n-dimensional successor, is now either a root or an i-dimensional successor, n < i < 1. Since it was an n-dimensional successor, the least dimension of its pre-existing children was n-1, so it is therefore permitted to be an (n-1)-dimensional root or an i-dimensional successor, n-1 < i < 1.
project(tree) {
if(tree == empty) {
return tree;
}
for i from 1 to n-1
tree.link(i) = project(tree.link(i))
if(tree has an nd link) {
if(tree has (n-1)-dimensional link)
find_foot(tree.link(n)).link(n-1)=tree.link(n-1)
for i from n-2 to 1
tree.link(n).link(i) = tree.link(i)
tmp = project(tree.link(n))
set all tree links to NULL
delete tree
tmp.set_dim(n-1)
return tmp
}
else
tree.set_dim(n-1)
return tree
}
Posted by lemanal at July 19, 2004 04:21 PM