algorithm - スプレーがどのように機能するか理解できません

Question

スプレーがどのように機能するのか理解できません。私が従うことができない部分は、i) ii)または iii)を実行する必要が
あるかどうかを知る方法です。 私が正しく理解していれば、これはパス内の現在のノードに関係しています。 それがルートの子である場合、現在のノードの親と現在のノードが両方とも左 (または右) の子であるかどうかに応じて、(ii) または (iii) のいずれかになります。わかりました。 今私が得られない部分： 下に移動すると、中間ノードを左右のサブツリーに「削除」するプロセスではないため、最終的に検索中のアイテムのルートになる中間ツリーができますか？ 次に、ツリーから開始すると、継続的に実行されますzigzig-zagzig-zig

zig


zig要素を削除していて、常にルートにあるため、他には何もありません。
例:

たとえば、私が探している場合20、ルートから始めて左に行きます。したがって、現在のノードにはルートが親としてあり、ジグを実行します。さてどうなる？？私は26左に行きますが、26ルートでもありませんか？では、ジグを行う必要がありますか？
しかし、この例で見たところ、ジグザグが行われており、その理由がわかりません。
ここで何か助けはありますか？

Answer 1

ルートとは、展開しているサブツリーのルートではなく、ツリー全体のルートを意味します。したがって、あなたの例では 12 がツリー全体のルートです。

...

作業の例が必要な場合は、最近 Java で SplayTree をコーディングしました。コードはこちらにあります。

スプレイ ツリーの大きな点は、最近挿入/クエリされたノードをツリー内で (最大で) 2 レベル上に移動することです。祖父母と親ノードの位置に基づいて、ジグ、ジグジグ、またはジグザグを実行する必要があります。

ノード x がアクセスされると、x に対してスプレイ操作が実行され、ルートに移動されます。スプレー操作を実行するには、一連のスプレー ステップを実行します。各ステップは x をルートに近づけます。

3 種類のスプレイ ステップは次のとおりです。(g = グランド ペアレント、p = 親、x = スプレイするノード)

• ジグ ステップ: このステップは、p がルートのときに行われます。ツリーは、x と p の間のエッジで回転します。
• ジグジグ ステップ: このステップは、p がルートではなく、x と p が両方とも右の子であるか、両方とも左の子である場合に実行されます。ツリーは、p をその親 g と結合するエッジで回転し、次に x と p を結合するエッジで回転します。
• ジグザグ ステップ: このステップは、p がルートではなく、x が右の子で p が左の子である場合、またはその逆の場合に実行されます。ツリーは x と p の間のエッジで回転され、次に x とその新しい親 g の間のエッジで回転されます。

http://en.wikipedia.org/wiki/Splay_tree

以下は、ツリー内のノード 3 の表示です。

スプレーする前のツリー:

└── 0
    └── (right) 9
        └── (left) 7
            ├── (left) 5
            │   ├── (left) 1
            │   │   └── (right) 2
            │   │       └── (right) 4
            │   │           └── (left) 3
            │   └── (right) 6
            └── (right) 8

ノード 3 への (右→左) ジグザグの後。

└── 0
    └── (right) 9
        └── (left) 7
            ├── (left) 5
            │   ├── (left) 1
            │   │   └── (right) 3
            │   │       ├── (left) 2
            │   │       └── (right) 4
            │   └── (right) 6
            └── (right) 8

ノード 3 への別の (左→右) ジグザグの後。

└── 0
    └── (right) 9
        └── (left) 7
            ├── (left) 3
            │   ├── (left) 1
            │   │   └── (right) 2
            │   └── (right) 5
            │       ├── (left) 4
            │       └── (right) 6
            └── (right) 8

ノード 3 への (左→左) Zig-Zig の後。

└── 0
    └── (right) 3
        ├── (left) 1
        │   └── (right) 2
        └── (right) 7
            ├── (left) 5
            │   ├── (left) 4
            │   └── (right) 6
            └── (right) 9
                └── (left) 8

(右) ノード 3 への Zig の後。3 がルート位置にあるので、ここで停止します。

└── 3
    ├── (left) 0
    │   └── (right) 1
    │       └── (right) 2
    └── (right) 7
        ├── (left) 5
        │   ├── (left) 4
        │   └── (right) 6
        └── (right) 9
            └── (left) 8t) 6
                └── (right) 9
                    └── (left) 8

ツリーでノード 3 に再度アクセスしようとすると、すでにルート位置にあるため、展開する必要はありません。