問題タブ [avl-tree]

JavaでBSTAVLを取得しました。これは、最後の10ノードを印刷することでバランスが取れていることを証明する必要があります。私のハックの解決策は、ノードの数を知って、順序どおりのトラバーサルの最後の10ノードから値を取得することでした。意図したとおりに機能していません。レコードは姓キーで保存され（重複レコードは保持されません）、各ノードのサイズのプリントアウトは0になります。私のプリントアウトには、ほとんどの場合「Z」の名前が付いています...予想どおり、最初のレコード（26000）のプリントアウトも含まれています。ツリーの障害ではなく、プリントアウトをどのように考案したかという問題だと思います（期待しています）。最後の10ノードを印刷するためのより洗練された方法はありますか？それは私が今持っているエラーを持っていないでしょう、または私の木の回転に欠陥がある可能性がありますか？

InOrderトラバースと出力: (get関数を介してアクセスされる出力）

putメソッド:(ルートノード、キー、および値を渡すメソッドを介して呼び出されます）

これがランダムな質問のように思われる場合は申し訳ありませんが、私は 100,000 を超える名前と値のペア (必要に応じてハイスコアと呼んでください) のデータベースを、バランスのとれた二分探索木、AVL スタイルに格納しています。ほとんどの場合、スコアを一覧表示するために、BST をインオーダー トラバーサルまたはリバース オーダー トラバーサルで出力しますが、今日、ツリーをランダム (または疑似ランダム) 順序で出力する必要があることに気づきました。これを行うための受け入れられた、または最適な方法はありますか?すべてのノードに一度だけアクセスしますが、予測できない方法でアクセスしますか?

PS -- 幅優先トラバーサルについて考えましたが、それは常に同じように行われるため、実際にはランダムではありません。これは一般的な問題のように思われるため、何か賢い方法、または理想的なインタビューの答えが必要です。ノードを訪問済みとしてマークするか、外部追跡データ構造を作成する以外に、本当に賢いものは思いつきませんでした。

C++ で AVL ツリー プログラムを作成しています。以前に作成した BST プライオリティ キュー プログラムに基づいています。残念ながら、ローテーションを引き起こす新しいノードが追加されるたびに、スタック オーバーフロー例外がスローされます。

これまでの私のコードは次のとおりです。

node.h

AVL.h

AVL.cpp

私はAVLツリーを調べていますが、削除に関する参照コードを見つけることができないようです（グーグルまたは私が手元にあるいくつかの教科書から）。
これがなぜなのかわかりませんが、JavaでAVLを削除した参考文献や例をご存知ですか？
（私はこれだけを見つけました：リンクでテスト中に失敗したと述べているavl ツリーの削除）

あるノードの左右の子の高さが 2 違うのは何が問題なのですか?

これは AVL ツリーとの初めての出会いであり、なぜそれが必須なのか理解できないようです。

本当に、子供たちが2つ違うのは何が問題なのですか?

よろしく

Insert新しい要素をAVLツリーに挿入しながらアクションを更新しようとしています。アクションを更新するとinsert、ルートツリーのサイズが各ノードに追加されます。

ここで、要素をボトムアップで挿入するので、+1ツアー中に通過するすべてのノードにを追加すると、たとえば、新しいツリーの後にツリーのバランスをとる必要がある場合など、これが機能しない場合があります。ポインタを変更するため、バランスが取れていないため、計算が正しくありません。

どうすればそれを正しく行うことができるかというアイデアやヒントはありますか？

AVL ツリーを実装しようとしていますが、Node クラスの使用方法に問題があるようです。エラー C4430: missing type specifier with the second getHeight が表示されます サブツリーのノードとして型を指定したと思いましたか?

以下に基本的なアルゴリズムを示します。最悪の場合の入力 BST は、片側のみへの挿入からリンク リストに縮退したものであることがわかっています。

この BST から AVL への変換アルゴリズムの回転数に関して最悪の場合の複雑さを計算するにはどうすればよいですか?

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

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

AVL ツリー ウィキペディアのページに次のコメントがあることに気付きました。

「各ノードがそのサブツリーのサイズ (それ自体とその子孫を含む) を追加で記録する場合、ノードは O(log n) 時間でインデックスによって取得することもできます。」

私はグーグルで検索し、インデックスによるアクセスについて言及している場所をいくつか見つけましたが、作成するアルゴリズムの説明を見つけることができないようです。

どうもありがとう

[更新] ありがとうございます。@templatetypedef の回答が見つかった場合は、@user448810リンクの 1 つと組み合わせて、特に役立ちます。特にこのスニピット：

「これら両方の機能の鍵は、ノードのインデックスがその左の子のサイズであるということです。左の子を介してツリーを下降している限り、ノードのインデックスを取得するだけです。しかし、移動する必要がある場合右の子を介してツリーをたどると、除外したツリーの半分が含まれるようにサイズを調整する必要があります。」

私の実装は不変であるため、各ノードが構築時にサイズを計算するため、リバランス時に追加の作業を行う必要はありませんでした (リンクされたスキーム impl と同じ)。

私の最終的な実装は次のようになりました。

これは他の実装とは少し異なります。バグがあると思われる場合はお知らせください。