問題タブ [binary-tree]

馬の系図データを再帰的にロードしています。いくつかの間違ったデータセットでは、再帰が止まらない...そしてそれはデータにサイクルがあるためです。

これらのサイクルを検出して再発を止めるにはどうすればよいですか?

私は、すべての「訪問した」馬でハッシュテーブルを定期的に維持することを考えました。しかし、馬は木に2回いる可能性があるため、いくつかの誤検知が見つかります.

あり得ないことは、馬が ITSELF の父または祖父または曽祖父として現れることです。

パフォーマンスが白黒になることは決してないことを私は知っています。多くの場合、1つの実装はXの場合は速く、Yの場合は遅くなりますが、一般的には、BツリーはAVLやRedBlackツリーよりも高速ですか？それらはAVLツリー（そしておそらくRedBlackツリーでさえも）よりも実装がかなり複雑ですが、より高速です（それらの複雑さは報われますか？）

編集：私はまた、それらが同等のAVL / RedBlackツリー（ノード/コンテンツの観点から）よりも速い場合、なぜそれらが速いのかを追加したいと思います。

二分木を考えてみましょう:

1. nが整数の場合、 nはノードです
2. aとbがノードの場合、 (+ a b ) はノードです。

次の 3 つの操作があります。

1. (+ a b ) -> (+ b a )
2. (+ (+ a b ) c ) -> (+ a (+ b c ))
3. (+ a (+ b c )) -> (+ (+ a b ) c ) -- (2.逆)

これらの操作を使用して、特定のツリーの可能な順列をすべて与えるアルゴリズムが必要です。任意の操作を任意のサブツリーに適用できます。順列とは、まったく同じ葉のセットを持つすべての木を意味します。そんなに難しいことではないのかもしれませんが、私には理解できないようです。

[編集] リーフは名前 (つまり変数) にすることもできるため、整数としてのプロパティに依存することはオプションではありません。木は合計を表します。

[編集 2] この演習のポイントは、フォームAおよび-Aの項を見つけて合計を減らし、それらを削除するためにツリーをサブツリー (+ A -A ) に取得することです。上記の 3 つの操作は私のシステムの公理であり、最後まで使用する必要があります。そうしないと、削減されたツリーが元のツリーと等しいことを証明できません。私はTwelfロジック プログラミング言語を使用しているので、最初に要求したことを実行するアルゴリズムを理解できれば、残りは簡単に実行できますが、別の解決策ももちろん歓迎します。

間隔（または範囲）のリストがあるとしましょう（例：10-15、5-7、9-12 ..）。問題は、重複する範囲のサブセットを見つけることです。もちろん、これにはインターバルツリーを使用できます。

私が抱えている実際の問題は、複数の範囲があることです。例によって最もよく説明されています：

1. 10-15、5-7、9-12
2. 1-2、3-6、14-15
3. 3-5、9-15、10-15

上記の場合、第 2 範囲では (1) と (2) が重複し、第 3 範囲では (3) と (1)、(2) が重複しています。

基本的に、アイテムのリスト間の重複をすべて見つける必要があります。

たぶん、これを見つけるために 3 つの別々のインターバル ツリーを使用できます。これを行うより良い方法はありますか？

これは今より重要なので、以前のCの質問を保留にする必要があります...

二分探索ツリーで挿入関数と削除関数を既にコーディングしましたが、削除関数は不完全です。助けが必要なことがいくつかあります...

1)私の挿入機能は良いですか、それとも何とか改善できますか?

2)私の削除機能には、左右の子を持つノードの削除がありません。過去数時間でたくさん検索しましたが、適切な方法が見つかりませんでした。

2.a) 2 つの子ノードを持つノードを削除するにはどうすればよいですか?

2.b)最初の質問と同様に、削除機能は適切ですか、それとも改善できますか? これらのifで多くのコードを繰り返しているので、これができることはわかっていますが、どうすれば改善できるかわかりません。それについても助けが必要です。

お気づきかもしれませんが、2点だけ指摘させてください。

• このツリーは、通常の int 表現の代わりに文字列を使用します。それが私が strcmp() をずっと使っている理由です。私はそれを正しく使っていると思います。
• 私は再帰を使用していません。むしろ、(この場合は構造体ポインターの) ポインターを渡し、それを操作します。どういうわけかよりきれいに見えます。将来的には、ノードが削除された場合に成功値を返したいと考えています。

以下の更新：
私はすでに削除機能の反復バージョンを実行しましたが、それについていくつか気に入らないことがあります。おそらく改善できる（または改善できない）可能性がありますが、方法がわかりません。また、欠落しているケースをコーディングして、2 つの子を持つノードを削除しようとしましたが、正常に機能していません...

私は、コードを改善できると思う場所と問題の場所をコード全体にコメントしました。また、簡単に参照できるように、これらの問題を A、B (B はもうありません)、C、D と名付けました。

二分木の可能なすべての順列を生成するためのアルゴリズムを見つける必要があり、リストを使用せずにそれを行う必要があります（これは、ツリー自体がリストに変換できないセマンティクスと制約を持っているためです）。高さが3以下の木で機能するアルゴリズムを見つけましたが、高さが高くなると、追加された高さごとに1セットの可能な順列が失われます。

各ノードは元の状態に関する情報を保持しているため、1つのノードは、そのノードに対してすべての可能な順列が試行されたかどうかを判断できます。また、ノードは天気に関する情報を保持しているか、「スワップ」されているかどうか、つまり、サブツリーのすべての可能な順列を確認したかどうかを確認します。ツリーは左中央にあります。つまり、右側のノードは常にリーフノードである必要がありますが（このアルゴリズムでカバーする必要がない場合を除く）、左側のノードは常にリーフまたはブランチのいずれかです。

私が現在使用しているアルゴリズムは、次のように説明できます。

アルゴリズムの望ましい動作は次のようになります。

等々...

整数、左と右のポインターを持つバイナリ ツリーが与えられた場合、O(n) 時間と O(1) 余分なメモリ (スタック/キュー/再帰なし) でツリーをトラバースするにはどうすればよいでしょうか?

この男は、現在のパスを整数としてエンコードした O(n) 合計時間ではないソリューションを提供しました (したがって、限られた深さのツリーで機能します)。

私は古典的な解決策を探しています

（ネタバレ）

子の各ノードの親をエンコードしました。