Splay tree rotationアルゴリズム：単純な回転ではなく、ジグジグとジグザグを使用する理由は何ですか？

Question

私は、スプレイツリーデータ構造のローテーションがレイティングノードの親だけでなく、祖父母（ジグザグとジグジグの操作）も考慮している理由をよく理解していません。なぜ、次のように動作しないのですか？

たとえば、新しいノードをツリーに挿入すると、左または右のサブツリーに挿入するかどうかがチェックされます。左に挿入すると、右のサブツリーに対して結果RIGHTが回転し、その逆も同様です。再帰的にそれが全体の「スプレイ」の手順を避ける必要があり、この

Tree insert(Tree root, Key k){ 
    if(k < root.key){ 
     root.setLeft(insert(root.getLeft(), key); 
     return rotateRight(root); 
    } 
    //vice versa for right subtree 
} 

ようかなっただろう、あなたは思いませんか？

Answer 1

あなたがツリー上で提案しているアルゴリズムは "ルートに移動"というヒューリスティックと呼ばれ、議論されていますon page four of Sleator and Tarjan's original paper on splay trees.アレンとマンローの古い論文を引用しています。ここではmove-to木を再形成するための手段としてルートを作成すると、各ルックアップの償却コストはO（n）になる可能性がありますが、これはかなり遅いです。 Splayingはツリーを再構成するための非常に注意深く設計されたアルゴリズムであり、実行されるアクセスの順序に関係なく、償却されたO（log n）ルックアップを保証します。

直感的に言えば、ツリーへの移動は、ノード上のすべてのノードをルートから下に移動して、アクセスされたノードを将来容易に到達させようとするため、ツリーを再形成する非常に良い方法ではありません。その結果、このバージョンのツリー再編成を実行すると、ツリー全体が悪化する可能性があります。他方、スプレイ方法は、スプレイされたノードおよびそのアクセス経路上のすべてのノードの高さを減少させる傾向があり、全体として、スプレイ中にツリーが良くなる傾向があることを意味する。

希望すると便利です。