バイナリツリーのバランスをとる (AVL)

https://stackoverflow.com/questions/133610

02-07-2019
|

質問

OK、これは周りの CS 関係者にとって理論の領域のもう 1 つの問題です。

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

これについて手伝ってくれませんか？

解決

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

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

質問への回答編集

AVL ツリーを理解するための私個人の方法を説明します。

まず、ツリーの回転とは何かを理解する必要があります。そのため、AVL アルゴリズムについて聞いたことのある他のすべてを無視して、それを理解してください。どれが右回転でどれが左回転なのか、それぞれが木に何をするのかをしっかりと頭の中に入れておかないと、正確な方法の説明を聞いても混乱するだけです。

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

次に、ノードを追加または削除すると、ツリーのバランスが崩れる可能性があることを理解してください。ただし、変更できるのは、追加または削除したノードの祖先であるノードのバランスのみです。したがって、これから行うことは、ツリーを遡って、回転を使用して見つかった不均衡なノードのバランスをとり、ツリーのバランスが再び整うまでバランススコアを更新することです。

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

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

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

他のヒント

ノードバランシングアルゴリズムの完全なコードは非常に大きくなるため、ここに投稿するのは良くないと思います。しかし、ウィキペディアの記事では、赤黒の木々アルゴリズムの完全な C 実装とその記事が含まれています。 AVL ツリー高品質の実装へのリンクもいくつかあります。

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

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

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

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

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
  }
}

私も同意します。完全なプログラムは適切ではありません。

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

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

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

ツリーが何度も読み取られ、作成後に変更されない場合は、完全にバランスのとれた AVL ツリーの追加のオーバーヘッドを考慮する価値があるかもしれません。また、赤黒ツリーはノードごとに 1 ビットの追加のストレージを必要とし、これによりノードの「色」が決まります。

AVL ツリーのバランスを取るために、ここで皆さんと共有したいと考えた関数をたくさん書きました。この実装は完璧だと思います。質問/質問/批判はもちろん歓迎です:

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

Stackoverflow の初心者なので、コードをここに投稿しようとしましたが、書式設定の問題が発生してしまいました。そこで、上記のリンクにファイルをアップロードしました。

乾杯。

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

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow

バイナリ ツリーのバランスをとる (AVL)

バイナリツリーのバランスをとる (AVL)