問題タブ [splay-tree]

スプレイ ツリーを使用している場合、最後にアクセスした要素がルート ノードに到達するのではないかと疑っていました。私のツリーが

順序通りのトラバーサルを実行すると、出力は次のようになります

したがって、ここで最後にアクセスされた要素は です8。疑問があるので、8が最後にアクセスされたノードになるので、ルートノードとして移動したい8ですか?

スプレイ ツリーについて読んだことがありますが、スプレイ ツリーを構築するには 2 つの方法があることがわかりました。彼らです

1. 一気飲み
2. トップダウン

だから私は知る必要があります2つの方法とその働きの違いは何ですか?

Splay ツリーで最悪のシーケンスを実行してみます。

しかし、Splay-tree で最悪の場合のシーケンスは何ですか? また、ツリーに挿入されたキーを指定して、このシーケンスを簡単に計算する方法はありますか?

これで私を助けることができますか？

これはシーケンス 20,10,5,30,40,57,3,2,4,35,25,18,22,27 です。新しく挿入されたすべてのノードをルートとして試してみましたが、うまくいきません。誰かが私に段階的な説明を教えてもらえますか?

スプレイツリーをコーディングしました。ノードはこのように表されます。

ここで、特定の範囲内のツリー内のすべての数値の合計を知る必要があります。このために、次の名前の関数を実装しましたsummation.

ret関数を呼び出す前に初期化されるグローバルint変数です。2 つのパラメーター&は範囲 (包括的) を定義します。0summationsted

このsummation関数は、O(n) の複雑さで機能します。誰でもこれのより速い実装を提案できますか??

2 週間前に、挿入、削除、キーの検索、および 3 つの要素の範囲の合計の取得などの基本的な機能を可能にするスプレイ ツリーの実装を完了しました。この実装は、この質問の参照として、または好奇心から見つけることができます。

追加のタスクとして (オプションで期限が過ぎています。私はこれを成績のためではなく、「Google で検索」するのが容易ではない有用なデータ構造であると信じているため、これを解決しています)、Rope データ構造を実装するように依頼されました。文字列を操作して、文字列が "warlock" で指定されたキーが 0 2 2 の場合、文字列は "lowarck" になります (0 2 は部分文字列 "war" であり、"lock" は "war" を削除した後に残ったものであり、挿入します2 文字目以降は "lo"+"war"+"ck" になります)。これは 1 つのクエリにすぎませんが、30 万文字の長さの文字列に対して最大 10 万のクエリになる可能性があるため、単純なソリューションは機能しません。

私の最初の疑問は、ツリーの初期化についてです(要点を読んだ人のために、ほとんどの人にとって理解しやすいように、頂点の代わりにノードを使用します)。

これは Node クラスと NodePair クラスです。

その後、次の方法でツリーを作成します。

これにより、文字列の最初の文字 (node.key として) の node.size が 1 で、一番左の子になる非常に不均衡なツリーが作成されます。文字列の最後の文字は、size=sb.length() のルートです。

これが正しく初期化されているかどうかは完全にはわかりません。キーとサイズを指定して inorder traversal print を実行したところ、文字列全体がサイズ順で取得されました。これは私が期待していたものです。

その後、Update メソッドを次のように変更しました。

これに：（CLRSの章14.1に基づく）

次に、オリジナルの find メソッド:

これに：（CLRS Chapter 14.1のOrder Statistics-SELECTに基づく）

ただし、ご覧のとおり、このメソッドがノードを返すのに対し、元の検索は NodePair を返すため、この時点で既に問題があります。インストラクターによるNodePairの説明は次のとおりです。

結果と新しいルートのペアを返します。見つかった場合、結果は指定されたキーを持つノードへのポインターです。それ以外の場合、結果は最小の大きなキー (順序の次の値) を持つノードへのポインターです。キーがツリー内のすべてのキーよりも大きい場合、結果は null になります。

Find メソッドを使用して分割するノードを探すため、これは分割メソッドを複雑にします。これに加えて、私はこの find メソッドで NullPointerException を取得しており、他の学生から、他のエラーを回避するには非再帰バージョンを使用する必要があることを理解しているため、基本的には OS-Select の非再帰バージョンを実装する必要があります。以前の find メソッドとして NodePair を使用するか、分割メソッドを次のように変更します。

ご覧のとおり、find メソッドは NodePair の findAndRoot に割り当てられています。OS-Select の非再帰への変換に加えて、私の主な問題は、以前の find メソッドと split メソッドで NodePair が使用される方法を理解することだと思います。

最後に、これはツリーとキーを受け取り、それらを操作するメソッドの実装です。

私のコードからわかるように、私はプログラミングを学び始めて 5 か月しか経っていない初心者であり、Java を選択したので、収集した情報から、このタイプのデータ構造はより中級であることがわかります。エキスパートレベル（以前の splay treeを実装できたことにすでに驚いています。ですから、回答で私の初心者レベルを考慮してください。

PD: これは非再帰的な OS-Select の疑似コード バージョンですが、まだ NullPointerException があります。