問題タブ [subtree]

次の（奇妙な）方法で二分探索木を作成する必要があります。

配列 (A[n]) が与えられます。A[1] がツリーのルートになります。

• 次に、ルートの左側のサブツリー (subtree1、以下で使用) に A[1]+A[2] を挿入し、ルートの右側のサブツリー (subtree2) に A[1]-A[2] を挿入します。

• A[1]+A[2]+A[3] を subtree1 (subtree3) の左側のサブツリーに挿入し、A[1]+A[2]-A[3] を subtree1 (subtree4) の右側のサブツリーに挿入します。

• 次に、A[1]-A[2]+A[3] を subtree2 の左側のサブツリー (subtree5) に挿入し、A[1]-A[2]-A[3] を subtree2 の右側のサブツリー (subtree6) に挿入します。 ）。

• 配列の最後に到達するまで、subtree3、subtree4、subtree5、subtree6 について繰り返します。

したがって、基本的に、配列の最初の要素がツリーのルートになり、次に下に移動します。すべての左側のサブツリーには、その親と配列の次の要素の合計が値として含まれ、すべての右側のサブツリーには、次の値の差がありますその親および配列内の次の要素の。

再帰の概念を使用する必要があることは理解していますが、変更された方法で使用します。ここに私の問題を入力して、私の脳以外の誰かに説明しようとすると、実際に試してみるべきいくつかのアイデアが得られるような方法でそれを形成しましたが、私が扱っている問題は通常の問題であることがわかります。再帰を使用してツリーを構築する方法について、いくつかのヒントを教えてください。

他の質問や議論を見回してみると、全体的な解決策を求めることに対するポリシーがあることがわかっているので、解決策を求めているのではなく、それへのガイダンスを求めていることを明確にしたいと思いました. 誰かが見たいと思ったら、私がすでに行ったことをあなたに見せることができます.

私のプロジェクトには、サブツリー戦略によってマージされたライブラリ プロジェクトを含む 3 つのサブディレクトリがあります。masterブランチをチェックアウトし、メイン プロジェクトとライブラリ ファイルに変更を加えたとします。ローカルの変更が失われるため、lib ブランチをチェックアウトできません。あるブランチでstashを実行し、それを別のブランチに適用することはお勧めできません。

標準のgitツールのみを使用して（git-subtreeパッケージなしで）変更を分割し、適切なブランチにコミットする方法???

現在、私は前学期のプロジェクト/論文を作成しており、「Web で Web ページの変更を検出する」ことを考えていました。このトピックに関する 2 つの論文を読みましたが、いくつかの混乱があります

1.と題する論文で

モバイル Web ページのトランスコーディングを高速化するためのアプリケーションを備えた、強化された Web ページ変更検出アルゴリズム1

それは書かれている

最初に、HTML ドキュメントからサブツリーを生成します。各サブツリーには、タグの内容に従ってマークが付けられます。

私の質問は、HTML ドキュメントからサブツリーを生成する方法です?? そのためのテクニックとは。次の質問は、「タグの内容に応じてマークを付ける」ことで何を言っているのかです。

2.こちらの画像をご覧ください!! 提案手法の全体図

「最も類似したサブツリーを計算する」ボックスで、マッチングはどのように行われますか?? と題された別の論文で

最適化されたハンガリー語アルゴリズムに基づく効率的な Web ページ変更検出システム [2]

ハンガリー語のアルゴリズムがマッチングに使用されます。行は論文から引用されています

ハッシングと類似度計算の数の削減に基づく、高速な HTML Web ページ変更検出アプローチ [3]

[2] のアプローチは、O(N ³ ) ハンガリアン アルゴリズムを使用して、重み付き 2 部グラフで最大の重み付きマッチングを計算し、O(N ₂ x N ₁ ³ ) の実行時間を持ちます。ここで、N ₁と N ₂は、それぞれ、古いページと新しい (変更された) ページのノード数です。」私の質問は、サブツリーが形成されているため、重みが追加される理由と、それらがどのように追加されるかです。

私の質問/混乱を読んでくれてありがとう.

まず第一に、私はそれがどのように行われるべきかを理解したと思いますが、私のコードは私が試した方法でコンパイルされません。私は、空のptreeトリックのこの公式の例に基づいて仮定しました。そこに次の行があります：

これは、ptreeからsubptreeを取得することが可能である（または可能である必要がある）ことを示しています。

BOOST_FOREACHしたがって、次のような方法でptreeを反復処理できると想定しました。

しかし、次のエラーが発生します。

エラー1エラーC2440：'初期化中'：'std :: pair <_Ty1、_Ty2>'から'const boost :: property_tree :: ptree＆'に変換できません

または私がしようとすると

私は得る：

エラー1エラーC2039：'empty_ptree'：は'boost::property_tree'のメンバーではありません

では、どうすればよいでしょうか。BoostPtreeを反復処理して、サブPtreeを取得する方法を教えてください。

更新： 私もそのようなコードを試しました

これはコンパイルされ、例外をスローしませんが、何も出力しませんSub data。このサイクルを維持するだけです。

アップデート2：

うーん...おそらく私のxmlで何かがうまくいかなかった-今私はそのコードで正しい結果を得る。

サブツリーのマージ戦略を使用する場合、git はどのようにサブツリーを見つけますか? ここに 1 つだけ言及があります。「マージするサブツリーを実際に推測します。通常、これは魔法のように正しいことが判明しますが、サブツリーに多くの変更が含まれている (または元々空だったなど) 場合は、見事に失敗する可能性があります。」失敗した場合、どのように推測し、何ができますか? その回答が書かれた 2009 年 8 月以降、何か変更はありますか?

networkXには、DiGraph（）というツリーがあります。

ツリーのノード2を取る場合。
2のサブツリーを取得するにはどうすればよいですか？

編集

私はこのサブツリーを期待していました

次のことを試みているときに問題が発生します：（1）元のツリーのルートの左側のサブツリーで最大の情報フィールドを見つける（2）ルートの右側のサブツリーで最小の情報フィールドを見つける元の木。

コードはコンパイルされますが、実行時にエラーが発生し、maxleftsubtree（）関数とminrightsubtree（）関数で何が起こっているのかわかりません。任意の提案をいただければ幸いです。

私の現在のコード：

同じサブツリーの複数の子孫ノードを (潜在的に) 返すクエリからサブツリー (PostgreSQL ltree) のルート ノードを選択する簡単な方法はありますか? このタスクを達成するためにかなり冗長なアルゴリズムを実装しました (インデントおよびフォーマットされた最大 40 行) が、ltree データが実際にはツリーであり、簡単にアクセスできるルート ノードがあるという事実を活用できれば素晴らしいことです。単一のクエリから複数の別個のサブツリー ルートが返される可能性があることに注意することが重要です。そのため、単純にデータを並べ替えて上位の結果を取得することはできません。

2012 年 6 月 7 日: クエリを最新バージョンに更新しました。これにより、時間の複雑さが半分になりました。サブツリーに先祖を持つすべてのノードをサブツリーから削除するために、（必要に応じて）自己アンチ結合を使用します。

基本的に、私のアルゴリズムは次のように機能します。

(詳細については、私の要旨を参照してください: https://gist.github.com/1507368 )

git-subtreeを使用して、ライブラリ リポジトリをより大きなプロジェクトにマージする方法をテストしています。原則として素晴らしいようです。「git subtree pull」を実行すると、次のようなマージ競合が発生することがあります。

これは、ライブラリ リポジトリで行われた変更のためのもので、ローカルで変更されていないファイルにマージされます。または別の例として、ローカル プロジェクト リポジトリに行を追加しましたが、マージされるサブツリーの一部であるファイルに次の行を追加しました。

git がこれらをマージの競合として報告するのに、競合として報告された領域が空であるのはなぜですか? それを防ぐ方法はありますか？

これらは簡単に解決できますが、git-subtree ワークフローを台無しにします

最近、プロジェクトで git サブツリーを多用しました。すべて本当にうまく動作します。顧客のためにこの種のプロジェクトが必要なときはいつでも、このプロジェクトが何度も再利用されることがわかりました。「フレームワーク」のようなものをイメージできます。

そのため、Visual Studio では、スケルトン パーツを簡単に再利用するための「ソリューション テンプレート」を作成し、必要な場合にのみ適応させます。

しかし、このスケルトンは一連のサブツリー (それぞれがそれ自体のプロジェクト) で構築されているため、git サブツリー参照を再作成するメカニズムが必要です。スケルトンを (ソリューション テンプレートまたはリポジトリのクローンを介して) 使用するすべての開発者が、それらを再作成するために参照について知る必要はありません。

では、このワークフローを実現する (ベスト プラクティス?) 方法はありますか? 前もって感謝します