問題タブ [binary-search-tree]

BST の定義が与えられ、BST のフォールドの一般化されたバージョンを使用している場合、BST が有効なものであるかどうかを確認するにはどうすればよいですか?

ノード値が左サブツリーのすべての値よりも大きく、右サブツリーのすべての値よりも小さいことを確認するという考え方です。Trueこれは、ツリー内のすべてのノードに対して行う必要があります。関数bstListは、BST の (順序付けられた) 値のリストを単純に出力します。

もちろん、次のようなものは機能しません。

たとえば、fold 関数をノードに適用すると19、all (<19) (bstList True) && all (>19) (bstList True).

二分探索木がどのように実装されているかは理解していますが、ほとんどのプログラミング言語が標準ライブラリに組み込んでいるハッシュテーブルよりも二分探索木を使用する利点が何であるかわかりません。

誰かが二分探索木で解決できる現実の問題の例を提供してもらえますか？

質問に関連する投稿を読んで解決策を考え出すために数時間を費やしましたが、解決策を見つけるのに実際には成功しませんでした。

だからここに行く：私はかつてインタビューで、特定の単語がファイルに存在するかどうかを検索するためにどのデータ構造を使用するかを尋ねられました。また、ファイルはメモリに収まらないほど大きいと思われ、インタビュアーは実際にディスク上のソリューションを探していました。

Bツリーはディスク上のデータ構造ですか？

二分探索木はメモリ内のデータ構造ですよね？

StackOverflowコミュニティの皆さん、こんにちは。

ツリーを構築せずに、プレオーダーまたはポストオーダートラバーサル（大きな違いはないはずです）のみを指定して、BSTの内部パス長を計算する方法を理解しようとしています。つまり、上記のトラバーサルの1つだけを使用したいと思います。これはほとんどの人にとって簡単な答えかもしれませんが、あなたはすでに私が木にかなり慣れていないと思っていたかもしれません。

よく考えていただければ幸いです。

現在、バイナリ検索ツリーを設定しており、テンプレートを使用して、バイナリ検索ツリー内のデータの種類を簡単に変更できます。現在、ツリーに格納されるデータを含むstudentRecordクラスのオーバーロードに問題があります。BSTがコンテンツの1つ（この場合は学生ID）に基づいて2つのオブジェクトを適切に比較できるように、このクラス内の比較演算子をオーバーロードする必要があります。ただし、studentRecord内の演算子がオーバーロードされているにもかかわらず、適切な比較はまだ行われていません。

以下の詳細：

現在、タイプのbstオブジェクトstudentTreeが作成されています

studentRecordは次のクラスです。

新しいアイテムが私のBSTに追加されるときはいつでも、それらを互いに比較する必要があります。したがって、studentRecordクラスをオーバーロードして、この比較プロセスが発生したときに、studentIDが比較されるようにしました（そうでない場合は、無効な比較が行われます）。

ただし、挿入関数がオーバーロードされた比較関数を使用することはありません。代わりに、2つのオブジェクトを別の方法で比較しているようで、BST内で無効な並べ替えが発生します。私の挿入関数の一部を以下に示します。テンプレート処理が行われるため、toInsertとnodePtr->dataの両方がstudentRecord型である必要があることに注意してください。

また、ここにBSTクラス定義の一部があります

これを引き起こしている可能性があるものについてのアイデアはありますか？間違ったクラスまたは間違った関数をオーバーロードしていますか？どんな助けでもありがたいです-非常に多くの異なることが一度に起こっているので、私は道に迷っているようです。

2つのランククエリ[rank(k)とselect(r)]を実装する必要があります。しかし、これを始める前に、2つの機能がどのように機能するかを理解する必要があります。

私の知る限り、指定さrank(k)れたキーのランクを返し、指定されたランクのキーkをselect(r)返しますr。

だから私の質問は：

1.）AVL（自己平衡BST）のノードのランクをどのように計算しますか？

2.）複数のキーが同じランクを持つことは可能ですか？もしそうなら、何が戻っselect(r)てきますか？

質問に答えるのに役立つ場合に参照できるサンプルAVLツリーを含めます。

ありがとう！

どこで間違いをしたのか、なぜそれがwhileループから出てこないのかを追跡することはできません。

二分探索木を使用して文字列のマップのように動作するクラスを実装する必要があります。これは私が実装したクラスです：

正直なところ、関数の実装方法がわかりませんgetNextPair()。
誰かが私を助けてくれるなら、私はそれをいただければ幸いです。

私が取り組んでいる課題を例にとってみましょう。データセットの1つの部分に対してバイナリ検索ツリーを使用し、次にセット内の別の部分に対してリンクリストを使用します。教授が提案した方法は次のとおりです。

ここで、dataは、各レコードの詳細を含むクラスです。明らかに、設定されているため、treeNodeはリンクリストに存在できません。

次のことははるかに簡単ではないでしょうか。

次に、次のように宣言できます。

両方の挿入アルゴリズムをクラスに含めます。

足りないものはありますか？

私はこの宿題に取り組んでおり、二分探索木を前順、後順、および順番に印刷する必要があります。ただし、私の inorder メソッドだけが機能しているようです。次のテスト ケースを使用して作業を確認しました。

以下の私のコードを見て、私が間違っていることを確認できますか。任意のヘルプ/オリエンテーションをいただければ幸いです。私のためにそれを解決する必要はありません。私が間違っていることを教えてください。ありがとう。