问题标签 [splay-tree]

我正在尝试为 splay 树编写 C++ 模板结构，但是当我尝试测试代码时，我得到了非常奇怪的结果。

这是我的模板代码：

我正在使用它来测试它：

我插入了元素 2，然后将根节点的值打印了两次。不知何故，这两张照片给了我两个不同的值（ http://ideone.com/RxZMyA的 Ideone 中的 2 和 10 ）。当我在计算机上运行程序时，它给了我 2 和 1875691072。在这两种情况下，当在 2 之后插入 3 时，根节点的左孩子是一个空指针，而它应该是一个包含 2 的节点对象。

有人可以告诉我为什么在两次打印相同的东西时会得到两个不同的值，以及我可以做些什么来使我的 splaytree.add() 函数按预期工作？谢谢！

我刚刚完成了一项考试，在那里我使用了中序遍历来检查我的一个展开树中的正确节点顺序。这是有效的吗？

我需要帮助理解张开树中之字形和之字形旋转的具体示例。我在一本书、维基百科以及其他一些在线资源中阅读过它们，虽然当它们应用于简单的树（即节点很少的树）时我可以理解它们，但当我看到示例时我会迷路其中应用于更大的树（即具有更多节点的树）。

特别是，我不明白这两个例子中的至少一个：

示例 1

（这不是完整的例子，但这是我不明白的部分）

我们可以在（1）中看到即将展开的节点是左孩子的右孩子，因此我们必须做一个之字形。因此，我可以理解 (1) 和 (2) 之间发生了什么，其中展开的节点现在已经取代了它的父节点。据我了解，整个锯齿形操作都发生在那里。所以第一次展开结束了，我们仍然需要展开节点，直到它位于树的根部。

我不明白（2）和（3）之间会发生什么。在 (2) 中，展开的节点是左子节点的左子节点，因此我期望进行 zig-zig 操作，其中展开的节点围绕其祖父节点旋转，即 (20, Z)。相反，幻灯片显示与其父级 (10, A) 的旋转。为什么？我所期望的是，我们的展开节点 (8, N) 做了一个 zig-zig 并因此取代了 (20, N) 的位置，它是它的祖父母，也是根。为什么家长反而参与其中？

在我找到此示例的资源（我的讲师的幻灯片）中，锯齿形旋转被描述为“与其父级一起旋转节点，然后与其祖父级一起旋转节点”。这就是这里发生的事情吗？这就是为什么在（2）和（3）之间，（8，N）随（10，A）而不是（20，Z）旋转的原因吗？

我对这个描述很困惑，因为 zig-zig 旋转被描述为“旋转节点与其祖父节点，然后旋转节点与其父节点”。但是，每次我看到一个 zig-zig 旋转的例子时，总是只有一个与节点的祖父节点的旋转，仅此而已。我从来没有见过2轮换。

然后是另一个例子：

在该示例中，展开操作涉及 zig-zig。如您所见，只有 1 次旋转。然后是第二次展开，因为被访问的节点仍然不在根位置。

我在这里所期望的是：

• 提供的 zig-zig 和 zig-zag 的描述都是正确的，因此在第二个示例中会有 2 次旋转：一次围绕节点的祖父母，然后围绕其父节点。
• 或者，提供的描述是错误的，因此第二个示例是正确的，但第一个示例不是因为我们在节点处于锯齿形位置时使用其父节点而不是其祖父节点旋转节点。

你能告诉我这两个例子中是否有任何一个是错误的，哪个是错误的？如果他们都没有错，我错在哪里？

谢谢您的帮助。

PS：很明显我是一名学生，我只想告诉你，我不是在作业的背景下问这个问题，因此我没有作弊。然而，我下周一有一个考试，我希望在我参加考试之前澄清任何误解。

https://youtu.be/G5QIXywcJlY?t=31m47s

在 31:47，我相信他执行了双重右旋，其中 5 是祖父母，4 是父母，1 是孩子。双右旋后，他有 4 作为 5 的右孩子。

我正在实现一个展开树。插入效果很好，但是当我尝试以之字形或之字形方式张开插入的节点时，我总是会遇到分段错误。当要展开的节点没有祖父母时使用左右旋转，效果很好。

这是右曲之字形旋转的代码。如果我这样做，例如

我得到了 j 和 p 的无限循环。insert 的第一个参数是 key，第二个是 rank（用于按顺序遍历）。

因此，在前面的示例中，在展开之前，树看起来像： z j p

由于 z 插入位置 1，因此 j 插入位置 1，将 z 移动到位置 2，依此类推。

这是我用于右转的 zig-zig 代码。

我已经追踪了它，它似乎应该正确地旋转给我。不应该发生无限循环的地方。但既然是这样，我会假设 j 和 p 以某种不应该的方式连接在一起。比如 j 有 p 作为它的左孩子，但是 p 由于某种原因有 j 作为它的一个孩子。

我一直在尝试实现splay树，但到目前为止没有成功。以前我成功实现了二叉搜索树和avl树，因为splay树是二叉搜索树的变体，所以插入代码和旋转代码很好。唯一的问题我面临的是每次插入节点时将节点向上移动到根。这是我的代码

我认为我的 moveUp() 方法出了问题。但我似乎无法弄清楚到底出了什么问题？

我正在为展开树编写代码，但我对展开树的删除方面有疑问。在互联网上研究它之后，这是我发现的：

首先搜索要删除的元素并将其展开到顶部。然后执行以下操作

1. 如果根（将元素展开到顶部之后）同时具有左右子节点，则删除根，这样您现在就有两个子树。在左子树中，找到最大的元素并将其展开到顶部，然后将其连接到右子树的根。
2. 如果根没有左孩子但有右孩子，则删除该根并将右子树的根作为新根。

但是如果根没有正确的孩子怎么办？所以我删除根，让左子树的根成为新的根？

还有其他需要我注意的条件吗？

如果有帮助，我在下面编写了删除代码。

我已成功通过 StreamBuilder 取回数据，需要对其进行排序。如何按键对快照数据的 Map 进行排序？另外，如果您举一个这样做的例子，我的价值也会有所帮助。我想我想做一个 SplayTreeMap，但如果有更好的方法请提供。这是我的字典...

我想通过按键显示它...... Vid1，Vid2，Vid3......

或通过诸如等级之类的值，即... Vid1：等级“1”，Vid2：等级“2”，Vid3：等级“3”...

如果要按该顺序插入 n 个键 1,2,…,n，

（一个）。到正常的 BST（二叉搜索树）

(b)。到张开树

在每种情况下 (a), b) 的复杂性是多少？

这两种情况都是 O(log n) 吗？还是 (a) 的 O(log n) 和 (b) 的 O(M log n) ？

我已经学习了Treap和Splay 树，并使用它们解决了一些问题。
理论上，它们的平均复杂度为O(log n)，但在最坏的情况下，Treap 的复杂度为O(n)，而Splay 树的平均复杂度为 O (log n)。

Treap在哪种情况下会出现最坏的情况（因为它的优先级是随机选择的），并且Treap真的比Splay 树慢吗？我已经使用 Splay tree和Treap解决了 SPOJ 上的一些任务，使用Treap的解决方案比使用 Splay tree的解决方案要快一些（大约0.2s）。那么哪个实际上更快，我应该主要使用哪个以及何时使用？