1

スプレーツリーのデータ構造のローテーションが、評価ノードの親だけでなく、祖父母（ジグザグおよびジグジグ操作）も考慮に入れている理由がよくわかりません。以下が機能しないのはなぜですか。

たとえば、ツリーに新しいノードを挿入するときに、左または右のサブツリーに挿入するかどうかを確認します。左に挿入すると、結果が右に回転し、右のサブツリーではその逆になります。再帰的にはこのようになります

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

それは「スプレイ」手順全体を回避するはずですよね？

4

1 に答える 1

5

ツリーで提案しているアルゴリズムは「ルートへの移動」ヒューリスティックと呼ばれ、スプレーツリーに関するSleatorとTarjanの元の論文の4ページで説明されています。彼らは、アレンとマンロによる古い論文を引用しています。そこでは、木の形を変える手段として根への移動を使用しようとすると、各ルックアップの償却コストがO（n）になる可能性があることが示されています。かなり遅い。スプレイは、ツリーを再形成するために非常に注意深く設計されたアルゴリズムであり、実行されるアクセスのシーケンスに関係なく、償却されたO（log n）ルックアップを保証します。

直感的には、ルートへの移動は、アクセスされたノードに将来到達しやすくするために、ノードからルートへのパス上のすべてのノードを下に移動するため、ツリーの形状を変更するのにあまり良い方法ではありません。その結果、このバージョンのツリーの再編成を行うと、ツリー全体が悪化する可能性があります。一方、スプレイ方式では、スプレイされたノードとそのアクセスパス上のすべてのノードの高さが低くなる傾向があります。つまり、スプレイ中にツリー全体が良くなる傾向があります。

お役に立てれば！

于 2012-12-27T19:26:06.377 に答える