问题标签 [splay-tree]

当我们使用展开树时，我有一个疑问，最后访问的元素将到达根节点。考虑我的树是

当我执行中序遍历时，输出将是

所以这里最后访问的元素是8，因为我有疑问，所以8将是最后访问的节点，所以我们想8作为根节点移动还是不移动？

考虑我的树是这样的

在那里，当我们搜索一个元素2时，将执行 zigzig 操作，所以首先旋转parent and ancestor of 2，然后旋转 a parent and 2。

在同样的情况下，考虑到我们正在搜索4，那个时候会执行 zigzag 操作。在那个第一个我们旋转4 and its parent然后4 and its ancestor将被旋转。

为什么我们这样做，在锯齿形中，为什么我们不旋转parent and ancestor而不是searching node and parent.

请解释一下？？提前致谢。

我已经阅读了有关 Splay 树的信息，发现有两种构建 Splay 树的方法。他们是

1. 自下而上
2. 自顶向下

所以我需要知道这两种方法及其工作有什么区别？

我想知道是否有一种方法可以构建支持恒定时间 get-min、delete-min 和合并操作的优先级队列结构。我不关心插入的时间复杂度，它不必支持减少键操作。我在（坏）伪代码中的用例：

我考虑过展开树（特别是https://cs.stackexchange.com/questions/524/does-there-exist-a-priority-queue-with-o1-extracts）和斐波那契堆，但它们没有t 似乎满足这些要求。

我想尝试在 Splay 树上执行最坏情况的序列。

但是 Splay-trees 的最坏情况序列是什么？考虑到插入树的键，有什么方法可以轻松计算这个序列？

任何人都可以帮助我吗？

我正在尝试打印一棵张开树，但我不知道我在哪里弄错了。displayTree 方法适用于 BST 和 AVL，但不适用于展开树。谁能帮我这个？

这是我的 SplayTree：

这是我的树节点：

这是我的结果：

这是序列 20,10,5,30,40,57,3,2,4,35,25,18,22,27 我已经尝试过将每个新插入的节点都设为根，但它不起作用。谁能给我一步一步的解释？

首先，我是编程新手，所以我希望得到简单且解释清楚的答案。其次，这是一个非常具体的问题，我不希望版主和其他用户将这个问题作为离题或过于宽泛而结束。

无论如何，我想使用某种数据结构在 java 中实现 Huffman 编码。但是，但是，我正在考虑使用 splay 树，因为它不会在我的课程大纲中涵盖，而且我想学习一种新的数据结构。现在的主要问题是霍夫曼编码算法是否首先需要展开树数据结构？

在基于 Huffman 的数据压缩项目中，我可以使用 splay 树做什么？或者您更愿意为这个项目建议一个更好的（因为它的效率和创造性，因为它是独一无二的，而且很少有人听说过）数据结构？

谢谢

我编写了一个展开树。节点是这样表示的。

现在，我需要知道一定范围内树中所有数字的总和。为此，我实现了以下名为summation.

ret是一个全局变量，在调用函数之前int被初始化。&两个参数定义范围（包括）。0summationsted

该summation函数的工作复杂度为 O(n)。任何人都可以为此建议更快的实施吗？

两周前，我完成了一个展开树的实现，它允许基本功能，如插入、删除、查找键和获取三者的一系列元素的总和。您可以在此处找到此实现作为此问题的参考或出于好奇。

作为一项额外的任务（它是可选的，它是过期的，我解决这个问题不是为了一个成绩，而是因为我相信它是一个有用的数据结构不容易“谷歌关于它”），我被要求实现一个 Rope 数据结构来操作字符串，因此如果字符串是“warlock”并且给定的键是 0 2 2，那么字符串将是“lowarck”（0 2 是子字符串“war”，“lock”是删除“war”后剩下的内容，然后插入它在第二个字符之后变成“lo”+“war”+“ck”）。这只是一个查询，但对于 300k 字符长的字符串，它最多可以查询 100k，所以一个简单的解决方案是行不通的。

我的第一个疑问是初始化树（对于那些已经阅读要点的人，我将使用 Node 而不是 Vertex，以便大多数人易于理解）。

这是 Node 类和 NodePair 类：

之后，我以这种方式创建树：

这会创建一个非常不平衡的树，其中字符串的第一个字符（作为 node.key）具有 node.size 1 并且是最左边的孩子；字符串的最后一个字符是 size=sb.length() 的根。

我不完全确定这是否正确初始化。我用键和大小做了一个中序遍历打印，我得到了整个字符串的大小顺序，这是我所期望的。

之后，我修改了 Update 方法：

为此：（基于 CLRS 第 14.1 章）

然后是find方法，来自原文：

为此：（基于 CLRS 第 14.1 章的 Order Statistics-SELECT）

但是，此时我已经遇到了问题，因为如您所见，原始 find 返回一个 NodePair，而此方法返回一个 Node。根据讲师对 NodePair 的解释是：

返回结果和新根的对。如果找到，result 是指向具有给定键的节点的指针。否则，result 是指向具有最小较大键的节点的指针（顺序中的下一个值）。如果键大于树中的所有键，则结果为空。

这使我的拆分方法变得复杂，因为它使用 Find 方法来查找要拆分的节点。除此之外，我在这个 find 方法中获得了 NullPointerException，从其他学生那里我了解到，为了避免其他错误，我们应该使用非递归版本，所以基本上我需要实现 OS-Select 的非递归版本，它返回一个NodePair 作为以前的 find 方法或修改我的 split 方法是：

如您所见，find 方法被分配给 NodePair findAndRoot。我相信除了将 OS-Select 转换为非递归之外，我的主要问题是要了解 NodePair 使用之前的 find 方法和 split 方法的方式。

最后，这是我接收树和键并操作它们的方法的实现：

正如您必须从我的代码中意识到的那样，我是一个只有 5 个月开始学习编程的初学者，我选择了 Java，所以从我收集到的信息中，我了解到这种类型的数据结构更多地处于中间状态 -专家级别（我已经很惊讶我能够实现以前的 splay tree。所以请在你的回答中考虑我的初学者级别。

PD：这是非递归 OS-Select 的伪代码版本，仍然有 NullPointerException..