3

同じデータを含み、ノードAが祖先としてノードBまたはBがの兄弟であるようにツリー上に配置されているノードのカップル（A、B）を識別するための高速アルゴリズムを見つけようとしています。 Aの祖先。

たとえば、次のツリーを見てください。このツリーでは、色がコンテンツを識別しています。

サンプルツリー

  • n6n1n1の祖先と同じように一致n6します。
  • n5とn3は、の祖先であるn3の兄弟と同じように一致します。n2n5
  • n3とn7同じ理由で一致します。
  • n5n7n7の祖先でも、の祖先のn51つの兄弟でもないため、一致しませんn5。
  • n2n4同じ理由で一致しません。

「ルールチェッカー」のナイーブな実装は簡単ですが、ツリーを複数回トラバースする必要があります（チェックされるノードごとに1回）。ただし、ツリーの2つの特別なプロパティを活用して、より良いソリューションを実装できると感じています。 。問題の2つのプロパティは次のとおりです。

  • 同じコンテンツを持つすべてのノードのフラットリストを取得できます（上記の例では、、、、を取得(n5, n3, n7)し(n1, n6)ます(n2, n4)。
  • 私の各ノードは、その親とそのすべての子の両方への参照を格納します（このプロパティは、リンクリストのように再帰的に利用できます）。

...しかし、一致するノードをすばやく見つける方法が必要であると確信しているにもかかわらず、これまでのところ、それを見つけることができませんでした。

私は現在Pythonで作業していますが、擬似コードや他の難解ではない言語の例も歓迎されます。

4

1 に答える 1

2

これが解決策だと思います。このソリューションでは、dfs-visiting-timeコストO（n）を事前に計算した後、O（1）を使用して各クエリに回答します。

dfsは次のようになります。

nowtime=0
def dfs(node):
    global nowtime
    nowtime+=1
    node.come_time=nowtime
    for i in node.sons:
        dfs(i)
    nowtime+=1
    node.leave_time=nowtime
dfs(root)

次に、次のようになります。

BはAの祖先であり、

B.come_time<A.come_timeおよびB.leave_time>A.leave_time

私はそれが本当だと思います：

AがBの直接の父親の子孫である場合に限り、 AはBの兄弟の子孫です。そして（@macのおかげで）AはBの兄弟の1人ではありません。また、AはBの子孫ではありません。

確認できます：

B.fa.come_time<A.come_timeおよびB.fa.leave_time>A.leave_time

と

B.fa！= A.fa

要約すると、私たちが持っている質問に答えるために：

def check(A,B):
    if B.come_time<A.come_time and B.leave_time>A.leave_time:
        return True
    if B.has_father() and A.has_father():
        if A.fa==B.fa:
            return False
        if B.fa.come_time<A.come_time and B.fa.leave_time>A.leave_time:
            return True
    return False

このソリューションの重要なアイデアは、dfs（）の訪問時間を使用して、ノードBが別のノードAの祖先であるかどうかを確認することです。[come_time、leave_time]間隔は、ノードがスタックに保持される正確な時間間隔です。dfsプロシージャでは、dfs（）が子孫を訪問している間は常にスタックにあるため、祖先の訪問時間間隔にすべての子孫の時間間隔が含まれることを確認するのは簡単です。

追加した：

私たちはそれを証明することができます：

AがBの直接の父親の子孫である場合に限り、 AはBの兄弟の子孫です。そして（@macのおかげで）AはBの兄弟の1人ではありません。また、AはBの子孫ではありません。

以来：

AがBの直接の父親の子孫である場合、AはB.faをルートとするサブツリーにあります。サブツリーには次のもののみが含まれます。

  1. B.fa
  2. B
  3. Bの兄弟
  4. Bの子孫
  5. Bの兄弟の子孫

したがって、Aが1ではなく、2ではなく、3ではなく、4ではない場合、Aは5である必要があります。

また、AがBの直接の父親の子孫でない場合、Aはサブツリーに含まれていません。Bのすべての兄弟がサブツリーにあるため、AがBの兄弟の子孫になることは決してないことは明らかです。

于 2012-08-17T02:49:40.497 に答える