私はレベル順序の簡潔なトライを実装していますが、特定のノードが親に戻ることができないようにしたいと考えています。
ランク/レベルの組み合わせをいくつか試しましたが、これについて頭を悩ませることはできません...
この記事を基本ドキュメントとして使用しています: http://stevehanov.ca/blog/index.php?id=120
チャイルドをトラバースする方法は説明していますが、上に行く方法は説明していません。
この MIT の講義 ( http://www.youtube.com/watch?v=1MVVvNRMXoU )のおかげで、これが可能であることはわかっています (15:50 に述べられているように一定時間で) が、スピーカーはバイナリ トライについてのみ説明します (例: : 式 select1(floor(i/2)) を使用)。
どうすればk-aryトライでそれを行うことができますか?
さて、私は何select1()であるかわかりませんが、他の部分（ ）は、ここでfloor(i/2)説明されているような、配列が埋め込まれたバイナリツリーで使用するトリックのように見えます。すべての親には正確に2つの子があるため、2で除算します->すべてのレベルは親レベルの2倍のスペースを使用します。
すべてのノードに同じ数の子がない場合（リーフと、子が少ない1つのノードを除く）、このトリックを使用することはできません。
特定のノードの親を知りたい場合は、すべてのノードの親へのポインターを追加する必要があります。
ただし、ツリーは通常、ルートから下に向かってトラバースされるため、通常は、パスのノードへのポインターを配列に格納します。任意の時点で、現在のノードの親は配列内の前の要素です。このように、すべてのノードで親へのポインターを追加する必要はありません。
私は自分の答えを見つけたと思います。Guy Jacobson のこの論文では、セクション 3.2 レベル順序単項次数シーケンスで説明しています。
親(x){ select1(rank0(x)) }
スペース効率の良い静的ツリーとグラフ http://www.cs.cmu.edu/afs/cs/project/aladdin/wwwlocal/compression/00063533.pdf
私のようにノードの番号付けを台無しにしない限り、これはかなりうまく機能します。