algorithm - 二分木 (AVL) のバランスをとる

Question

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

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

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

score 16 · Accepted Answer

ノードバランシングアルゴリズムの完全なコードをここに掲載するのは良くないと思います。ただし、赤黒ツリーに関するウィキペディアの記事には、アルゴリズムの完全な C 実装が含まれており、AVL ツリーに関する記事には、高品質の実装へのリンクもいくつか含まれています。

ほとんどの汎用シナリオでは、これら 2 つの実装で十分です。

score 15 · Accepted Answer

スケープゴートツリーには、理解するための最も単純なバランス決定アルゴリズムがある可能性があります。挿入によって新しいノードが深すぎる場合は、高さのバランスではなく重量のバランスを見て、バランスを取り直すノードを見つけます。削除時にリバランスするかどうかのルールも単純です。ノードには難解な情報は保存されません。それが正しいことを証明するのは難しいですが、アルゴリズムを理解するのにそれは必要ありません...

ただし、AVL とは異なり、常に高さのバランスが取れているわけではありません。赤黒のようにアンバランスは制限されていますが、赤黒とは異なりパラメーターで調整できるため、ほとんどの実用的な目的では、必要なだけバランスが取れているように見えます。ただし、きつく調整しすぎると、最悪の場合の挿入については、AVL と同じかそれよりも悪い結果になるのではないかと思います。

質問への回答編集

AVL ツリーを理解するための個人的な道筋を示します。

まず、ツリーローテーションとは何かを理解する必要があります。そのため、AVL アルゴリズムについて聞いたことがある他のすべてを無視して、それを理解してください。どちらが右回転でどれが左回転であるか、そしてそれぞれがツリーに対して何をするか、頭の中でまっすぐに理解してください。そうしないと、正確なメソッドの説明に混乱するだけです。

次に、AVL ツリーのバランスをとるための秘訣は、各ノードが左サブツリーと右サブツリーの高さの差を記録することであることを理解してください。「バランスの取れた高さ」の定義は、これがツリー内のすべてのノードに対して -1 から 1 の間であるということです。

次に、ノードを追加または削除した場合、ツリーのバランスが崩れている可能性があることを理解してください。ただし、追加または削除したノードの祖先であるノードのバランスのみを変更できます。そのため、ツリーを元に戻して、ローテーションを使用して見つけた不均衡なノードのバランスを取り、バランススコアを更新して、ツリーが再びバランスを取るようにします。

それを理解するための最後の部分は、見つけた各ノードのバランスを再調整するために使用される特定の回転を適切なリファレンスで調べることです。これは、高い概念とは対照的に、その「テクニック」です。AVL ツリーコードを変更している間、またはデータ構造の試験中に詳細を覚えておくだけで済みます。私が最後に AVL ツリーコードをデバッガーで開いてから何年も経ちます。実装は、機能するポイントに到達してから機能し続ける傾向があります。だから本当に覚えていません。数枚のポーカーチップを使ってテーブル上でそれを解決することはできますが、本当にすべてのケースを取得したかどうかを確認するのは困難です (数は多くありません)。調べてみるのが一番。

次に、すべてをコードに変換する作業があります。

コードリストを見ることは、最終段階以外のどの段階でもあまり役に立たないと思うので、無視してください。コードが明確に書かれている最良のケースでも、プロセスの教科書の説明のように見えますが、図はありません。より典型的なケースでは、C 構造体操作の混乱です。だから、ただ本に固執してください。

score 4 · Accepted Answer

最近、AVL ツリーに関する作業を行っています。

それらのバランスをとる方法について私が見つけることができた最良の助けは、グーグルを検索することでした.

この疑似コードをコーディングしただけです (回転の方法を理解していれば、実装は非常に簡単です)。

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

score 1 · Accepted Answer

私は同意します、完全なプログラムは適切ではないでしょう。

従来の AVL および RB ツリーは決定論的アプローチを使用していますが、バランスを維持するためのコストが少なく、キーの統計的分布に関係なく適切なバランスを保証する「ランダム化された二分探索ツリー」を検討することをお勧めします。

score 0 · Accepted Answer

AVLツリーのバランスをとるために、ここでみんなと共有しようと思ったたくさんの関数を書きました。この実装は完璧だと思います。質問/質問/批評はもちろん大歓迎です：

http://uploading.com/files/5883f1c7/AVL_Balance.cpp/

Stackoverflowの初心者なので、ここにコードを投稿しようとしましたが、フォーマットの問題で立ち往生していました。そのため、上記のリンクにファイルをアップロードしました。

乾杯。

score 0 · Accepted Answer

挿入/削除ごとに潜在的に多くのローテーションを行う必要があるため、AVL ツリーは非効率的です。

挿入/削除がはるかに効率的であるため、赤黒ツリーはおそらくより良い代替手段です。この構造により、リーフへの最長パスが最短パスの 2 倍を超えないことが保証されます。そのため、AVL ツリーよりもバランスが取れていませんが、最悪のバランスの悪いケースは回避されます。

ツリーが何度も読み取られ、作成後に変更されない場合は、完全にバランスの取れた AVL ツリーの追加のオーバーヘッドに値する可能性があります。また、Red-Black ツリーは、ノードの「色」を与えるノードごとに 1 ビットの余分なストレージを必要とします。

score 0 · Accepted Answer

@ http://code.google.com/p/self-balancing-avl-tree/という自己均衡 avl ツリーの完全な実装があります。また、対数時間の連結操作と分割操作、およびマップ/マルチマップコレクションも実装します。

algorithm - 二分木 (AVL) のバランスをとる

7 に答える 7

Related

Reference