Search code examples
data-structurescomputer-sciencetriebitvector

How to get parent in a k-ary level order succint trie?

I'm implementing a level order succint trie and I wan't to be able for a given node to jump back to his parent.

I tried several combination of rank/level but I can't wrap my head around this one...

I'm using this article as a base documentation : http://stevehanov.ca/blog/index.php?id=120

It explain how to traverse childs, but not how to go up.

Thanks to this MIT lecture (http://www.youtube.com/watch?v=1MVVvNRMXoU) I know this is possible (in constant time as stated at 15:50), but the speaker only explain it for binary trie (eg: using the formula select1(floor(i/2)) ).

How can I do that on a k-ary trie?

Solution

  • I think I've found my answer. This paper of Guy Jacobson explains it in section 3.2 Level-order unary degree sequence.

    parent(x){ select1(rank0(x)) }

    Space-efficient Static Trees and Graphs http://www.cs.cmu.edu/afs/cs/project/aladdin/wwwlocal/compression/00063533.pdf

    This work pretty good, as long as you don't mess up your node numbering like I was.