3
$\begingroup$

I was reading this blog post (https://research.swtch.com/treenum) that proposes a new base-k ordering for k-ary trees - I found myself wondering: is it possible to use Mathematica to solve a recurrence relation to provide a closed-form formula going from one index to its children's index?

enter image description here

For example, 0 would map to 1, 14 or 27 depending on the argument 0, 1 or 2) or 1 would map to 2, 6, 10 (given the argument 0, 1 or 2)...

You'd need to assume the tree has a maximum height.

Improve this question
$\endgroup$
5
  • $\begingroup$ This is the depth-first ordering. From my experience with binary trees, the breadth-firsth ordering is much better to work with. So is there any particular reason why you want the depth-first ordering? $\endgroup$
    – Henrik Schumacher
    Commented Feb 28 at 15:25
  • $\begingroup$ Data locality is much better with preorder - I completely agree breadth-first ordering is easier to work with. $\endgroup$
    – Torkoal
    Commented Feb 28 at 18:57
  • $\begingroup$ On the other hand, breadth first access is contiguous memory access. The hardware prefectcher has a much easier time to guess the next adresses and load the memory before it is actually accesses. Typically, the drawback of breadth-first is that you need a large queue instead of a small stack. But you need neither for full and complete k-ary tree... $\endgroup$
    – Henrik Schumacher
    Commented Feb 28 at 19:02
  • $\begingroup$ Anyways, I doable strategy would be to first run a depth-first search to find a node reordering. And then to permute all data associated to the nodes w.r.t this reordering. After that you can traverse simply by running forward or backward loops. If you have many traversals to do, then this will ammortize the one depth-first scan in the beginning. $\endgroup$
    – Henrik Schumacher
    Commented Feb 28 at 19:04
  • $\begingroup$ The idea is to have a tree where it isn't complete, but we use the node IDs as if it was $\endgroup$
    – Torkoal
    Commented Feb 28 at 19:20

2 Answers 2

Reset to default
2
$\begingroup$

We first define a function that creates the tree with input: k-> ary of tree and levels-> number of levels:

getTree[k_, levels_] := Module[{c = 0, tr},
  tr = NestTree[Range[k] &, 0, levels - 1];
  TreeMap[c++ &, tr, 
   TreeTraversalOrder -> {"DepthFirst", "TopDown", "LeftRight"}]
  ]

Here is an example:

tr = getTree[3, 4]

enter image description here

Then we define a function that gets the searched for child. Input: ind-> name of given node, d-> which of the k children, tr-> tree:

getChild[ind_, d_, tree_] := Module[{vl, pos},
  vl = VertexList[tree];
  pos = Append[TreePosition[tr, ind][[1]], d];
  Cases[vl, {_, pos}][[1, 1]]
 
  ]

Here is an example:

getChild[28, 2, tr]

30

Note, you would eventually like to add code that checks for invalid input. But to keep things simple, I leave it out here.

Improve this answer
$\endgroup$
1
$\begingroup$

Probably not what you want because this involves lookup tables. But there is a chance that this solves your problem, so I give it a shot.

First we generate a 3-ary tree of the desired depth (I store it as a directed graph for later use):

base = 3;
maxlevel = 3;
descendantcount[base_, maxlevel_] := 
  Quotient[base^(maxlevel + 1) - 1, base - 1];

T = Graph[ DirectedEdge @@@ EdgeList[KaryTree[descendantcount[base, maxlevel], base]]];

Next we build a lookup table IndexToDFS that map the index of the currect vertex ordering (which is 1-based breadth-first ordering, btw.) to the 0-based depth-first ordering. In the same go we build the inverse lookup DFSToIndex. If everything were 1-based, then one could use simple arrays; but you want 0-basedness, so we need to use Association as data structure).

counter = 0;
IndexToDFS = Association[];
DFSToIndex = Association[];
child[dfs_, k_] := 
  IndexToDFS[VertexOutComponent[T, DFSToIndex[dfs], 1][[k + 2]]];


DepthFirstScan[T, 1,
  {"PrevisitVertex" -> ((
       AssociateTo[IndexToDFS, # -> counter];
       AssociateTo[DFSToIndex, counter -> #];
       ++counter
       ) &)
   }];

Graph[T,
 DirectedEdges -> True,
 VertexLabels -> Normal@IndexToDFS,
 VertexSize -> .2,
 GraphLayout -> {"LayeredEmbedding", LayerSizeFunction -> (4 &)}
 ]

enter image description here

Now children can be "computed" with the following method:

child[dfs_, k_] := IndexToDFS[VertexOutComponent[T, DFSToIndex[dfs], 1][[k + 2]]];

For the example given:

{child[10, 0], child[10, 1], child[10, 2]}

{11, 12, 13}

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.