問題タブ [leftist-tree]

リンク

私がこの質問をする理由は次のとおりです。

参照はメソッド内でのみ切り替えられるため、これは機能しませんか？

私は技術面の面接に向けて勉強していて、1、2 年前のデータ構造に関する講義のスライドを読んでいました。

左派ヒープのマージの最悪のケースの実行時間が O(log n) であるのに対し、スキュー ヒープの場合は O(n) である理由が明確ではありません。

左派のヒープは、小さい方のルートを持つツリーを選択し、その右側のサブツリーを大きい方のツリーと再帰的にマージすることで、A と B をマージします。次に、ヌル パスの長さをチェックし、左派の構造プロパティに違反している場合は、2 つのサブツリーを交換します。

スキュー ヒープも同じことを行いますが、A と B を再帰的にマージするたびに 2 つのサブツリーをやみくもに交換します。

スキュー ヒープのマージの最悪のケースが O(n) になるのはなぜですか? 再帰的にマージするときに高さの境界を保証できないためですか (毎回サイドを交換しているため)? これは、ツリー内のすべてのノードの高さの合計が O(n) になるというフロイドのアルゴリズムと関係がありますか?

removeSelection左派ヒープから特定のノードを削除する関数を実装しました。このコードは、ヒープに挿入されたキーを追跡するハッシュテーブルを介してノードを見つけます。その後、ノードはヒープのルートにパーコレートされ、deleteMinそれを削除するために呼び出されます。swapWithParent呼び出す関数でコードが失敗しているようでpercolateUp、セグ フォールトが生成されます。

これは、ヒープの main から呼び出される関数です。

percolateUp機能:

swapWithParent機能:

NULL ポインターを逆参照している可能性のある場所はありますか? 確認しましたが、エラーが見つからないようです。

こんにちは、私は左派のヒープを実装しようとしています。ここに私のヘッダーファイルとヘッダーファイルのソースファイルがあります

とソースファイル

しかし、これらのエラーが発生しています。なぜこれらのエラーなのか教えてください。関数を const として宣言しましたが、それを変更していないので、何が問題なのですか?私はこの関数を定義しようとしていますが、これは私がしたくないことです。同じ問題がルートにもあります。なぜコンパイラは、ルートの値を変更しようとしていると言うのですか? isempthy() 関数は (root==NULL) かどうかをチェックするだけですが、その値は変更されません。混乱しています。const キーワードを削除した場合、コードはコンパイルされますか?コードの主な動作は変更されませんか?私はここに新しく、非常に大きなコードを投稿して申し訳ありませんが、コードをより明確にするために、ヘッダーとソース ファイルを一緒に投稿します作業を簡素化するために、私を助けてください、私はとても良いサイトが存在することを嬉しく思います。

私の実装は、追跡可能な少数のアイテムで正しく動作します。この左派のヒープは、50,000 個のアイテムを挿入するのに数秒かかりますが、スキュー ヒープは数ミリ秒かかります。

したがって、アルゴリズムは正しく実装されていると思いますが、効率的ではありません。

関係のない (?) コードは省略されています。

最近、Leftist_tree の「Exercise 3.2 マージの呼び出しではなく直接挿入を定義する」に来たときに、Purely-functional-data-structures という本を読んでいます。

それが機能するかどうかを確認するために、本で提供されているマージ機能をテストします。

すると面白いものを見つけました。["a";"b";"d";"g";"z";"e";"c"]このツリーを作成するための入力としてリストを使用しました。そして、2 つの結果は異なります。マージ メソッドの場合、次のようなツリーを取得しました。

実装した挿入メソッドは、次のようなツリーを提供します。

「挿入」バージョンを設計するために「マージ」の実装に従っていますが、2 つの方法の間にはいくつかの詳細があると思います。しかし、その後、逆のリスト ["c";"e";"z";"g";"d";"b";"a"] を試してみると、2 つのleftist-tree-by-insert tree が得られました。それは私をとても混乱させたので、挿入方法が間違っているか正しいかわかりません。だから今、私は2つの質問があります：

1. 私の挿入方法が間違っている場合は？
2. leftist -tree-by-mergeとleftist-tree-by-insertは同じ構造ですか? つまり、この結果は、ある意味でそれらが等しいかのような錯覚を私に与えます.

コード全体

16. 2015年10月更新

2 つの実装をより正確に観察すると、違いがベース ツリーのマージか、より明確に表現できるグラフを使用T (1, x, E, E)した要素の挿入にあることが簡単にわかります。x

そのため、このツリー構造はまさに「左派」であるにもかかわらず、私の挿入バージョンは常により複雑な作業を使用して左派ツリーの利点を利用しないか、常に悪い状況で機能することがわかりました。

少し変更すると、2 つのコードは同じ結果になります。

私の最初の質問ですが、答えは正確ではないと思います。それは本当に左派のツリーを構築することができますが、常に悪い状況で機能します。

2番目の質問は少し無意味です（よくわかりません）。しかし、それでもこの条件は興味深いものです。たとえば、マージ バージョンはより効率的に機能しますが、前述のように挿入順序を必要とせずにリストからツリーを構築します (["a";"b";"d";"g";"z"; "e";"c"], ["c";"e";"z";"g";"d";"b";"a"] 、順序が重要でない場合、私にとってはそれらは同じセットであると考えてください。) マージ関数は、より良い解を選択できません。(["a";"b";"d";"g";"z";"e";"c"] のツリー構造は ["c";"e";" よりも優れていると思います。 z";"g";"d";"b";"a"

だから今私の質問は：

1. それぞれの副右背骨が空のツリー構造は良い構造ですか?
2. はいの場合、常に任意の入力順序で構築できますか?