具体的には、AVL ツリーです。出来ますか？やりたいのですが、削除されていないノードがローテーションで管理するのに問題があるかもしれないと思っています。
私は正常に動作するものを持っていますが、これを遅延削除で別のものに使用したいと思います。
1680 次
2 に答える
1
すべてのノード (削除済みとマークされたものを含む) に関して「バランス」を維持したい場合は、何もする必要はありません。すでにそこにいます。
削除されていないノードのセットに関して「バランス」を維持したい場合、問題はその理由です。 バランシングの全体的なポイントは、暴走 (線形の最悪のケース) 検索を防ぐことであり、それはノードの削除ステータスではなく、ノードに依存します。
于 2009-03-11T23:34:25.973 に答える
1
AVL ツリーのコンテキストで、削除しないとは正確にはどういう意味ですか?
つまり、ツリーをまったく更新しないということです。
これにより、バランス係数の上方スキャンが不適切なバランス係数で機能するため、ツリーが正しく再調整されなくなります。
これは、バランス係数を更新することを意味する可能性がありますが、バランスをとることはできません。
これは、何かを削除することにしたときに、バランス係数が 2 より大きいか -2 より小さいことになります。これは、修正するために複数の回転を意味します。ただし、ここでの問題は、ローテーション時に、サブツリーの深さを削除したかどうかを知ることができなくなることです。片側に3つのサブツリーの深さが多すぎることはわかっていますが、その余分な深さの各レベルを引き起こしているのは正確に1つの要素であることがわかりません.一度に1つの要素を追加または削除しているため、通常は知っていることです. - そのため、何回転する必要があるかわかりません。3 回のローテーションを行っても、サブツリーの深さは 1 つしか失われません。その深さには 2 つの要素があったからです。実際、どうすれば知ることができますか必要な要素を取得するためにどの要素を回転させるか? 選択した削除要素からのパスと、バランス ファクターが 3 であるポイントに、必ずしもすべてが存在するとは限りません。
確かではありませんが、私たちが知っているように、怠惰な削除はAVLを壊すと言いたいと思います。
とにかく、なぜ遅らせたいのですか？AVL の要点は、O(log n) にとどまるように、各追加/削除でリバランス コストを償却することです。
于 2009-03-28T11:34:08.467 に答える