問題タブ [splay-tree]

単語とその頻度を保持するために splaytree を実装しており、単語と頻度 (キーと値) の各ペアを保持する Pair クラスを作成することにしました。つまり、splaytree の各ノードは Pair クラスのペアを保持します。Pair クラスは次のようになります。

スプレイツリー:

BinaryNode クラスがあります。

私が問題を抱えているのは、すべての単語と頻度のペアをツリーに入れ、ペアが既に存在するかどうかを確認し、存在する場合は頻度を1つ上げる方法です。テキスト ファイルを 1 行ずつ読み込み、各行を単語に分割してから、countWords() メソッドを実行しますが、現在は混乱しています。

私はこれが実際には機能していないことを知っています.SplayEntryクラスをインスタンス化する方法と順序を理解するのに助けが必要ですか? また、words 配列内のすべての単語について、それがツリー内にある (含む) SplayEntry に存在するかどうかをチェックし、その単語が新しい単語である場合、頻度は 1 になり、それ以外の場合、頻度は+1になります。最後に、新しい SplayEntry を Splaytree に追加し、それを適切なノードに配置します。

現在、必要以上に多くの時間を同じコードに取り組んでいて、自分自身を混乱させています。正しい方向に導くことができるいくつかの指針を非常に高く評価します!

私が自分自身を明確にしていない場合は教えてください。

スプレー木をテストするためにオンラインでアプレットを見つけようとしていますが、これまでに見つけたアプレットのどれも、私が必要としているものを満たしていません。

すでに構築されているスプレーツリーを入力できるものが必要です。最初のツリーはありますが、順序がわからないため、インサートを使用して構築することはできません。

理想的には、ドラッグアンドドロップアプレットを探しています。

Splay Treesウィキペディアのページには、次のように書かれています(「利点」セクション)。

更新後に以前のバージョンと新しいバージョンの両方にアクセスできる、スプレイ ツリーの永続的なデータ構造バージョンを作成する可能性。これは関数型プログラミングで役立ち、更新ごとに償却された O(log n) スペースが必要です。

何故ですか？関数型プログラミングは、特に永続的な Splay ツリーをどのように利用していますか?

スプレーツリーのデータ構造のローテーションが、評価ノードの親だけでなく、祖父母（ジグザグおよびジグジグ操作）も考慮に入れている理由がよくわかりません。以下が機能しないのはなぜですか。

たとえば、ツリーに新しいノードを挿入するときに、左または右のサブツリーに挿入するかどうかを確認します。左に挿入すると、結果が右に回転し、右のサブツリーではその逆になります。再帰的にはこのようになります

それは「スプレイ」手順全体を回避するはずですよね？

スプレーがどのように機能するのか理解できません。私が従うことができない部分は、i) ii)または iii)を実行する必要が
あるかどうかを知る方法です。 私が正しく理解していれば、これはパス内の現在のノードに関係しています。 それがルートの子である場合、現在のノードの親と現在のノードが両方とも左 (または右) の子であるかどうかに応じて、(ii) または (iii) のいずれかになります。わかりました。 今私が得られない部分： 下に移動すると、中間ノードを左右のサブツリーに「削除」するプロセスではないため、最終的に検索中のアイテムのルートになる中間ツリーができますか？ 次に、ツリーから開始すると、継続的に実行されますzigzig-zagzig-zig

zig


zig要素を削除していて、常にルートにあるため、他には何もありません。
例:

たとえば、私が探している場合20、ルートから始めて左に行きます。したがって、現在のノードにはルートが親としてあり、ジグを実行します。さてどうなる？？私は26左に行きますが、26ルートでもありませんか？では、ジグを行う必要がありますか？
しかし、この例で見たところ、ジグザグが行われており、その理由がわかりません。
ここで何か助けはありますか？

私はいくつかのデータ構造の内外を学習しようとしており、バイナリ スプレー ツリーを適切に機能させようとしています。次のコードを実行すると、探しているノードがルートを 1 つ以上超えているたびに、そこにあることがわかり、ルートからその側全体が削除されます。ノードが上から 1 レベルだけ下にある場合は、正常に機能します。

何がうまくいかないのかわかりませんが、回転機能と関係があると思います。これをモデルにした挿入機能で適切に動作するようにしました。

私はスプレーツリーを作成しました。頭を左に向けたときに通常の方法でツリーが見えるように、逆に印刷しようとしています。次のコードを記述しましたが、ツリーはある程度正しく出力されますが、右端のノードにスペースが追加され、ルートノードの下に配置する必要のあるすべての子ノードにスペースが追加されるわけではありません。

再帰またはインデントの加算と減算の配置にエラーがあるように感じます。

私が持っているコードは

ルートでこのようなツリーを回転させるために呼び出すと:

4 と 1 を削除し、5 を 7 の左根にします。メソッドを void メソッドにしようとしましたが、それもうまくいかないようです。私はこれを完全に間違った方法で行っていますか？

OK、チェックしたい場合は、ここにスプレイアルゴリズムがあります。

これが私のスプレイ関数です：

以下は、ジグ（左に1回転）とザグ（右に1回転）の方法です。

＆これが私のf**の問題です。まず、検索機能のみで表示します。つまり、特定のキーを持つノードが見つかった場合はスプレイします。

私の検索機能：

ノードがrootの子である場合、以下は正常に機能します。-ジグシングル-ザグシングルしかし、シングルノードをダウンさせるとすぐに問題が発生します。私はこれらのことのどれもうまく実行することができません。 ジグジグ-ジグザグ-ザグザグ-ザグジグ

これがサンプルツリーです。（ジグジグケース）

5を検索すると、答えは次のようになります。

しかし、私の出力は次のようになります。

何が問題なのか理解できません。これを100回ドライランしましたが。:( すべての助けをいただければ幸いです。よろしくお願いします。

等しい AVL とスプレイ ツリーを形成するような一連の数字 (1 ～ 7、すべての数字を 1 回だけ使用) はありますか?