問題タブ [splay-tree]

バイナリ ツリーのスキルを磨くためにいくつかの演習を行った結果、ウィキペディア: スプレー ツリーで概説されているように、スプレー ツリーを実装することにしました。

私が得ていないことの1つは、挿入に関する部分です。

それは言います：

まず、splay ツリーで x を検索します。x がまだ存在しない場合、それは見つかりませんが、その親ノード y は見つかりません。次に、y に対してスプレイ操作を実行し、y をスプレイ ツリーのルートに移動します。3 番目に、適切な方法で新しいノード x をルートとして挿入します。このように、y は新しいルート x の左または右の子になります。

私の質問は次のとおりです。上記のテキストは、記事の他の例に比べて非常に簡潔に見えますが、それはなぜですか? ここにはいくつかの落とし穴が残っているようです。たとえば、y ノードをルートまで展開した後、やみくもにルートを x に置き換えて、y を左または右の子として x に追加することはできません。

値がツリーにまだ存在していないと仮定しましょう。

私はこの木を持っています：

8 を挿入します。上記の説明で、6 ノードを見つけます。通常のバイナリ ツリーでは、6 ノードの右の子として 8 が追加されますが、ここではまず、ルートまでの 6 ノード:

次に、これら2つのいずれかが明らかに間違っています。

最初にスプレイを行い、次にルートとして新しい値を正しく追加する唯一の方法は、次の基準をチェックする必要があることを意味するように思えます(スプレイされたノードを新しいルートの左の子として追加するため):

1. ルートに展開したノードは、新しいルートよりも小さい (6 < 8)
2. ルートに展開したノードの右端の子も、新しいルート (20 8) より小さいです。

ただし、展開したノードを分割する場合、適切な子を取得して新しいノードの適切な子として追加すると、次のようになります。

しかし、この単純な変更で常に正しいツリーが得られるのでしょうか? 例を思いつくのに苦労していますが、これは次のようになる可能性があります。

• 追加したい新しい値は、一時ルート (ルートに展開したノード) よりも高いですが、一時ルートの右側の子の左端の子よりも高いですか?

すなわち。広げた後、基本的にこのように見えるツリーですが、ルートを置き換える前は?

13 を追加すると、新しいツリーは次のようになります。

または、これは決して起こり得ませんか？

私の 2 番目の質問は次のとおりです。操作を次のように書き直す方がはるかに簡単ではないでしょうか。

まず、splay ツリーで x を検索します。x がまだ存在しない場合、それは見つかりませんが、その親ノード y は見つかりません。次に、新しいノードを親ノードの左または右の子として追加します。3 番目に、追加したノードでスプレイ操作を実行し、新しい値をスプレイ ツリーのルートに移動します。

私が変更したものを示すために私のものを強調してください。

再帰的なスプレー ツリーをボトムアップで実装しようとしています。展開する必要があるノードまで再帰的に下に移動し、そのノードの親と祖父母を見つけます。その後、状況に応じてジグザグまたはジグジグのいずれかをうまく実行できます。問題は、これが完了した後、一度表示されたノードを前の再帰呼び出しに戻すことです。以前の再帰呼び出しは、現在そのノードの子であるノードの親を参照しています。上に行くにつれてノードを上に再帰するにはどうすればよいですか?

アルゴリズムとデータ構造のクラスでは、Haskell でスプレイ ツリーを実装するタスクを課されました。スプレー操作の私のアルゴリズムは次のとおりです。

1. 表示するノードがルートの場合、変更されていないツリーが返されます。
2. 表示されるノードがルートから 1 レベルの場合、ジグ操作が実行され、結果のツリーが返されます。
3. 展開するノードがルートから 2 レベル以上の場合、そのノードから始まるサブツリーを展開した結果に対してジグジグまたはジグザグ操作が実行され、結果のツリーが返されます。

これは私の先生によれば有効です。ただし、ウィキペディアのスプレイ ツリーの説明では、ジグ ステップは「スプレイ操作の最後のステップとしてのみ実行される」と述べていますが、私のアルゴリズムではスプレイ操作の最初のステップです。

ジグ操作を最初ではなく最後に実行するスプレイ ツリーを実装したいのですが、どのように実行するのが最適かわかりません。ジグ操作を実行する必要があるかどうかを判断する前に、展開するノードをどのように見つける必要があるかを考えると、そのようなアルゴリズムはより複雑になると思われます。

Haskell (または他の関数型言語) でこれを実装するにはどうすればよいですか?

例

この例では、値 4 を検索し、それをツリーの一番上に表示するように求めています。

私のアルゴリズム（最初のステップとしてジグ）

ウィキペディアのアルゴリズム (最後のステップとして zig)

どちらのツリーも有効ですが、構造が異なります。2 つ目は関数型言語、できれば Haskell で実装したいと考えています。

私は現在データ構造コースに参加しており、2-3-4木とスプレー木について学びました。どのような状況で、スプレーツリーの代わりに2-3-4ツリーを使用するのでしょうか。それらは両方とも自己バランス型であり、ソートされているので、それらの間にそれほど大きな違いは見られません。

私はスプレー木の基本を読んでいます。ある操作の償却原価は、n回の操作に対するO（log n）です。いくつかの大まかな基本的な考え方は、ノードにアクセスするときにそれをスプレーする、つまりルートに移動するので、次にこれにすばやくアクセスするときに、ノードが深い場合はツリーのバランスを強化するというものです。

このサンプル入力に対して、ツリーが償却O（log n）を実行する方法がわかりません。

n個のノードのツリーがすでに構築されているとします。次のn回の操作はn回の読み取りです。深さnの深いノードにアクセスします。これにはO（n）が必要です。このアクセスの後、ツリーはバランスが取れるようになります。しかし、最新のディープノードにアクセスするたびに言ってください。これは、O（log n）より小さくなることはありません。では、最初のコストのかかるO（n）演算をどのように補償し、各読み取りの償却コストをO（log n）として取得できるでしょうか。

ありがとう。

スプレイ ツリーについて読んでいるときに、ウィキペディアでスプレイ ノード 'X' のランクと償却コストに関する表現を見つけました。{ジグジグまたはジグザグ操作の償却コストを次のように制限できます。

ここで、x はルートに向かって移動されるノードであり、添字 "f" と "i" はそれぞれ操作の後と前を示します。スプレー操作全体を合計すると、これは O(log n) である 3(rank(root)) にテレスコープされます。ジグ操作は多くても 1 つなので、これは定数を追加するだけです。}

私はこれを解釈することができません。上記の詳細を説明してください。可能であれば、いくつかの例を挙げてください。

スプレー ツリーの他の定理の説明へのリンクを提供してください。

ありがとう

一部のバイナリ ツリー データ構造 ( Splayツリーなど) は、読み取り時に再調整して、最近アクセスしたアイテムをルートに移動し、その後のルックアップ時間を短縮できるようにします。

標準コンテナ ( std::map、std::set) はこれを行うことができますか?

少なくとも 1 つの懸念事項は、スレッドの安全性です。以前は、標準コンテナーで読み取り専用操作のみを実行している限り、ミューテックス/ロックなどを導入せずに複数のスレッドからこれを実行しても安全だと考えていました。

通常、標準ツリー コンテナーには赤黒ツリーが使用され、これらのデータ構造は通常、読み取り時に変更されないことがわかっています。しかし、変更を加えた仮想の実装は準拠しているのでしょうか?

私の c++-standards-foo には改善が必要ですが、現在の標準がコンテナーのスレッド セーフに対応しているかどうかはわかりません。これは で違いc++0xますか?

MarkAllenWesisによるデータ構造とアルゴリズムのスプレーツリーについて読んでいます

スプレイ戦略はローテーションのアイデアに似ていますが、ローテーションの実行方法についてもう少し選択的である点が異なります。アクセスパスに沿って下から上に回転します。xを、回転しているアクセスパス上の（ルート以外の）ノードとします。xの親がツリーのルートである場合、xとルートを回転させるだけです。これは、アクセスパスに沿った最後の回転です。それ以外の場合、xには親（p）と祖父母（g）の両方があり、考慮すべき2つのケースと対称性があります。最初のケースはジグザグのケースです。ここで、xは右の子で、pは左の子です（またはその逆）。この場合、AVLの2回転とまったく同じように、2回転を実行します。それ以外の場合は、ジグジグの場合があります。xとpは、両方とも左の子、または両方とも右の子です。

上記のテキストで、「2つのケースと対称性があります」というステートメントの後に著者はどういう意味ですか？2つのケースが示されていますが、ここでの対称性は何ですか？

ありがとう！

いろいろな木を勉強していて、AVL木やスプレー木に出くわしました。私は知りたいです

1. AVLツリーとスプレーツリーの違いは何ですか？
2. これらの房をどのような基準で選択しますか？
3. これらの木のポジティブとネガティブは何ですか？
4. これらの木のパフォーマンスは、大きなO表記でどのようになっていますか？

Javaでボトムアップのスプレイツリーを実行しようとしています。しかし、どういうわけか、ツリーを構築し、いくつかの要素を追加し、挿入されたノードを一番上に広げようとすると、ローテーション メソッドで null ポインター例外が発生します。なぜそのエラーが発生するのか誰にも教えてもらえますか?

基本的に、左ポインター、右ポインター、親ポインター、ルート ノード、および splayNode のホルダーを持つこの汎用 SPTNode クラスがあります。また、単一回転、ZigZig 回転、ZigZag 回転、splay、および挿入メソッドのメソッドもあります。

そして、ここに私の比較クラスがあります: