问题标签 [splay-tree]

通过一些练习来磨练我的二叉树技能，我决定实现一个展开树，如Wikipedia: Splay tree中所述。

我没有得到的一件事是关于插入的部分。

它说：

首先，我们在展开树中搜索 x。如果 x 不存在，那么我们不会找到它，而是找到它的父节点 y。其次，我们对 y 执行展开操作，这会将 y 移动到展开树的根部。第三，我们以适当的方式插入新节点 x 作为根。这样，y 要么是新根 x 的左孩子，要么是右孩子。

我的问题是：与文章中的其他示例相比，上述文字似乎过于简洁，这是为什么呢？似乎这里遗漏了一些问题。例如，在将 y 节点展开到根节点后，我不能盲目地将根节点替换为 x，然后将 y 作为左子节点或右子节点附加到 x 上。

让我们假设树中不存在该值。

我有这棵树：

我想插入 8。根据上面的描述，我将找到 6 节点，并且在正常的二叉树中，8 将作为 6 节点的右子节点添加，但是在这里我首先必须展开6 节点到根：

那么这两个显然是错误的：

在我看来，首先进行展开，然后将新值正确添加为根的唯一方法意味着我必须检查以下标准（将展开的节点添加为新根的左子节点）：

1. 我张开到根的节点小于新根（6 < 8）
2. 我展开到根节点的最右边的子节点也小于新根节点 (20 8)

但是，如果我要拆分我展开的节点，通过获取右子节点并将其附加为新节点的右子节点，我会得到：

但是，这种简单的改变是否总能给我一棵正确的树？我很难想出一个例子，但这会导致以下情况：

• 我要添加的新值高于临时根（我张开到根的节点），但也高于临时根的右孩子的最左边的孩子？

IE。一棵树在张开后基本上看起来像这样，但在我替换根之前？

我想添加 13，这将使新树像这样：

或者这永远不会发生？

我的第二个问题是这样的：将操作重写如下会不会容易得多：

首先，我们在展开树中搜索 x。如果 x 不存在，那么我们不会找到它，而是找到它的父节点 y。然后我们将新节点添加为父节点的左子节点或右子节点。第三，我们在添加的节点上执行 splay 操作，这会将新值移动到 splay 树的根。

强调我的以显示我所做的更改。

我正在尝试实现递归展开树，自下而上。我递归到需要展开的节点，然后找到该节点的父节点和祖父节点。然后我可以根据情况进行曲折或曲折。问题是完成此操作后，我将已展开一次的节点返回到上一个递归调用。之前的递归调用引用了节点的父节点，现在是该节点的子节点。我如何在上升时递归展开节点？

对于我的算法和数据结构课程，我的任务是在 Haskell 中实现一个展开树。我的展开操作算法如下：

1. 如果要展开的节点是根，则返回未更改的树。
2. 如果要展开的节点距根节点只有一层，则执行 zig 操作并返回结果树。
3. 如果要展开的节点距离根节点有两层或更多层，则对从该节点开始展开子树的结果执行 zig-zig 或 zig-zag 操作，并返回结果树。

根据我的老师，这是有效的。然而，维基百科对展开树的描述说之字形步骤“将仅作为展开操作的最后一步完成”，而在我的算法中，它是展开操作的第一步。

我想实现一个展开树，它最后而不是第一个执行 zig 操作，但我不确定如何最好地完成。在我看来，这样的算法会变得更加复杂，因为在确定是否应该执行 zig 操作之前，需要如何找到要展开的节点。

如何在 Haskell（或其他一些函数式语言）中实现这一点？

例子

在此示例中，我们搜索值 4，提示我们将其展开到树的顶部。

我的算法（zig作为第一步）

维基百科算法（zig 作为最后一步）

两棵树都是有效的，但它们有不同的结构。我想用函数式语言实现第二个，最好是 Haskell。

我现在正在学习数据结构课程，我们学习了 2-3-4 树和展开树。我想知道在什么情况下你会使用 2-3-4 树而不是 splay 树？它们都是自我平衡和排序的，所以我看不出它们之间有太大的区别。

我正在阅读伸展树的基础知识。一次操作的摊销成本是 O(log n) 超过 n 次操作。一些粗略的基本想法是，当您访问一个节点时，您将其展开，即您将其带到根目录，以便下次快速访问它，并且如果节点很深，它会增强树的平衡性。

我不明白树如何为此示例输入执行摊销 O(log n)：

假设已经构建了一个包含 n 个节点的树。我接下来的 n 次操作是 n 次读取。我访问深度为 n 的深度节点。这需要 O(n)。确实，在此访问之后，树将变得平衡。但是说每次我访问最新的深度节点。这永远不会小于 O(log n)。那么我们如何才能补偿第一次昂贵的 O(n) 操作并将每次读取的摊销成本变为 O(log n)？

谢谢。

在阅读有关展开树的信息时，我发现了一些关于展开节点“X”的等级和维基百科中的摊销成本的表达。它给出为 { 我们可以通过以下方式限制任何锯齿形或锯齿形操作的摊销成本：

其中x是向根移动的节点，下标“f”和“i”分别表示操作之后和之前。当对整个展开操作求和时，它会伸缩到 3(rank(root))，即 O(log n)。由于最多有一个 zig 操作，这只会增加一个常数。}

我无法解释这一点。请有人详细解释上述内容。如果可能的话，举一些例子。

请提供一些链接以解释伸展树的其他定理

谢谢

一些二叉树数据结构（例如Splay树）将在读取时重新平衡以将最近访问的项目移向根，从而可以减少后续查找时间。

标准容器（std::map, std::set）是否允许这样做？

至少一个问题是线程安全。以前，我认为只要您只在标准容器上执行只读操作，就可以安全地从多个线程执行此操作而无需引入互斥锁/锁等。也许我需要重新考虑一下？

我知道通常红黑树用于标准树容器，并且这些数据结构通常不会在读取时修改。但是，修改后的假设实现是否符合要求？

我的 c++-standards-foo 需要改进，但我不确定当前标准是否解决了容器的线程安全问题。这有什么不同c++0x吗？

我正在阅读 Mark Allen Wesis 的数据结构和算法中的伸展树

张开策略类似于轮换的想法，只是我们对如何执行轮换更有选择性。我们仍将沿访问路径自下而上旋转。让 x 是我们正在旋转的访问路径上的（非根）节点。如果 x 的父节点是树的根，我们只需旋转 x 和根。这是沿访问路径的最后一次旋转。否则，x 既有父母（p）又有祖父母（g），有两种情况，加上对称性，需要考虑。第一种情况是 zig-zag 情况，这里 x 是右孩子，p 是左孩子（反之亦然）。如果是这种情况，我们执行双重旋转，就像 AVL 双重旋转一样。否则，我们有一个 zig-zig 情况：x 和 p 要么都是左孩子，要么都是右孩子。

在上面的文字中，作者所说的“有两种情况加对称”是什么意思？给出了两种情况，但这里的对称性是什么？

谢谢！

我正在研究各种树，遇到了 AVL 树和张开树。我想知道

1. AVL树和splay树有什么区别？
2. 我们选择这些树的依据是什么？
3. 这些树的正面和负面是什么？
4. 这些树在大 O 符号方面的表现如何？

我正在尝试在java中做一个自下而上的splay树。但不知何故，当我构建一棵树、添加几个元素并尝试将插入的节点展开到顶部时，我的旋转方法中会出现空指针异常。谁能告诉我为什么会出现这个错误？

基本上，我有这个带有左指针、右指针、父指针、根节点和 splayNode 持有者的通用 SPTNode 类。它还具有用于单次旋转、ZigZig 旋转、ZigZag 旋转、splay 和插入方法的方法。

这是我的比较器类：