11

次の木を想像してみてください。

    A
   / \
  B   C
 / \   \
D   E   F

たとえば、FがAの子孫であるかどうかを照会する方法を探しています（注：FはAの直接の子孫である必要はありません）。これは、この特定の場合に当てはまります。より大きな潜在的な子孫ノードプールに対してテストする必要があるのは、限られた量の潜在的な親ノードのみです。

ノードが潜在的な親プール内のノードの子孫であるかどうかをテストする場合、すべての潜在的な親ノードに対してテストする必要があります。

これが思いついたものです：

  • マルチウェイツリーをトライに変換します。つまり、上記のツリーのすべてのノードに次のプレフィックスを割り当てます。

     A = 1
 B = 11
 C = 12
 D = 111
 E = 112
 F = 121

  • 次に、可能なすべてのプレフィックスサイズのビット配列を予約し、テスト対象の親ノードを追加します。つまり、Cが潜在的な親ノードプールに追加されている場合は、次のようにします。

      1    2    3  <- Prefix length

*[1]  [1]  ...
 [2] *[2]  ...
 [3]  [3]  ...
 [4]  [4]  ...
 ...  ...

  • ノードが潜在的な親ノードの子孫であるかどうかをテストするときは、そのtrieプレフィックスを取得し、最初の「プレフィックス配列」（上記を参照）の最初の文字を検索し、存在する場合は、2番目の「プレフィックス」の2番目のプレフィックス文字を検索します配列」など、つまりFをテストすると次のようになります。

     F = 1    2    1

   *[1]  [1]  ...
    [2] *[2]  ...
    [3]  [3]  ...
    [4]  [4]  ...
    ...  ...

    そうです、FはCの子孫です。

このテストは最悪の場合のO（n）のようです。ここで、n =最大プレフィックス長=最大ツリーの深さです。したがって、最悪のケースは、ツリーを上ってノードを比較するという明白な方法とまったく同じです。ただし、テスト対象のノードがツリーの最下部近くにあり、潜在的な親ノードが最上部にある場合、これははるかに優れたパフォーマンスを発揮します。両方のアルゴリズムを組み合わせると、両方の最悪のシナリオが緩和されます。ただし、メモリのオーバーヘッドが問題になります。

それを行う別の方法はありますか？どんなポインタでも大歓迎です！

4

8 に答える 8

8

入力ツリーは常に静的ですか? その場合、Lowest Common Ancestor アルゴリズムを使用して、O(n) 時間/空間構造を使用して O(1) 時間で子孫の質問に答えることができます。LCA クエリには 2 つのノードが与えられ、サブツリーに両方のノードが含まれるツリーの最下位ノードはどれかを尋ねられます。次に、1 つの LCA クエリで IsDescendent クエリに答えることができます。LCA(A, B) == A または LCA(A, B) == B の場合、一方が他方の子孫です。

このTopcoder アルゴリズムのチュートリアルでは、問題の詳細な説明と、コードの複雑さ/効率のさまざまなレベルでのいくつかの解決策を示します。

于 2011-05-16T17:51:51.780 に答える
4

これがあなたの問題に当てはまるかどうかはわかりませんが、階層をデータベースに保存する方法の 1 つは、「このノード以降のすべてを提供する」機能をすばやく使用して、「パス」を保存することです。

たとえば、次のようなツリーの場合:

    +-- b
    |
a --+       +-- d
    |       |
    +-- c --+
            |
            +-- e

上記のツリーの文字が各行の「id」であると仮定すると、次のように行を保存します。

id    path
a     a
b     a*b
c     a*c
d     a*c*d
e     a*c*e

特定のノードのすべての子孫を見つけるには、パス列で「STARTSWITH」クエリを実行します。で始まるパスを持つすべてのノードa*c*

特定のノードが別のノードの子孫であるかどうかを確認するには、最長パスが最短パスで始まっているかどうかを確認します。

たとえば、次のようになります。

  • a*c*eで始まるため、e は a の子孫ですa
  • a*c*dで始まるため、d は c の子孫です。a*c

それはあなたのインスタンスで役に立ちますか？

于 2011-05-16T16:34:48.490 に答える
3

ツリーをトラバースするには、「ツリーの深さ」の手順が必要になります。したがって、バランスの取れたツリー構造を維持する場合、ルックアップ操作にO(log n)操作が必要になることが証明されます。私が理解していることから、あなたの木は特別に見え、バランスの取れた方法で維持することはできませんよね? したがって、O(n)が可能になります。しかし、これはとにかくツリーの作成中に悪いので、とにかくルックアップを使用する前におそらく死ぬでしょう...

insertと比較してそのルックアップ操作が必要になる頻度に応じて、追加のデータ構造を維持するために挿入中に支払うことを決定できます。償却されたO(1)が本当に必要な場合は、ハッシュをお勧めします。すべての挿入操作で、ノードのすべての親をハッシュテーブルに入れます。あなたの説明によれば、これは特定の挿入のO(n)個のアイテムである可能性があります。nを挿入しないと( O(n^2)に向かって) 悪いように聞こえますが、実際にはツリーはそれほど劣化しないため、償却された全体的な hastable サイズはO(n log n)になります。 . (実際には、log nの部分はツリーの劣化度に依存します。最大の劣化が予想される場合は、それを行わないでください。)

したがって、すべてのinsertに対して約O(log n)を支払い、 lookupに対してハッシュテーブル効率O(1)を取得します。

于 2011-05-16T16:48:15.777 に答える
2

M-way ツリーの場合、ビット配列の代わりに、バイナリの「トライ ID」(レベルごとに M ビットを使用)を各ノードに格納しないのはなぜですか? あなたの例（M == 2と仮定）： A=0b01, B=0b0101, C=0b1001, ...

次に、O(1) でテストを実行できます。

bool IsParent(node* child, node* parent)
{ 
   return ((child->id & parent->id) == parent->id)
}

最上位ビット セットの位置を返す高速な FindMSB()関数がある場合、レベルごとにストレージを ceil(lg2(M)) ビットに圧縮できます。

mask = (1<<( FindMSB(parent->id)+1) ) -1;
retunr (child->id&mask == parent->id);
于 2011-05-16T16:38:53.813 に答える
1

プレオーダー トラバーサルでは、子孫のすべてのセットが連続しています。あなたの例では、

A B D E C F
+---------+ A
  +---+ B
    + D
      + E
        +-+ C
          + F

前処理できる場合は、各ノードに番号を付けて子孫間隔を計算するだけです。

前処理できない場合、リンク/カット ツリーは、更新とクエリの両方で O(log n) のパフォーマンスを提供します。

于 2011-05-16T17:11:09.850 に答える
0

「ノード A はノード B の子孫ですか?」という形式のクエリに答えることができます。2つの補助配列を使用するだけで、一定時間で。

深さ優先の順序で訪問することによってツリーを前処理し、ノード A ごとに開始時刻と終了時刻を 2 つの配列 Start[] と End[] に格納します。

したがって、End[u] と Start[u] はそれぞれ、ノード u の訪問の終了時刻と開始時刻であるとしましょう。

次に、次の場合に限り、ノード u はノード v の子孫です。

開始[v] <= 開始[u] および終了[u] <= 終了[v]。

これで完了です。この条件をチェックするには、配列 Start と End で 2 つのルックアップが必要です。

于 2012-11-24T15:49:32.253 に答える
0

価値があるのは、ここで求めていることは、クラスがクラス階層内の別のクラスのサブタイプであるかどうかをテストすることと同等であり、CPython のような実装では、これは古き良き方法で行われるだけです。親の方法。

于 2021-08-10T17:15:17.637 に答える