問題タブ [avl-tree]

再帰的な手順を使用せずに、avl ツリーのノードのバランス係数を計算したいと考えています。どうやってやるの？メソッドを教えていただくか、C++ コード スニペットを提供してください。

私が開発したAVLツリーを使用するためのコードを投稿します。挿入方法、avlinsert方法は以下のとおりです。私はこのコードを紙で開発しましたが、テストされていませんが、これが機能することを願っています。私が議論したい主な問題は、ノードが最初にコードを見るバランスファクターです。このようにして、私が何を求めようとしているのかが明確になります。だからここにコードがあります：

これはコード全体ではありませんが、私がやろうとしていることを示すには十分です。このコードで、挿入中（2番目のwhileループブロック）にノードのバランス係数を設定していることがわかりました。OK、これで結構です。しかし、この挿入の後、回転を実行する必要があります。回転のコードもありますが、主な問題は、ノードが回転するときに、回転のコードでノードのバランス係数をリセットする必要があることです。これが私の問題です。どうすればいいですか？そして、コードスニペットは何でしょうか？

AVL ツリーのノードのバランス係数を計算するには、左側のサブツリーの高さと右側のサブツリーの高さを見つける必要があります。次に、左側のサブツリーの高さから右側のサブツリーの高さを引きます。

balancefactor = leftsubtreeheigh - rightsubtreeheight

私の質問は次のとおりです。左のサブツリーまたは右のサブツリーの高さを計算するにはどうすればよいですか?

たとえば、与えられた図^₁では、ルート ノード 40 の左側のサブツリーの高さは 4 で、40 の右側のサブツリーの高さは 2 であるため、高さの差は 2 です。

C++ でこれを行うにはどうすればよいですか? 非常に紛らわしいので、再帰は使いたくありません。再帰の代わりに明示的なスタックを使用すると、はるかに理解しやすくなります。

^₁ フィギュアは imgur サーバーから削除されました。

AVL ツリーの実装を依頼する課題に取り組んでいます。回転方法が正しいと確信していますが、いつ使用するかを理解するのに苦労しています。

たとえば、本の説明では、ノード/要素を挿入するために下ったのと同じ道を登る必要があると書かれています。ただし、親ポインターを持つことはできません。

最新のコード:

ここでやりたいことは、ツリーを元に戻すことですが、ノードを挿入した後でのみバランスを確認できます。したがって、これはelse節にあります。

R Samuel Klatchko が提案したバランスコードも入れてみましたが、各インサートのバランスを確認しました。例: 7、9、5、3、および 1 を連続して挿入すると、1 を挿入しようとすると null ポインター例外が発生します。

編集：上記の理由の1つは、私が高さを行っていた方法に関係している可能性があります. height() を使用して毎回高さを計算すると、単一の右回転で正常に動作しますが、AVL ツリーの O(log(n)) 時間を壊します。

これを達成する方法について何か考えはありますか？

2つのAVLツリーがあり、最初のツリーの各要素が2番目のツリーのどの要素よりも小さいと仮定します。それらを単一のAVLツリーに連結する最も効率的な方法は何ですか？私はどこでも検索しましたが、有用なものは何も見つかりませんでした。

この非常に単純なコード ブロックに問題があります。アドバイスをください。 （私はこの問題を解決しました。この問題を解決する際に、ID stakx を持っている人が本当に助けてくれました。唯一の問題は、スタック < treeNode > を使用していたことでした。スタックのプッシュ メソッドを注意深く見たところ、コピー プロセスがありました。 head->object=number と書くと、最後にこの stack< treeNode* > のようなポインターのスタックを作成し、問題を本当に解決しました。今は問題ありません。stakx という人にとても感謝しています。)

コードの前に、次のツリーalt テキスト http://img44.imageshack.us/img44/7016/avlimage06.jpg を想定する必要があります
。ルートが 8 で、スタックに 6 と 4 の 2 つのノードがあることが図でわかるように。このスタックとルート ノードを次のコードに渡します

この関数の出力は、

ここに私が使用しているスタックの pop メソッドのコードがあります

これがスタックのプッシュメソッドのコードです

BBTHMNN(h) = 平衡二分木には最小数のノードがあります

BBTHMNN(h) = BBTHMNN(h-1) + BBTHMNN(h-2) + 1

上記の式を満たす平衡二分木の名前。ネットで調べたのですが、木の名前がわかりませんでした

以下のコードはほぼ完全に機能しますが、9、7の子は、左の子としてではなく、まっすぐにぶら下がっています。どうすればこれを修正できますか？

ありがとう、CB

サポートの重複キーを作成したいavl-treeのですが、with duplicates のデフォルトの動作に問題がありbinary search tree、ローテーションによって同じキーを持つノードが親の左右に配置される可能性があります。

たとえば、すべてキー A を持つ 3 つのノードを追加すると、ツリーは次のように回転します。

したがって、そのキーですべてのエントリを取得することは問題になります...そして、双方向の検索は良くありません。

私が考えた解決策は、各ノードに重複の配列を格納することです。そのため、既に存在する新しいアイテムを追加すると、新しいアイテムが配列に追加され、キーでアイテムを削除するとノード全体が削除され、すべてのアイテムが検索されますwith key はその配列を返します。

重複を処理する他の方法はありますか?

挿入項目はキーと値を受け取ります..したがって、特定のキーメソッドを使用してfindAllで値を返すために、値を保存する必要があります。

私は現在、AVL ツリーの使用を必要とするプロジェクトを行っています。avl 用に作成した挿入関数は機能していないようです。最大で 3 つまたは 4 つのノードで機能します。

私は本当にあなたの助けに感謝します