問題タブ [tree-balancing]

アルゴリズムが進むにつれて大きくなる大きなツリーがあります。各ノードにはセットが含まれています。これは、平衡二分探索木として実装されていると思います。各ノードのセットは、そのノードの作成後、そのノードの子の作成に使用する前に、固定されたままになります。

ただし、各セットのコピーには法外な費用がかかるのではないかと心配しています。代わりに、新しく作成された各ノードのセットが、親ノードのセットの適切な部分をすべて利用することをお勧めします。要するに、私はセットのO（log n）をコピーするのは幸せですが、O（n）はコピーしません。

そのような部分的なコピーの最適化を提供するSTLの連想データ構造の変形はありますか？おそらくブーストで？もちろん、このようなデータ構造をHaskellやOCaMLに実装するのは簡単ですが、C++ではより多くの労力が必要になります。

各ノードの重みを使用して、(int を使用しますが、ジェネリックに設計された) 二分探索ツリーのバランスを取るための再帰的な Java メソッドを構築しています。私の目的では、ノードの重みは子の数 + 1 として定義されます。

バランシングの最後に、任意のノードの値は、そのノードをルートとするサブツリー内のすべてのノードの値の中央値になります。

これが私のコードです：

何も返さずにツリーを変更しようとしていますが、コードはツリーを変更しません。どこかで参照渡しと値渡しで混乱していることは知っていますが、どこにあるのかわかりません-誰か助けてもらえますか? デバッグに数時間費やしましたが、再帰をデバッグするときは本当に混乱します。

スプレーツリーのデータ構造のローテーションが、評価ノードの親だけでなく、祖父母（ジグザグおよびジグジグ操作）も考慮に入れている理由がよくわかりません。以下が機能しないのはなぜですか。

たとえば、ツリーに新しいノードを挿入するときに、左または右のサブツリーに挿入するかどうかを確認します。左に挿入すると、結果が右に回転し、右のサブツリーではその逆になります。再帰的にはこのようになります

それは「スプレイ」手順全体を回避するはずですよね？

ツリーのバランス部分に問題が発生しました。再帰的な挿入の後にcheckBalが呼び出されました。5、2、4を追加しようとすると、2のバランスがチェックされ、5まで戻り、右回転の左の部分に移動します。これは正しいことです。しかし、rotateLeft関数は2行目でエラーになります。

この実装の何が問題になっていますか？私はあちこちを検索し、私がしたことを人々がそれがどのように行われたかについて話す方法と比較しました。私はついにすべてが機能するようになりました。最後にNをKに設定するのを忘れていました。

ツリーがAVLツリーであるか、プロローグを使用していないかをテストしようとしています。

これまでに行ったテストで機能する高さテストを作成しましたが、バランステストはまだうまくいきません。

これはこれまでの私の仕事です：

私はこのコードを古いstackoverflowコードに基づいています。ただし、すべての場合に機能するわけではありません。私の身長コードが含まれます。どこかで私は間違いを犯しました、そして私はそれをどこで見つけるか確信しています。

なぜ私のコードはいくつかの木を評価しないのですか？

Prolog-バランスツリーかどうか

これは私がバラナスツリーのテストに基づいたスレッドであり、彼がコメントに投稿したツリーで試してみましたが、失敗しました。何かアイデアはありますか？

C ++で赤黒木を実装していますが、回転メソッドに問題があります。挿入方法はバランスが取れていなくても問題なく機能しますが、回転しようとするとすぐにツリーの情報が失われます。私の推測では、ノードへのポインターを正しい方法で設定していませんが、ここで何が問題になっているのかを正確に理解していません。

これが私の右回転方法です：

起こっていることの例は、c、b、およびaを挿入することです。ツリーは最初は次のようになります。

ローテーション後、ツリーはルートノードのみを出力します。

何が起こっているのかについて何かアイデアはありますか？ありがとう！

したがって、KD ツリーのバランスをとるときは、中央値を見つけて、それよりも小さいすべての要素を左側のサブツリーに配置し、大きいものを右側に配置する必要があります。しかし、中央値と同じ値を持つ要素が複数ある場合はどうなるでしょうか? それらは左のサブツリーに入りますか、右のサブツリーに入りますか、それとも破棄しますか?

私は複数のことを試してみましたが、最近傍検索アルゴリズムの結果に影響を与え、ツリーの特定のセクションのすべての要素がすべてまったく同じ値を持つ場合があるため、質問しません。その場合にそれらを分割する方法を知っています。

N 個のノードを持ち、すべての内部ノードが p 個の子を持つ一定の (一度構築されると変更されない) バランス ツリーがあるとします。明らかに、ノードにアクセスするための最悪のシナリオは logp(N) です。しかし、r 個のノードにアクセスするための償却コストはどうでしょうか? それらに昇順でアクセスするとどうなるでしょうか (検索ツリーを使用)。それはただの (logp(N))/r ですか?

AVL ツリーのプレゼンテーションを作成していますが、バランス ファクターとは何かを理解できません。AVLツリーの高さがどのように影響するかをグラフィカルに理解できるリンクまたは何かを教えてください