問題タブ [avl-tree]

次のコードは、私を本当に困惑させました。

クラス

挿入機能。

これが高さ関数です。

誰でも理由を知っていますか？

=== 更新:

ローテーションをするとき

必要に応じて値を交換していないようです。n = child はローカルでスワップしているように見えますが、残りのコードの変更は反映されていません。私に無限ループを与えます。

私は IIT からデータ構造についての講義を見ています (Dr.naveen garg ) AVL ツリーについて。

私の質問: T2 の高さが (h-1) にならないのはなぜですか?

50,49,48をAVLツリーに挿入すると、印刷されます。

これが私の関数です。左に回転：

入れる：

私はAVLツリーについて学び、すべての回転を行う方法を知っていますが、知っておく必要があるのは、挿入または回転のたびにノードのバランス係数が更新されるようにする方法です。

ありがとう！

「ここからインスタンス化」に問題があります。

私のエラーは次のとおりです。

私が取り組んでいる AVL テンプレート (C++ テンプレート) の一部として、n1+n2 が両方のツリーの合計要素である場合、O(n1+n2) の複雑さで 2 つの AVL ツリーをマージしようとしていました。

次のアルゴリズムを考えました。

1. 1 番目のツリーを順番にトラバーサルし、配列/リストを作成する - O(n1)
2. 2 番目のツリーでの順序走査と配列/リストの構築 - O(n2)
3. これら 2 つの配列の並べ替えをマージし、n1+n2 - O(n1+n2) のサイズで最終的に並べ替えられた配列/リストを作成します。
4. n1+n2 頂点 - O(n1+n2) を持つ空のほぼ完全な二分木を構築します。
5. マージされた配列/リスト内の要素で頂点を更新しながら、ほぼ完全な二分木を順番にトラバーサルします。

私の質問は、n1 + n2頂点を持つ空のほぼ完全なバイナリツリーを実際に構築するにはどうすればよいですか?

JavaでAVLツリーを実装したいのですが、これまでに持っているものは次のとおりです。

add 関数と remove 関数を実装する必要があります。これが私がこれまでに持っているものです。両方ともO(log(n))時間内に実行されるはずです。どちらもツリー全体のルートを返す必要があります。

追加機能と削除機能の作成について助けが必要です。

追加操作と削除操作がどのように機能するかを説明するガイドはありますか? コピーするライブラリ、または AVL ツリーがどのように/なぜ機能するかを理解できるものはありますか?

今のところ、同じ側の AVL ツリーの更新の実装のみに取り組んでいます。

私が得ている問題は、バイナリ検索ツリーが AVL の並べ替えを通過した後、表示機能が爆発することです。それに応じてポインターを移動しますが、関数が壊れると別のオブジェクトが挿入され、一生デバッグできません。どんな助けでも大歓迎です。

ここに私のAVLTreeクラスがあります

}

一般的な AVL 実装を http://sourceforge.net/projects/standardavl/files/standardavl/0.1/からダウンロードしました。

このプロジェクトのメイクファイルは、コードを正しくコンパイルします。コンパイラは次の出力を生成します。

makefile は「standardavl.cpp」のみをコンパイルします。standartavl には「AvlTree.h」が含まれており、このファイルには「AvlTree.cpp」が含まれているためです。

標準avl.cpp

AvlTree.h

私のプロジェクトでは、ファイル AvlTree.h から最後の行 (#include "AvlTree.cpp") を削除し、そのファイルを個別にコンパイルしました。ファイル「standardavl.cpp」も使用しません。ファイル Point.h を KeyPair.h に変更し、そこにすべての演算子を実装しました。

私のコンパイラは次の出力を生成します。

ここで何が間違っていますか？

AVL tree各ノードは次のもので構成されています。

• 鍵
• 価値

はキーAVL treeで並べ替えられます。

したがって、2つのキーを取得し、それら2つのキー間の最大値を見つけたい場合。左側のサブツリーの最大値や右側のサブツリーの最大値など、各ノードに追加情報を追加しようとしましたが、間にいくつかのノードを「失う」ことなく正しいアルゴリズムを取得することはできません。

複雑さの時間： O（log n）最悪の場合。