問題タブ [search-tree]

私は、データ ノードの最も近い一致を見つける必要があるツリー構造を維持する問題のアルゴリズムを求めています。完全に一致しない場合は、最も近いプレフィックスにフォールバックします。

たとえば、次の構造があるとします。ここで、単語 (単語の数字) は枝であり、角括弧付きの数字はデータ (リーフ ノード) です。以下の表に示すように、一連の結果を返すアルゴリズムを求めています。パスの区切りは">"

私は本当にC++（STLまたはboostベースの）ライブラリを求めています。しかし、この目的のための気の利いたアルゴリズムへのポインタだけでも同様に良いでしょう.

完了した宿題があり、100 点中約 3 点が次の質問に対するものです。

「有向グラフ上に DFS ツリーを構築するとします。その後、バック エッジがないことに気付きます。これはグラフについて何を示しているでしょうか?」

私はこれについていくつか考えましたが、これは、グラフをトポロジー的に横断する特定のパスが 1 つだけ存在するという暗黙の依存関係があることを意味するということだけを推論できます。残念ながら、ウェブ上のどこにもこれに関する情報を見つけることができなかったので、ここに回答を投稿して、誰かがその（不）正確性について検討できるかどうかを確認したいと思いました. この問題の解決に役立つ可能性のある追加の考えや指針があればお知らせください。

本当にありがとう！

分割係数が の検索ツリーを何と呼びますか? ツリー内に格納されているデータ ポイントの次元は2^kどこですか? k(データ点はベクトルですx_1, ... x_k)

通常のk=1二分探索木が得られるからです。k=2ツリー内のすべてのノードで 4 つの象限に分割するなどです。

このような任意のツリーの適切な名前は何kですか?

特定のクエリの検索ツリーを描画する方法と、プロローグでコードをトレースする方法を知る必要があります。以下に例を示します。

a) 次のクエリの検索ツリーを描画します。

プロローグにクイックソートのコードがあります：

例はquicksort([3,2,4,1,5], Sorted)です。私はこれをほとんど描きましたが、 のリストのトレースしか見つけられず、番号Small=[2, 1]のリストに対して同じことを行うことができませんでしたBig。このコードの図を描くのを手伝ってくれる人はいますか? プログラムの実行中のトレースを理解したい。本当に感謝します！

1 から 10^9 までのn 個の数値のセットを保存する必要があります。

1. 初期化には O(n) 時間がかかります - これは数学的な期待値です
2. 検索には O(1) 時間がかかります - これは最悪のケースです
3. 構造体には O(n) メモリが必要です

それを実装することが可能かどうか、およびその方法を理解するのを手伝ってもらえますか?

ハッシュ関数または検索ツリーを使用できると思います。