効率的に（M-ウェイ）ツリーTを与えられたツリーノード

Question

の深いマーク子供たちを見つける：

 A 
    /\ 
     B C 
    /\ \ 
    D* E* F 
/\ \ \ 
    G H* I J* 

マークされたノードDの*、E * H *およびJ *を使用すると、取得するための高速な方法がありますすべて指定されたノードの下にマークされた子、すべてのサブツリーを歩いたり、マークされたすべての子をすべてのノードに格納することは別ですか？私は：

B -> D*, E*, H* 
C -> J* 
A -> D*, E*, H*, J* 

Answer 1

原則として、ツリーを歩いてマークされた値のリストを保存することとの間にトレードオフがあります。あなたは2つの極端なことを言いました、私はそれらの中間のどこかに座っている例をあなたに与えます。頭に浮かぶ

ひとつのアイデアはあなたの例では、それはあまり保存しないように、ストレージと時間のかなりバランスの取れたミックスを与える必要があり、各マークされたノード、でマークされ子供たちの次の「層」を記憶するが、ためていますたとえば、あなたが

 A 
    /\ 
     B* C 
    /\ \ 
    D* E F 
/\ \ \ 
    G H* I* J* 
//\ 
K L M 

を持っている場合は、H,I,JにDと「空」のマーカーでBでD,IとHを格納します。あなただけのすべてのブランチがマークされたノードに当たるまで、例えば、Aためのリストを取得するために、あなたはA->BとA->C->F->Jから歩いてしなければならないので、その後Bはあなたを与えるだろう、歩かなければならないノードのためのリストを取得するには

I,D、DはHとなります。あなたがこの場合も、元のツリーとだけ一緒にマークされたノードの木を記憶するものとして考えることができ

、2本の木

B  J 
/\ 
D I 
| 
H 

マークされたノードの分布に応じて、あなたがすることができるかもしれませんこのアイデアをアプリケーションに最適化します。

Answer 2

まあ、少なくとも1回は木を歩かなければなりません。それより速い方法はありません。あなたはそれらを保管したくないので、毎回それらを歩かなければならないでしょう。

Answer 3

下に移動すると、ツリーのかなり小さな部分にアクセスできます。

木はという最小限のスペースで表現できます。すなわち、構造体のベクトル、「親ノード」インデックスと「マーク済みフラグ」以外のフルペイロード（ルートは-1）です。

for each node 
    if marked && given parent in parents'chain 
    ok, save (for instance) the index 
    endif 
next 

IMO、およびデータ配信統計に応じて、私はこれが効率的であると感じます。

Answer 4

現在のノードをルートとするサブツリーにマークされたノードがある場合に限り、すべてのノードに1ビット（またはboolean）を格納できます（true）。このラベル付けは、ツリーを更新しながら維持するのが容易で、再帰アルゴリズムと反復アルゴリズムの両方で簡単に不要なサブツリーをスキップできます。ただし、マークされたノードへのパス上のすべてのノードをトラバースする必要があります。

アクセスのためのオーバーヘッドを確保するが、維持することは難しいもう一つのアイデアは、マークされたすべてのノードに子ポインタの第2のペアを持たせることです。これらを使用すると、マークされたノードのツリーを小さなストレージオーバーヘッドで保存できます。この方法でマーキング自体をエンコードすることもできます。それらのポインタのうち少なくとも1つがnullでない場合にのみ、ノードがマークされます。根は特別な方法で扱われなければならない。