問題タブ [avl-tree]

AVLツリーはBツリーとどのように異なりますか？

ページ化されたバイナリツリーは、AVLツリーやBツリーとどのように異なりますか？

「動く」辞書でフレーズを検索するスライディング ウィンドウ圧縮アルゴリズム (LZ77) を作成しています。

これまでのところ、各ノードが配列に格納される BST を作成しました。配列内のインデックスは、ウィンドウ自体の開始位置の値でもあります。

現在、BST を AVL ツリーに変換することを検討しています。私が見たサンプル実装には少し混乱しています。バランス係数のみを保存しているように見えるものもあれば、各木の高さを保存しているものもあります。

各ノードの高さおよび/またはバランス係数を保存することのパフォーマンス上の利点/欠点はありますか? これが非常に単純な質問である場合は申し訳ありませんが、高さのバランスを実装するために BST を再構築する方法をまだ視覚化していません。

ありがとう。

AVL ツリーを実装しようとしていますが、各ノードの親を挿入して追跡する最良の方法がわかりません。これは教育的なものなので、「ブーストを使用する」ことを提案しないでください:)

これはコンパイルされますが、その正確性や最善の方法であるとは確信していません。具体的にはこれ

また、リバランスしてツリーを上に移動するときに、高さの部分をやり直します。

このように挿入します

これが方法です。ここで 2 番目のパラメーターを何にすべきかわかりません。私は NULL だと思っていたでしょうが、コンパイラはそれを好みません (関数定義が異なります)。

ここに私のインサートがあります

-

教育目的で AVL ツリーを実装しようとしていますが、期待どおりにローテーションが機能しません。

それぞれが左、右、および親ノードへのポインターを持つノードがあります。

以下は、右から右への回転のコードです。まず、インプット（明確にするために、これがRRケースであると私が理解していることです）

ローテーションを行うコードは

これは実際に機能します。a がルートでない場合でも機能します。

失敗しているテストケースは dcbae のようなものです

この場合、回転させてから、何か他のものを差し込んでいきます。

帰って見ようと思った

http://www.cse.ohio-state.edu/~sgomori/570/avlrotations.html

しかし、最初に、かろうじて外れたり、遠く離れたりしていないことを確認したかったのです。

C# で AVL ツリーを実装しましたが、その挿入行列は次のとおりです。

ここで私の質問は、AVL ツリーのパフォーマンスが優れているか、それともアルゴリズムの変更またはコードのリファクタリングを再検討する必要があるかということです。

編集: 要素は、0 から #of 要素までの整数です。テスト コードは次のとおりです。

編集：実装コード

BinarySearchTree

AVLツリー

コードはこちら: http://pastebin.com/VAdc67bE

関数 rotacao_esquerda に問題があります。これは AVL ツリーのローテーションです。

修正方法は？

AVL ツリーを取得するためのバランスを取るプロセスがローテーションと呼ばれるのはなぜですか? （ところで、一回転＆二回転って何？）

私の教科書はどれもその言葉を何の説明もなくあからさまに使っています。

回転を実行してAVLツリーのバランスをとった後、挿入直後に、すべての親ノードのバランス係数を（適切には-1または1で）変更するにはどうすればよいですか？

AVLツリーの各ノードの構造は次のとおりです。

ウィキペディアで与えられた定義に従ってバランス係数を設定しました。

各ノードに親ノードへのポインターが必要ですか？

AVL ツリーにノードを追加するための挿入関数を再帰的に呼び出すときに、特定のノードのバランス係数を計算するにはどうすればよいですか。ローテーション ロジックを開始していません。バランス係数を計算したいだけです。

私の現在の試みでは、左と右のサブツリーの高さを保存することを余儀なくされています。それらがなければバランス係数を見つけることができないからです。