問題タブ [splay-tree]

私がスプレイするときのために右回転方法に取り組んでいます。左の子と右の子の値を保持するために使用するノードがあります。左の子をテストしている場合、右はnullですが、コンパイルするとnullポインター例外が発生します。値がnullであっても、nullポインター例外をスローするのではなく、新しいノードをnullに割り当てるだけでよいのでしょうか。

以下は私の割り当てです

テストの場合、ツリーは次のようになります。

xが3であるため、leftCは2であり、leftsRightはnullである必要がありますが、nullポインターをスローするだけです。

単にnullに割り当てるのではなく、nullポインタをスローするのはなぜですか？

ユーザーがバイナリ検索ツリー、スプレイツリー、赤黒ツリーのいずれかを選択できるようにするプログラムがあります。私はバイナリ サーチ ツリーのクラスを作成し、現在はスプレイ ツリーに取り組んでいますが、ユーザーと対話する私のメソッドはバイナリ サーチ ツリーでのみ機能することに気付きました。ユーザーが選択したツリーのインスタンスを作成するように設定しましたが、コードでは、ユーザーが二分探索ツリーを選択した場合に作成される変数のみを使用します。私の質問は、ユーザーが選択したツリーのインスタンスのみを作成するようにするにはどうすればよいか、また、アイテムを挿入したりツリーで作業したりするときに条件ステートメントを追加する必要がないように、変数を 1 つだけ使用するにはどうすればよいかということです。別の木のため？

これは私が今持っているものです

ご覧のとおり、ユーザーが bst を選択した場合に作成されるツリーである myTree のみを入力します。while ループでは、myTree でのみ作業します。

これをより一般的にするにはどうすればよいですか、または私の他のアイデアは、ユーザー入力を取得してそのツリーのインスタンスを作成し、インスタンスを別のメソッドに渡して、インスタンスを参照するため myTree のみを使用できるようにすることでしたそのメソッドに渡されましたが、インスタンスを別のメソッドに渡す方法がわかりません。この方法が最善のようですが、よくわかりません

どんな助けでも大歓迎です

スプレイツリーの右回転メソッドに取り組んでいます。プログラムを実行しようとすると、ヌル ポインター例外が発生し続けますが、その理由がわかりません。これは私のツリーです

これは、lr 割り当て上にあるヌル ポインターを取得する場所です。2 には権利がないため、lr は null である必要がありますが、ノードが null であってはならず、プログラムを続行する必要がありますか? またはnullなので、2に権利があるかどうかを最初に確認する必要がありますか?

問題は次のとおりです。

T を n ノード上のスプレイ ツリーとし、x を T のノードとする。x でのスプレイ操作を考える。x の下のサブツリーは必然的にバランスが取れますか (つまり、スプレイ ツリーの x をルートとするサブツリーの高さは、スプレイ操作後に O(logn) になりますか?

私はそれに多くの時間を費やしましたが、それでもイライラしています....あなたの答えに感謝します。

いくつかのスプレー ツリーアルゴリズムを実装しました。

それらを比較する最良の方法は何ですか？

ランダムノードを追加したときの実行時間を比較するのは良い出発点ですか?

また、各ノードがどれだけアクセスされたかを追跡する二分探索ツリーも実装しました。optimize()最適二分探索木を作成するメソッドを書きました。
検索ツリーを変更する予定がなく、各アイテムがアクセスされる頻度が正確にわかっている場合は、最適な二分探索ツリーを構築できます。これは、アイテムを検索する平均コスト (期待される検索コスト）を最小限に抑えます。
スプレーツリーの比較にこれをどのように含めることができますか?

このスプレー ツリーの実装では、リストされているmakeEmpty()関数 (すべての要素を削除する) の時間計算量は O(n) です。次のように実装されます。

と の両方が木の高さに比例する時間の複雑さを持っている可能性があることを考えるとfindMax、remove最悪の場合、なぜこれに O(n) の時間がかかるのでしょうか?

ありがとう！

ここ ( http://www.nocow.cn/index.php/Code:Splay_Tree/C ) (最初のもの)で説明されているような、トップダウンのスプレイでスプレイ ツリーを実装しようとしています。サブツリーがそのノードのルートである各ノードでサブツリーのサイズも維持するボトムアップ スプレー バージョンを既に実装しています (つまり、サイズ = 1 + 左 -> サイズ + 右 -> サイズ)。

各スプレイ操作と同様に、ノードをルートまで上に移動していたので、ローテーションごとにすべての先祖を更新する必要はありませんでした。しかし、トップダウン バージョンでは、各ノード (および他の種類の不変条件) でこのサブツリー サイズの値を維持する方法がわかりません。各回転で先祖を再帰的に更新する必要はありません。

つまり、トップダウンのスプレイ操作を行っているときに、各ノードでサブツリーのサイズを維持するにはどうすればよいですか? （上記のページに記載されているスプレイ操作の修正版があればいいのですが）

そのため、新しいツリーを挿入した後に Splay 関数を実装することになりました。ただし、複数の int を挿入しようとすると、Segmentation Fault (core dump) と表示されて終了します。

誰でも私の問題がどこにあるかを確認できますか?