问题标签 [splay-tree]

我正在实现一个 splaytree 来保存单词及其频率，并选择创建一个 Pair 类来保存每个单词频率（键值）对。也就是说，splaytree 的每个节点都持有一对 Pair 类。Pair 类如下所示：

Splaytree：

并且有 BinaryNode 类。

我遇到的问题是如何将每个单词和频率对放入树中，并检查该对是否已经存在，如果存在，将频率提高一倍。我逐行读取文本文件并将每一行拆分为单词，然后执行 countWords() 方法，该方法现在一团糟：

我知道这并没有真正起作用，我需要帮助来弄清楚我应该如何实例化 SplayEntry 类以及以什么顺序？我还希望该方法对于 words 数组中的每个单词，检查它是否存在于树内（包含）的 SplayEntry 中，如果该单词是新单词，则频率将为 1，否则频率将为是+1。最后，我只是将新的 SplayEntry 添加到 Splaytree 中，然后将其放入适当的节点中。

现在我只是因为在同一段代码上工作了太多时间而不是必要的时间而使自己感到困惑，我非常感谢一些可以引导我朝着正确方向前进的指针！

如果我没有说清楚，请告诉我。

我试图在网上找到一个小程序来测试伸展树，但到目前为止我发现的没有一个能满足我的需要。

我需要一些可以输入已经构建的展开树的东西。我有初始树，但无法使用插入构造它，因为我不知道它的顺序。

理想情况下，我正在寻找一个拖放小程序。

在Splay Trees Wikipedia 页面上，据说（在“优势”部分）：

可以创建 splay 树的持久数据结构版本——它允许在更新后访问先前版本和新版本。这在函数式编程中很有用，并且每次更新都需要分摊的 O(log n) 空间。

这是为什么？函数式编程如何特别使用持久的 Splay 树？

我不太明白为什么 splay 树数据结构中的旋转不仅考虑了评级节点的父节点，还考虑了祖父节点（之字形和之字形操作）。为什么以下不起作用：

例如，当我们向树中插入一个新节点时，我们检查是插入左子树还是右子树。如果我们插入到左边，我们将结果向右旋转，右子树反之亦然。递归它会是这样的

那应该避免整个“张开”过程，你不觉得吗？

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

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

我一直在尝试学习一些数据结构的来龙去脉，并且试图让二叉树能够正常工作。每次我运行以下代码并且我正在寻找的节点超过根时它告诉我它在那里，然后只是从根向下删除整个边。如果节点仅从顶部向下一层，则它可以正常工作。

我不确定出了什么问题，但我想这与我的旋转功能有关。我让它在我之后建模的插入函数中正常工作。

我已经建立了一棵张开的树，我试图将它反向打印出来，这样当你把头转向左边时，你可以以正常的方式看到树。我已经编写了以下代码，它输出的树有点正确，但是它在最右边的节点上添加了额外的空格，并且它没有为应该放置在根节点下方的所有子节点添加空格：

我觉得这可能是我的递归或缩进加减放置的错误。

我的代码是

当我调用它在根部旋转这样的树时：

它删除了 4 和 1 并使 5 成为 7 的左根。我尝试将该方法设置为 void 方法，但这似乎也不起作用。我这样做是完全错误的吗？

好的，这里是 splay 算法，如果你想检查的话。

这是我的伸展功能：

以下是 Zig (Single Rotate Left) & Zag (Single Rotate Right) 的方法。

&这是我的**问题。首先，我只在搜索功能中展开。即如果找到具有特定密钥的节点，则展开。

我的搜索功能：

如果节点是根的子节点，则以下工作正常。- Zig Single - Zag Single 但是，一旦我们关闭一个节点，问题就开始了。我无法成功执行任何这些事情。 之字形 - 之字形 - 之字形 - 之字形 - 之字形

这是样本树。（之字形案例）

当搜索到 5 时，答案应该是。

但我的输出变成：

无法弄清楚是什么问题。试运行这东西 100 次，但是。:( 任何和所有帮助表示赞赏。在此先感谢

是否存在这样的数字序列（1-7，所有数字都使用，每个数字仅一次），可以形成相等的 AVL 和展开树？