問題タブ [splay-tree]

私はデータ構造の初心者です。スプレー ツリー: を使用して範囲関数の疑似コードを記述しようとしています。Range(S, A, B)これは、キー値 C が A ≤ C ≤ B を満たすすべてのメンバーのセットに S を変更します。スプレー ツリーがバイナリの型になることはわかっています。ツリーを検索し、独自のスプレイ操作を実装します。基本的に、A と B の間の値の範囲を返そうとしています。しかし、これをどのように行うべきか、どこから始めるべきか、どの条件を確認する必要があるかを理解するのに苦労しています。スプレー ツリーの定義を読んだことがありますが、それらが前方移動アルゴリズムを使用した二分探索ツリーのようなものであることを知っています。

これは私がこれまでに持っているものです:

この時点の後、私はやや失われたように感じます。スプレー ツリーの値を確認する方法がわかりません。追加情報を提供できるかどうか、またはどの方向に進むべきかをお知らせください。

次のような再帰的な SplayTreeMap (自動生成) を取得しました (疑似コード):

クラス エントリは次のようになります。

私がやりたいことは、 に 1 を追加することEntry('subpath', 'othercooltype').songsです。を試しmap.updateましたが、成功しませんでした ( [ERROR:flutter/lib/ui/ui_dart_state.cc(148)] Unhandled Exception: type '(dynamic) => dynamic' is not a subtype of type '(SplayTreeMap<dynamic, dynamic>) => SplayTreeMap<dynamic, dynamic>' of 'update')。また、その値を保存し、キーを削除して更新されたキーを追加しようとしましたが、バグがありました (機能する場合もあれば、機能しない場合もあります)。

私の現在のコード:

スプレー ツリー内の各ディクショナリ操作は、スプレー操作を使用して、ノードをツリーのルートに移動します。このスプレイ操作の償却効率は、通常、潜在的な方法で分析され、オンラインの多くのソース (ウィキペディアを含む) ページで説明されています。このスプレー操作の償却時間は、O(m lg n) として報告されます。

ただし、挿入、削除などの完全な辞書操作の実際の分析はどこにもありません...これらの各操作は、スプレイ操作に加えて、ツリーを下方向に検索して、挿入するノードの正しい位置を見つけますまたは削除します。そのノードを見つけた後でのみ、スプレー操作を開始できます。

人々は次のような発言をする傾向があります。

• 「スプレーツリー操作の複雑さは、関連するスプレーの複雑さと同じです」
• [「私たちの分析では、検索、挿入、または削除を実行する時間は、関連するスプレイの時間に比例することに注意してください」], p. Goodrich の本の 456「C++ のデータ構造とアルゴリズム」

2 つの質問があります。

• 検索を実行する時間がスプレイの時間に比例するというこの結論をどのように出すことができますか? この種のことは、ノードへの下方トラバーサルの時間もスプレイのタイに比例することを意味しますか?
• 下向きトラバーサルの償却時間効率はどれくらいですか? 下向きのトラバーサルを行うだけでツリーの構造を変更しないという理由だけで、それは定数ですか (そのため、可能性は同じままです)。そして、これは最悪の場合なので、= N よりも一定ではありませんか?

どうすればこの結論を下すことができるでしょうか。

スプレーツリーを実装しようとしています。コードは無限ループ印刷に入ります

20 10 20 15 10 20 15 15 10 10 20 15
以下のテストコードでは、それ自体が繰り返されます。デバッグを試みましたが、どこが間違っているのかわかりません。歪んだ方法でノードを挿入し続けると、コードは正常に実行されます。例：最後に 1 を挿入しないとうまくいきますが、スキューがなくなるとすぐに問題が発生します。

これが私のコードです

splay_tree.h

node.h

main.cpp