algorithm - 頂点の数とエッジの数の関係を使用して、不正な形式の可能性のある二分木のループを見つける

Question

私は最近のインタビューでこの質問に直面しました。元の質問は

構造体 (バイナリ ツリーまたは双方向リンク リストのいずれかを指すことができるように構造化されている) へのポインターが与えられた場合、それがバイナリ ツリーまたは DLL のどちらを指しているかを返す関数を記述します。構造体は次のように定義されます。

struct node
    {
     /*data member*/
     node *l1;
     node *l2;
    };

私はすぐに問題に飛び込みましたが、問題にはあいまいさがあることに気付きました。ポインタがそれらのいずれも指していない場合 (つまり、不正な形式の DLL または不正なツリーです)。そのため、インタビュアーは、3 つのケースすべてを返すことができるように関数を作成する必要があると私に言いました。したがって、関数の戻り値は次の形式の列挙型になります

enum StatesOfRoot 
   {
   TREE,
   DLL,
   INVALID_DATA_STRUCTURE,  /* case of malformed dll or malformed tree */
   EITHER_TREE_DLL,         /* case when there is only 1 node */
   };

問題は二分木と DLL のプロパティを確認することになりました。DLL の場合は簡単でした。二分木の場合、私が考えることができる唯一の検証は、ルートからノードへの複数のパスがあってはならないということでした.(またはループがあってはなりません). HashMap を使用するノード (インタビュアーがすぐに拒否した) か、BST を使用して訪問したノードのセットを維持する (std::set を使用したかったのですが、インタビュアーが突然、STL を使用できないという別の制限をポップアップしました)。彼は拒否しました。他のデータ構造を使用することは許可されていないというこの考え。それから私は亀とウサギの問題の修正版を提案しました (バイナリ ツリーの各ブランチを単独のリンク リストと見なす) が、これはうまくいかないと彼は言いました。

問題の核心

それからインタビュアーは彼の解決策を提案しました。彼は、頂点の数とエッジの数を数えることができ、頂点の数=エッジの数+1の関係を主張できると言いました(二分木を保持する必要があるプロパティ) . 私を困惑させたのは、（追加のデータ構造を使用せずに）頂点の数をどのように数えることができるかということでした. 彼は、トラバーサル ( preorder,postorder,inorder ) を実行するだけで実行できると述べました。訪問したノードを追跡していないため、ツリーにループがある場合、どうすれば無限ループを防ぐことができるかを質問しました。彼はこれは可能だと言いましたが、方法は教えてくれませんでした。私は彼のアプローチを真剣に疑っています。彼が提案した解決策が正しかったかどうかについて、誰か洞察を提供できますか? はいの場合、どのようにして個別の頂点の数を明示的に維持しますか? 渡されるのは単なるポインターであり、他の情報はないことに注意してください。

PS: その後、面接官に最終的な解決策を答えることなく、次のラウンドに進むという通知を受け取りました。トリックラウンドのはずだった？

編集：

明確にするために、3番目のケースが存在しないと仮定した場合（つまり、dllまたはバイナリツリーであることが保証されている場合）、問題は非常に簡単です.3番目のケースのツリー部分が私を夢中にさせています. . この点に注意して回答してください。

Answer 1

あなたが彼の解決策に懐疑的であることは正しい.

双方向リンクリストは簡単です。DLL は不変条件を適用します。

1. null ノードを除いて、ノードの左側のノードの右側のノードはそれ自体です。
2. null ノードを除き、ノードの右側のノードの左側のノードはそれ自体です。
3. 非循環 DLL は、左にたどり続けると最終的に null に到達します。
4. 非周期的な DLL は、正しい手順に従っていると最終的に null に到達します。
5. 循環 DLL は、左にたどり続けると、最終的に開始ノードに到達します。

上記は、追加の一時変数と DLL をウォークスルーするだけで簡単に確認できます。

(注: 3 と 4、または 5 のチェックには時間がかかる場合があります。)

二分木は難しいものです。BT は不変条件を適用します。

1. 「No Loops」は、次のいずれかで表示できます。
   • 2 つのノードが同じノードを指しておらず、ルートを指しているノードがないことを示します。
   • ルートからのすべてのパスが最終的にリーフで終わることを示します。
   • 参照されたすべてのノードが異なることを示します。
2. 「マージなし」は、次のいずれかで表示できます。
   • 2 つのノードが同じノードを指していないことを示します。
   • 参照されたすべてのノードが異なることを示します。

あなたが提案したように、これらは、ツリーをトラバースし、訪問した各ノードをマークして、ノードが2回訪問されないようにするか、訪問した各ノードのリストを（ハッシュセットまたは他の構造などに）保存してすばやく調べることによって決定できます。 -up ノードが異なる場合。

コンピューターのメモリよりもツリーが深くなった場合 (またはより多くのノードを訪問した場合)、無限ループが確実に発生します。

ただし、バイナリの「有向非巡回グラフ」(DAG) とバイナリ ツリーを区別するのには役立ちません。

ただし、ツリー内の要素の数がわかっている場合は、これは通常、バイナリ ツリーのライブラリ実装の場合です。インタビュアーが示唆したように、以前に知られているノードの数と比較してエッジの数をカウントすることにより、無限ループを検出できます。

その数を前もって知らなければ、無限に大きな木と大きな有限の木の違いを知ることは困難です。(コンピュータのメモリ サイズや、ツリーの作成にかかった時間などの情報がわかっている場合を除きます)。

これはまだ、「マージなし」不変条件を検出するのに役立ちません。

訪問したノードを外部データ構造に保存するか、訪問したときに各ノードを訪問済みとしてマークすることによって、ノードが2回参照されていないことを示さずに、マージが存在しないことを判断する有用な方法は考えられません。

最後の手段として、次のことができます。

1. コンピューターのメモリと比較したツリーの深さ (または訪問したノードの数) に基づいて、「ループなし」があることを示します。（または以下のように、編集で）
2. この方法で「マージなし」を実証します。
   • ルートの左の子、つまりツリーの深さ 1 から開始します。
   • 深さ 1 と深さ 0 のすべてのノードにアクセスし、直接の親のみが選択したノードを参照していることを確認します。
   • ルートの右の子についても同じことを行います。
   • ツリーのノードごとにこのプロセスを続けます。
     1. ノードを選択し、その直接の親への参照を保持し、
     2. ツリーの上位にあり、選択したノードと同じ深さのすべてのノードにアクセスします。
     3. 訪問したノードのうち、直接の親のみが選択した子を参照していることを確認します。
   • これが完了したら、ツリーを再度トラバースして、すべてのノードの左右のポインターが両方とも同じノードを指していないことを確認します。

このプロセスにはいくつかの追加変数しか必要ありませんが、各ノードをツリー内の上位または同じ深さにあるすべてのノードと個別に比較するため、多くの時間がかかります。

私の直感では、上記の手順は v の順序ではなく、v-squared アルゴリズムになることがわかります。

これにアプローチする別の方法を考えている人がいる場合は、コメントを追加してください。

---

編集：同じ深さ以上のすべてのノードだけでなく、ツリー内のすべてのノードと比較するだけで検索を拡張するだけで、ここで「ループなし」を確認できる場合があります。プログレッシブアルゴリズムでこれを行う必要があります。各ノードをツリー内のその上のすべてのノードとそれ自体の深さと比較し、ツリー内のすべてのノードに対して、それよりも 1 ～ 5 ノード深く、次に 6 ～ 10 世代をチェックする必要があります。低く、など。非プログレッシブな方法でチェックすると、検索が無限に行き詰まる可能性があります。

Answer 2

まず第一に、元の問題は、正しい入力が DLL またはツリーのいずれかであることを明確に示しているため、IMO にはあいまいさはありません。入力が間違っていても、コードがどのように機能するかは問題ではありません。

とにかく、あなたとあなたのインタビュアーは「もしも」の土地に追いやられました。

しかし、「追加のデータ構造を使用しない」とはどういう意味ですか。スタックを使用してターニングポイントを記憶しないと (再帰メカニズムを使用するか、スタックデータ構造を手動で作成することによって)、保証された正しいバイナリツリーでさえトラバースできないためです。

したがって、スタックと再帰を使用できると思います。

ちょっとしたメモ: はい、構造体にツリーの上位へのポインターが含まれている場合は、定数メモリで実行できることはわかっていnodeます (ポインターを変更して、最後に戻すことができます)。これを証明し、これを「自明」と仮定します。少なくとも再帰を使用できる必要があります。

まあ、私は次のことを「単純な順不同のトラバーサル」とは呼びませんが、ここにあります:

#include <stdio.h>
#include <stdbool.h>

struct node
    {
     /*data member*/
     struct node *l1;
     struct node *l2;
    };

// This one counts the nodes in a subtree of V with a depth no more than l that are equal to V0
int CountEqual(struct node* V0, struct node* V, int l)
{
    int thisOneIsEqual = 0;
    if( V == NULL ) {
        return 0;
    }

    if( l == 0 ) {
        return 0;
    }

    if( V0 == V ) {
        thisOneIsEqual = 1;
    }

    return thisOneIsEqual +
        CountEqual(V0, V->l1, l - 1) +
        CountEqual(V0, V->l2, l - 1);
}

// This one checks whether there're equal nodes in a subtree of root with a depth of L
bool Eqs(struct node* root, int L, struct node* V, int l)
{
    if( V == 0 ) {
        return false;
    }

    if( l == 0 ) {
        return false;
    }

    if( CountEqual(V, root, L) > 1 ) {
        return true;
    }

    return
        Eqs(root, L, V->l1, l - 1) ||
        Eqs(root, L, V->l2, l - 1);
}

// This checks whether the depth of the tree rooted at V is no more than l
bool HeightLessThanL(struct node* V, int l)
{
    if( V == 0 ) {
        return true;
    }

    if( l == 0 ) {
        return false;
    }

    return
        HeightLessThanL(V->l1, l - 1) &&
        HeightLessThanL(V->l2, l - 1);
}

bool isTree(struct node* root)
{
    int l = 1;
    while( 1 ) {
        if( HeightLessThanL(root, l - 1) ) {
            return true;
        }

        if( Eqs(root, l, root, l) ) {
            return false;
        }

        l++;
    }
}

// A simple test: build a correct tree, then add cycles, equal nodes etc.
#define SIZE 5
int main()
{
    struct node graph[SIZE];
    int i;

    for( i = 0; i < SIZE; ++i ) {
        graph[i].l1 = 0;
        graph[i].l2 = 0;
        if( 2 * i + 1 < SIZE ) {
            graph[i].l1 = graph + 2 * i + 1;
        }
        if( 2 * i + 2 < SIZE ) {
            graph[i].l2 = graph + 2 * i + 2;
        }
    }

    graph[1].l2 = graph + 3;

    printf( "%d\n", isTree( graph ) );
    return 0;
}

アイデアは、いくつかの L について、高さ L の木があることを知っているか、深さ L のサブツリーに 2 つの等しいノードがあることを知っているということです。

Answer 3

You have to assume some common interfaces to DLL's and trees. An abstract parent might define a virtual toHead() where a DLL would go to a head node, and a tree would go to root and return the node obeject etc. Hash tables are over kill here. My C/C++ is rusty, so the pointers might be a little wrong, however, what you are looking for is that the location in memory is the same as the value of "copyHead" since the value stored in "copyHead" is the location of the head... hope that makes since to you.

type *myType;
myType = &structure;

node *copyHead = myType.toHead(); // Where toHead() returns a pointer to the head.

while( copyHead != &(*myType.next()) ) {
    if(*myType.curr() == null) { return "is tree"}
}

return "is DLL";