algorithm - 无法弄清楚 splaying 是如何工作的

Question

我不明白展开是如何工作的。
我无法理解的部分是我们如何知道 a: i) zig ii) zig-zag 或 iii) zig-zig 必须完成。
如果我理解正确的话，这与路径中的当前节点有关。
如果它是根的 child 那么它是一个 zig 否则是 (ii) 或 (iii) 取决于当前节点的父节点和当前节点是否都是左(或右)子节点。到此为止。
现在我没有得到的部分:
当我们向下移动时，不是将中间节点“移除”到左子树和右子树中的过程，以便我们有一个中间树最终将成为搜索项的根吗？
然后，如果我们从一棵树开始，我们将不断地执行 zig 而不会执行其他操作，因为我们正在删除元素并且始终位于根部。
示例:

例如，如果我正在寻找 20，我会从根开始，然后向左走。所以当前节点有根作为父节点，我做了一个之字形。现在发生了什么？？我在 26 并向左走，但 26 不也是根吗？那我应该做一个之字形吗？
但是从我在这个例子中看到的，一个锯齿形正在完成，我不明白为什么。
有什么帮助吗？

Answer 1

根是指整棵树的根，而不是你展开的子树的根。因此，在您的示例中，12 是整棵树的根。

...

如果您想要一个示例，我最近用 Java 编写了一个 SplayTree。您可以找到代码 here .

splay 树的重要之处在于它们将最近插入/查询的节点向上(最多)移动到树中的两层。您必须根据它的祖父节点和父节点位置执行之字形、之字形或之字形。

当访问一个节点x时，对x进行splay操作，将其移动到根节点。为了执行 splay 操作，我们执行一系列 splay 步骤，每个步骤都将 x 移近根。

展开步骤的三种类型是:(g = grand parent，p = parent，x = node to splay)

• Zig 步骤:当 p 是根节点时完成此步骤。树旋转了在 x 和 p 之间的边上。
• Zig-zig 步骤:当 p不是根并且 x 和 p 要么都是右 child 要么是都留下了 child 。树在连接 p 的边上旋转它的父节点 g，然后在连接 x 和 p 的边上旋转。
• Zig-zag 步骤:当 p 不是根且 x 是右 child 时执行此步骤p 是左 child ，反之亦然。树在边缘旋转在 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

经过(右->左)Zig-Zag 到节点 3。

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

在另一个(左->右)Zig-Zag 到节点 3 之后。

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

经过(左->左)Zig-Zig 到节点 3。

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

经过(右)Zig 到节点 3。现在是时候停止了，因为 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，则不必展开它，因为它已经在根位置。