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

Question

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

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

Answer 1

他们所说的根是指整个树的根，而不是你正在展开的子树的根。因此，在您的示例中，12 是整个树的根。

...

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

展开树的重要之处在于它们将最近插入/查询的节点（最多）在树中向上移动两级。您必须根据其祖父节点和父节点位置执行 zig、zig-zig 或 zig-zag。

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

三种类型的展开步骤是：（g = 祖父，p = 父，x = 展开的节点）

• Zig Step：当 p 是根时完成此步骤。树在 x 和 p 之间的边缘上旋转。
• Zig-zig Step：当 p 不是根并且 x 和 p 都是右孩子或都是左孩子时，执行此步骤。树在连接 p 与其父节点 g 的边上旋转，然后在连接 x 和 p 的边上旋转。
• Zig-zag Step：当 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

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

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

经过（左->左）之字形到节点 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，则不必展开它，因为它已经在根位置。