問題タブ [binary-search-tree]

ユーザーからの単語が辞書にない場合に同様の単語を生成できる「スマート」辞書を作成しようとしています。

辞書は、単語を含むファイルを読み取ることから始まります。単語はバイナリ ツリーとハッシュ テーブルに追加する必要があります。ハッシュ テーブルは、単語または類似の単語が辞書にあるかどうかを判断するために使用されます。ハッシュ テーブルにはブール効果があるため、バイナリ サーチ ツリーに単語が含まれているかどうかをすばやく調べることができます。ハッシュ テーブルには類似した単語も含まれているため、ハッシュ テーブルは辞書の約 10 倍の長さにする必要があります。Java は比較的新しいので、私の状況に最適なハッシュ関数を作成する方法についてのヒントと提案をお願いします。

一般的なBSTの作成を検討しています。COTSがないという空想はありませんが、ボイドのタイプを追跡するための最良の方法を決定しようとしています*。ノードのインターフェースは次のとおりです。

ただし、追加/削除を作成するときは、比較を行う必要があるため、「データ」が指しているデータの種類を追跡する必要があります。

基本的な考え方は、列挙型Node_Typeと、2つのTreeNodeと列挙型を3番目の引数として受け取る関数compareTreeNodesを持つことです。これにより、関数はvoid*のキャスト先を決定できます。

他の/より良い考えはありますか？

二分探索木を読んでいて、なぜBSTが必要なのかと考えていました。私の知る限り、すべてのことは、単純なソートされた配列を使用して実現することもできます。たとえば-n個の要素を持つBSTを構築するには、n*O(log n)時間が必要です。つまりO(nlog n)、ルックアップ時間はO(log n)です。しかし、これは配列を使用して実現することもできます。ソートされた配列（O(nlog n)時間が必要）を持つことができ、その中でのルックアップ時間も、O(log n)つまり二分探索アルゴリズムです。では、なぜ別のデータ構造が必要なのですか？それらを特別なものにするBSTの他の使用/アプリケーションはありますか？

-ラヴィ

Peter Brass のAdvanced Data Structuresを読んでいます。

検索ツリーに関する章の冒頭で、彼は検索ツリーには 2 つのモデルがあると述べました。1 つはノードが実際のオブジェクト (ツリーが辞書として使用される場合の値) を含み、もう 1 つはすべてのオブジェクトが格納されている場所です。葉と内部ノードは比較専用です。

最初のモデルに対する 2 番目のモデルの利点は何ですか?

データ構造の中間試験に備えて、教授は昨年のテストを出しました。これは、サンプル ツリーを完全な二分探索ツリーに再配置する問題です。ツリーを書き出すいくつかの異なるバージョンを試しましたが、Wolfram Mathematica からのこの完全なバイナリ ツリーの例は、フルの定義にも適合するため、まったく役に立ちませんでした。教科書では、完全なバイナリ ツリーを、レベル n-1 までのツリーが完全であり、レベル n にいくつかの余分なリーフ ノードがあり、すべて左揃えであると定義しています。

ノードはA E I L N O P R S T U、n=11 ノードです。これが私が思いついた最良の答えです：

しかし、これは WM のツリーの例には当てはまりますが、本の例には当てはまりません。それで、正しい答えはどれですか？

以前にも同様の質問があったことは知っていますが、私の解決策ははるかに簡単だと思います。特にウィキペディアと比較すると。

私が間違っていることを証明してください！

指定されたデータ構造を持つノードを持つツリーがある場合:

次のような関数を書くことができます:

このコードは非常に簡単で、最悪の場合は O(n)、平均的な場合はおそらく O(logn) です。特にツリーのバランスがとれている場合 (n はツリー内のノードの数)。

ハッシュテーブルに対する二分探索木の利点は何ですか？

ハッシュテーブルはTheta（1）の時間内に任意の要素を検索でき、要素を追加するのも同じくらい簡単です....しかし、逆の利点があるかどうかはわかりません。

私は Dr. Racket を使用しており、言語は Pretty Big で、単純な二分探索木を "in?" で作成しようとしています。値が二分探索木にあるかどうかを返すメソッド。あらゆる種類の検索ツリー (文字列、int などを含むかどうか) を受け入れて、一般的である必要がありますが、このエラー メッセージが表示されて気が狂いそうです。コードは次のとおりです。

編集:: 現在は動作しますが、数字以外では動作しません (または、少なくとも文字列では動作しません)。新しい問題:

私が受け取っているエラーは言う:

使用時:

入力として。

BSTからノードを削除するにはどうすればよいですか？

Dr.Schemeでそれを行うためのアルゴリズムが必要です。

以下に示す二分木を前提として、関数A（root）が呼び出されたと仮定して、以下に示す二分木のノードにアクセスする順序を決定します。ツリーノードとポインタが次のように定義されていると仮定します。rootが60を含むノードへのポインタであると仮定し ます。この問題に対する私の答えを以下に示します。それが正しいか？私は何を間違えましたか？

回答： void Aでは、最初にnode_ptr->データを出力して、60が出力されるように指示します。次に、関数はB（node_ptr-> left）を呼び出し、次にB内でAが呼び出され（node_ptr-> left）、5であるデータを出力します。 。次に、A（node_ptr-> right）が呼び出され、Aに戻り、そのデータを印刷して、8が印刷されるようにします。次に何をすべきかよくわかりませんが、論理的には30を印刷するのは理にかなっていますが、ptrが8から30になる方法がわかりません。同じパターンで続行すると、38が印刷され、32が印刷されます。右のサブツリーの場合...9077 62 88