問題タブ [avl-tree]

わかりました、これは周りの CS 関係者のための理論領域のもう 1 つの問題です。

90 年代、私は BST の実装でかなりうまくいきました。私が理解できなかった唯一のことは、バイナリ ツリー (AVL) のバランスをとるアルゴリズムの複雑さでした。

これについて私を助けてもらえますか？

上の画像は、ウィキペディアが不均衡であると示している「AVLツリーに関するウィキペディアのエントリ」からのものです。この木はどうしてまだバランスが取れていないのですか？記事からの引用は次のとおりです。

ノードのバランス係数は、右側のサブツリーの高さから左側のサブツリーの高さを引いたものであり、バランス係数が1、0、または-1のノードはバランスが取れていると見なされます。他のバランス係数を持つノードは不均衡と見なされ、ツリーのバランスを取り直す必要があります。バランス係数は、各ノードに直接格納されるか、サブツリーの高さから計算されます。

左と右の両方のサブツリーの高さは4です。左のツリーの右のサブツリーの高さは3ですが、それでも4より1つ少ないだけです。誰かが私が欠けているものを説明できますか？

すべての AVL ツリーが赤黒ツリーのように着色できるという証明を探しています。誰か証明してくれませんか？

AVL-treeでノードのバランスを計算する最良の方法を探しています。私はそれが機能していると思っていましたが、いくつかの重い挿入/更新の後、正しく機能していないことがわかりました(まったく)。

これは一種の 2 つの部分からなる質問です。最初の部分は、サブツリーの高さを計算する方法です。「ノードの高さは、そのノードから葉までの最長の下り経路の長さです」という定義を知っています。 ." 私はそれを理解していますが、実装に失敗しています。さらに混乱させるために、ツリーの高さに関するウィキペディアでこの引用を見つけることができます。

2番目の部分は、AVLツリーのサブツリーのバランス係数を取得することです。 「あなたLとサブツリーの高さを取得してからR差し引く」RLという概念を理解するのに問題はありません。そして、これは次のように定義されています。BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

ウィキペディアを読むと、AVL ツリーへの挿入を説明する最初の数行で次のように述べられています。

続いて、「バランス ファクターが 2 または -2 になる場合、このノードをルートとするツリーはバランスが取れていないため、ツリーのローテーションが必要です。ツリーのバランスをとるには、せいぜい 1 回または 2 回のローテーションが必要です。」- 問題なく把握できます。

しかし（はい、常にしかしがあります）。

ここで混乱します。テキストには、「R のバランス係数が 1 の場合、そのノードの (外部) 右側で挿入が発生し、左回転が必要であることを意味します」と記載されています。しかし、私が引用したように、バランス係数が範囲内[-1, 1]にある場合、バランスをとる必要はないとテキストが述べていることを理解していますか?

概念の理解に非常に近づいていると感じています。ツリーのローテーションを減らし、通常のバイナリ検索ツリーを実装し、AVL ツリーを把握しようとしていますが、その本質的なひらめきが欠けているようです。

編集：私は常にコードで何かを把握するのが簡単だったので、コード例は学術的な公式よりも好まれていますが、どんな助けも大歓迎です.

編集：すべての回答を「承認済み」としてマークできたらいいのにと思いますが、私にとっては、NIckの回答が最初に「あはは」になったものでした。

具体的には、AVL ツリーです。出来ますか？やりたいのですが、削除されていないノードがローテーションで管理するのに問題があるかもしれないと思っています。

私は正常に動作するものを持っていますが、これを遅延削除で別のものに使用したいと思います。

プログラム中にソートされていないコレクションから何度か構築する大きなAVLツリーがあります（後でアイテムを挿入/削除するために使用されます）。

各アイテムに単純な挿入を使用するよりも優れたアルゴリズムはありますか? 最初にコレクションを並べ替えてから別の方法で構築する方が効率的ですか?

私のアプリケーションのプロファイリングは、この AVL の建物がホットスポットの場所であることを示しています。

スティーブ・エッゲのシングルトンに関する記事を読んでいました。その中で彼は、先生がAVL木は悪だと言ったと述べています。赤と黒の木がより良い解決策であるというだけですか？

プログラマーとして、RBツリー、Bツリー、またはAVLツリーの使用をいつ検討する必要がありますか？選択を決定する前に考慮する必要がある重要なポイントは何ですか？

重要なポイントを参照して、なぜそれが他のものよりも選ばれるのか、各ツリー構造のシナリオで誰かが説明できますか？

このコードを可能にしたいです。

具体的には、 Comparer クラスにstatic int compare(K key1, K key2)機能を持たせたいと思っています。派生を使おうと考えていたのですが、テンプレートでうまくいくアイデアが見つかりませんでした。

ありがとうございました。

このツリー構造のバランスを取る方法