アルゴリズムコースの最近のテストでは、AVLツリーの再バランスに使用されるメソッドを使用して、特定のバイナリツリーのバランスをとるタスクを得ました。問題は、もしその木がBSTでないならば？ローテーションを使用するのは理にかなっていますか？つまり、あなたはそれらを使うことができますが、それを「修正」する前にそのようなツリーのバランスをとる方法はないようです。それをBSTにします。非BSTとのバランス
可能であれば、これが役立つ状況はありますか？私は混乱を招く以外に、この背後にある真の論理を見つけることができないようです。
これは実際にツリーが表すものによって異なります。ツリーの回転は、バイナリ検索プロパティを保持しながらツリーを再構成する方法を表すため、バイナリ検索ツリーについて話す際の自然なアイデアです。他の木では、これは不可能かもしれません。たとえば、BSTのように動作しますが高次元で動作するk-d treeでは、ツリー内のノードのレベルがそのノードに対する比較の仕組みを決定するため、回転はできません。ただし、サブツリーを削除して最初から再構築することで、k-dツリーを再調整することは可能です。 （この考え方は、通常のBSTでも使用できます;詳細はscapegoat treeを参照してください）。
パーズツリーなどの他のツリー構造では、順序付けではなく階層構造をエンコードするため、回転という概念は全く意味がありません。そのような場合、ツリー自体が根本的に不均衡なものを表現しようとしているため、ツリーは基本的に不均衡になっている可能性があります。
一般的に、いいえ、特定の状況では、よりバランスのとれたツリーについて話すことは可能かもしれませんが、ツリーの回転を非BSTに一般化する方法はありません。
BSTを使用する本当の感覚は、O（logn）検索にあり、各要素を置き換えます。 ツリーがバイナリでない場合、検索と置換はコストがかかるため、AVLをBSTとしてバランスさせる理由が最悪の場合にリンクリストになります。
アプリケーションには、メモリ管理、プロセススケジューリングなども含まれます。などなど。