問題タブ [treap]

複数の等しいキーを持つバランスの取れた検索ツリーを作成する必要があります。必要な機能を実装しました：

私が遭遇する問題は、ツリーからノードを削除 (stergere) することです。一意のキーを削除しようとすると機能しますが、一意でないキーを削除しようとするとクラッシュします。

それは動作しますが、:

そうではありません。

この関数をどのように変更すればよいですか?

私が Web で見たほとんどの例では、ランダムな (異なる!) 優先順位を生成するある種の外部乱数ジェネレーターがあると見なされています。

私が覚えていることから、優先順位を実際にランダムに生成し、それらをトレプに挿入して、可能な優先順位の衝突を解き放つ方法がありました。

では、2 つの質問があります。

1. Treap は実際にすべての優先度を個別に持つ必要がありますか、それとも最終的に比較される可能性のあるノードの優先度のみを持つ必要がありますか? つまり、優先度のある 2 つのノードがあり、pそれらが決して接触しないことを確認できる場合、それらに同じ優先度を持たせることに問題はありますか?
2. Treap で優先順位を生成および解除するにはどうすればよいですか?

ありがとう

編集：これが私が話していることの説明です：

問題 8.12 @ランダム化されたアルゴリズム

次に、treap の操作を実装するために必要なランダム ビットの数を分析してみましょう。単位間隔 [0,1] から各優先度 Pi を一様にランダムに選択するとします。次に、各 Pi のバイナリ表現は、偏りのないコイン投げの結果である (潜在的に無限の) ビット シーケンスとして生成できます。アイデアは、異なる優先度間の比較を解決するために必要な数のビットのみをこのシーケンスで生成することです。ツリー T 内の要素の優先順位のバイナリ表現のプレフィックスをいくつか生成しただけだとします。ここで、項目 y を挿入しながら、その優先順位 Py を他の優先順位と比較して、y をどのようにローテーションするかを決定します。PyをいくつかのPIと比較しながら。現在の部分バイナリ表現で比較を解決できる場合は、完了です。さもないと。それらは同じ部分バイナリ表現を持ち、最初に異なるまで、それぞれに対してより多くのビットを生成し続けます。

だから、私は構造を持っています

次に、

私が理解していないのは、この機能です：

私が理解しているように、同じ型の構造体へのポインターの 2 つの参照を渡すよりも、構造体へのポインターとして渡しますt。tsplit()参照の代わりにポインターを渡すことができないのはなぜですか? 意味はありますか？

私は最近treapを学んでいますが、優先順位のために乱数を生成するために奇妙な方法を使用した実装に行き着きました.私はそれを取得できません.

データ構造とアルゴリズムに関する学部課程の学期プロジェクトとして辞書プログラムを作成する必要があり、問題に対する最適な解決策 (データ構造) を見つけることが期待されています。

ハッシュ テーブルまたはトライのいずれかを使用することを検討しました。誰かからTreapsの使用を勧められましたが、まだ調べていません。

私のデータベースには、約 10 万個の異なる単語とその意味が含まれています。プログラムが提供することが期待される基本的な機能は、単語/定義の挿入、更新、削除、および検索です。オートコンプリートとスペル修正をなんとか押し込むことができれば、それは追加のボーナスになります.

したがって、私の質問は、私の要件を念頭に置いて、どのデータ構造が私の目的に最も適しているかということです。私が「最高」と言うとき、実行時の複雑さと低コスト (メモリ要件) が最も優れたデータ構造を求めています。

また、指定された接頭辞で始まるすべての単語を返すアルゴリズムが必要でした。たとえば、関数呼び出しを行うと、、、などで始まるdictionary.getWordsStartingWith("fic")すべての単語のリストが返されるはずです。辞書をトライとして実装すれば、これを実行できることはわかっていますが、これは可能ですが、可能ですか?ハッシュテーブルでそれを行うには？ficfictionfictitiousfickle

私は丸一日デバッグしてきましたが、本当に完全に迷っています。ヘルプ！Visual Studio でローカルに大量のケースをテストしました。それは正常に動作します。しかし、当校のオンラインジャッジシステムでは、セグメント障害の問題を意味するRE(exitcode 6)を報告するケースがいくつかあります。これらのケースで何が起こったのか、すべてのランダムなケースがローカルで完全に機能していることは本当にわかりません。セグメント障害を引き起こす可能性のある問題のリストを確認しました。なかなか手が出ないので、助けてください。それは本当に私を夢中にさせます。

注: ネタバレです。データ構造にはさらに多くのコードがありますが、残りは正常に機能するため、関連するすべてのコードを取得しようとしました。treapNode* treap::deleteNode(valueType value)この関数がセグメント違反の問題を引き起こすと確信しています。不足している点に気付いた場合は、お知らせください。

とても長く見えて本当に申し訳ありません...私のコーディングに関するアドバイスはありますか？本当に感謝しています！

- - - - - - - - - -アップデート - - - - - - - - - - -

わかりました、簡単にするためにすべてのコードをここに置きます。ところで、私は UNIX のようなプラットフォームにアクセスできません...

-------------------入力フォーマットの更新----------------

例：

oj は、既に存在する番号を挿入せず、存在しないランクを削除しないことを約束します。

HackerRankの問題に対するこの解決策を理解するのに苦労しています。以下のソリューション コードをご覧ください。尾中公幸氏によるものと思われます。

問題は次のとおりです: 一意の番号のリストとm、タイプ " " のクエリが与えられた場合、move the current ith to jth elements (l,r) to the beginning番号の最終的な配置が返されます。

Onaka は、treap データ構造 (優先度と二分探索の両方を維持するもの) が での解決に役立つことを示唆していますO(m log n)。私は C++ に精通していないので、treap の使用方法を概念化しようとしましたが失敗しました。私の理解では、問題を解決するには、現在の要素logへの時間アクセスと、現在の最初の要素と全体的な順序の時間更新が必要です。しかし、それを概念化する方法がわかりません。ith to jthlog

理想的には、それがどのように行われるかを言葉で説明したいと思います。または、オナカのコードが何をしているかの説明です。

ありがとう！

Treap のヒープ順序に違反できるかどうか、または左および/または右回転メソッドを使用した構造のような二分探索ツリーであるかどうかはわかりません。

これは左回転のコードです

と右回転

これらのローテーションが、ヒープの順序付けと、treap の構造のようなバイナリ検索ツリーに違反しないことを期待しています。