問題タブ [binary-tree]

二分探索木でノード (値 k を持つ) を検索するための基本的な木探索アルゴリズム。「x」は、二分探索木のノードを示します。

反復バージョン:

（反復アルゴリズムの）最初の行は、実際には while (x ≠ NIL OR k ≠ key[x]) ではなく (while x ≠ NIL and k ≠ key[x]) であるべきではありませんか?

ちなみに、これはアルゴリズム分析の有名な本の 1 つからのものです。

以下を末尾再帰バージョンに変換するにはどうすればよいですか。

分岐は 2^n の大きさであるため、単一のアキュムレータを維持することは不可能のようです。

考えられる解決策は、反復ごとにアキュムレータに新しいアキュムレータをリストに追加させることです。多分上記の解決策は最適ですか？

前もって感謝します。

2 つのバイナリ ツリーの順序と順序が同じである場合、それらが同一であることを証明する方法を知っている人はいますか? (おそらく、同じ inorder トラバーサルと preorder トラバーサルを持つ 2 つの異なるバイナリ ツリーを持つことはできないことを示すことによって)

あるいは、これを反証する事例を示してください。または、なぜそれができないのかを示してください。

(認めますが、これは純粋に学術的なものですが、宿題などではありません。私の本能はそれが真実であると教えてくれますが、グラフで証明したことはないと思います。)

ハッシュ関数が適切に選択されていれば、ハッシュテーブルの挿入と検索の両方に O(1) の時間がかかることは誰もが知っています。では、二分探索木を使用する理由は何でしょうか? 完全なハッシュ関数を設計するのが難しかったという理由だけでしょうか?

ここで、どうやってこの質問を思い付くのですか？標準C++ STL にはとsetがmapあり、バイナリ検索ツリーで実装されていますが、ハッシュはありません (非標準の , については話していませんhash_set) hash_map。一方、Ruby にはHash. この違いの背後にある合理性を理解したいと思います。

私は自分の割り当てにavlツリーを実装しています。

問題は、avl_swr（）を使用してツリーを回転させると、print_avl（）に従って正常に回転しますが、関数が呼び出し元に戻ると、ツリーが破損することです。何か案は？

私が現在取り組んでいるシステムには、二分決定木の作成が含まれます。それらの多くは。それらの一部は XML 形式で保存されるため、必要に応じて手動で分析できます。

ツリー構造は、基本的にネストされた <NODE> タグです。各ノードには、ノードのプロパティを定義する子タグがいくつかある場合もあります。

私がやりたいのは、ツリーをグラフィカルに表示することです。垂直または水平は関係ありませんが、次のように幾何学的にツリー型のレイアウトを使用したいと思います。

...ファイル システム ブラウザで一般的に使用されるレイアウトではなく、バイナリ ツリーを表示する最良の方法ではありません。

.NET ベースのライブラリ、またはこれをうまく行うスタンドアロン ツールはありますか?

独立したノードとは、返されるセットに直接関係のあるノードを含めることはできず、親と子の両方を含めることはできないことを意味します。Googleを使おうとしましたが、うまくいきませんでした。私は正しい検索語を持っていないと思います。

リンク、どんな助けでも大歓迎です。今これを始めたばかりです。

量だけでなく、実際の独立ノードのセットを返す必要があります。

二分探索木タイプのデータ構造の場合、Big O表記は通常O（logn）と表記されます。ログに小文字の「l」がある場合、これは自然対数で表される対数基数e（n）を意味しますか？簡単な質問で申し訳ありませんが、私は常に異なる暗黙の対数を区別するのに苦労していました。

このような文字列に基づいて、バイナリ ツリーを整数で埋めるとします。

LT は、ツリーの左側の部分と同じ形式の式です。RTも同様。有効な文字列は次のようになります: 4(2(1)(3))(6(5)(7). どうすればこの木を埋めることができますか? これは、いかなる種類のソートされたツリーでもありません。したがって、すべての「レベル」をノードで埋めることができます。ご協力ありがとう御座います。

いらっしゃいませ！ツリーノード（実際には検索ツリーではなく、元のバイナリツリー）を受け取るlessという名前の再帰的なパブリック静的メソッドと、ツリー内のすべての値が整数未満の場合に返されるintパラメーターがあります。したがって、私はSoを使用しますpublic class TN { public int value; public TN left, right; public TN(int v, TN l, TN r) {value = v; left = l; right = r;} } 。私のメソッドは、次のようになります。

私はそれが正しいのか、それとも何かが足りないのか疑問に思いましたか？trueとfalseを返す必要がありますか？