问题标签 [splay-tree]

在使用伸展树的绳索数据结构的标准实现中，节点将根据测量每个节点从字符串开始的位置的排名统计量进行排序，因此通常在二叉搜索树中找到的键将是不相关的，将他们不是吗？

我问是因为下图中显示的键（感谢维基百科！）是字母，一旦节点数量超过所选字母的长度，它们可能会变得不唯一。使用整数或完全避免使用键不是更好吗？

另外，谁能指出我在每次操作后重新计算排名统计的逻辑的良好实现？

据推测，如果拆分的索引位于附加到特定节点的子字符串中，例如，在上面节点 E 上的“Hel”和“llo_”之间，您将从 E 中删除子字符串，将其拆分并重新附加为两个孩子E. 对吗？

最后，经过一定次数的这样的操作，我想这棵树的叶子可能和字母一样多。跟踪它并根据需要修剪树（通过组合子字符串）的最佳方法是什么？

谢谢！

我需要使用展开树计算范围和。

我已经实现了 Insert、Find、Remove 和 Splay 方法，它们工作正常，但是我在计算树中给定范围的总和时遇到了麻烦。

注意：测试用例中的树非常深，我不能使用递归解决方案。

这是我在 C# 中的树类实现：

这是我的求和方法：

问题是在这种方法中，我需要复制我的原始树，但我不能复制，它总是会改变原始树，所以树会被弄乱。

如果您能帮助解决此方法或帮助我实施更好的方法，我将不胜感激。

我是数据结构的初学者。我正在尝试为具有展开树的范围函数编写一些伪代码：Range(S, A, B)，它将 S 更改为键值 C 满足 A ≤ C ≤ B 的所有成员的集合。我知道展开树属于二进制类型搜索树并实现自己的展开操作。基本上，我试图返回介于 A 和 B 之间的一系列值。但是，我无法理解我应该如何执行此操作，或者我什至应该从哪里开始，以及我应该检查哪些条件。我已经阅读了展开树的定义，并且知道它们就像具有移至前端算法的二叉搜索树。

这是我到目前为止所拥有的：

在这一点之后，我感到有些失落。我不确定如何检查伸展树的值。请让我知道我是否可以提供更多信息，或者我应该进入哪些方向。

我必须使用java实现splay树结构。给定一个名为 Node 的类，它具有：

1. 左，右孩子
2. 信息（一个整数）
3. 节点的高度

我的作业包括创建“插入”方法。

我已经尝试了一些策略，但到目前为止还没有奏效，我试图通过获取代码而不是通过一些可以帮助我的想法来获得一些帮助。

所以我一开始的策略是实现一个递归方法，像二叉搜索树一样插入信息，然后展开（使用伪代码）：

我不完全确定这个想法是否适用于锯齿形和锯齿形。

另一方面，我没有节点父节点的信息，所以我在如何进行 zig 和 zag 旋转时遇到了麻烦，我尝试使用 a.height==1，但这会有问题

我有一个像这样的递归 SplayTreeMap （自动生成）（伪代码）：

类条目如下所示：

我想要做的是将 1 添加到Entry('subpath', 'othercooltype').songs. 我试过map.update了，但没有成功（[ERROR:flutter/lib/ui/ui_dart_state.cc(148)] Unhandled Exception: type '(dynamic) => dynamic' is not a subtype of type '(SplayTreeMap<dynamic, dynamic>) => SplayTreeMap<dynamic, dynamic>' of 'update'）。我还尝试保存它的值，删除密钥并添加更新的密钥，但它有问题（有时有效，有时无效）。

我当前的代码：

我正在编写一个 Splay Tree 实现。代码在 VS 中编译得很好，但测试系统因 DEADLYSIGNAL 而失败。测试的具体输入是：

这是完整的代码：

VS 调试器没有告诉我导致此错误的原因。Sanitazier 将其描述为读取错误，但我无法确定它到底发生在哪个函数中。此外，完整的消毒剂输出：

希望有人帮忙。先感谢您。

在Mark Allen Weiss 的Data Structures and Algorithm Analysis in C++（第 4 版）中，在第 162 页的图 4.50 中，该书描述了将树的最左边的孩子与唯一的左孩子展开最终的样子。

我感到困惑的是这本书是如何从第 2 步到第 3 步的。以下是第 162 页图 4.50 中突出显示的步骤：

而我的第三步看起来像这样：

我的第四步也是最后一步是这样的：

我对这本书如何平衡树感到困惑。对我来说，当 1 超过 4 时，树的底部看起来像这样：

我的逻辑是发生平衡的根是 2。然后你会做一个左旋转，树的底部看起来像这样：

我做错了什么，还是我只是以一种不同但同样有效的方式来做这件事？我也很困惑，因为这本书的最后一棵树从 6 的根开始不平衡，而我的 4 的根没有不平衡。

展开树中的每个字典操作都使用展开操作将节点带到树的根部。这种展开操作的摊销效率通常使用潜在方法进行分析，并在许多在线资源（包括维基百科）页面中进行了描述。然后将该展开操作的摊销时间报告为 O(m lg n)。

但是，我在任何地方都找不到完整字典操作的实际分析，例如插入，删除，......这些操作中的每一个都使用除了展开操作之外，还通过树向下搜索以找到要插入的节点的正确位置或删除。只有找到该节点后，才能开始展开操作。

人们倾向于发表如下声明：

• “展开树操作的复杂度与关联展开的复杂度相同”
• [“对于我们的分析，我们注意到执行搜索、插入或删除的时间与相关张开的时间成正比”]，p。Goodrich 的书的 456 题为“C++ 中的数据结构和算法”

我有两个问题：

• 怎样才能得出这样的结论，即执行搜索的时间与展开的时间成正比？这种暗示向下遍历到节点的时间也与splay的平局成正比？
• 向下遍历的摊销时间效率是多少？它是一个常数吗，仅仅是因为你没有通过简单地向下遍历来改变树的结构（所以你的潜力保持不变）？这个常数不是比= N，因为这是最坏的情况吗？

一个人怎么能得出这个结论？

我正在尝试实现一个展开树。但是在由 splay() 函数调用的 left_rotate 和 right_rotate 函数中出现了分段错误。我已经尝试调试但没有任何线索。我在哪里做错了！我认为存在某种逻辑错误。这是我的代码：

splay_tree.h

节点.h

主文件

我正在尝试实现伸展树。代码进入无限循环打印

20 10 20 15 10 20 15 15 10 10 20 15
用于以下测试代码，它会不断重复。我试过调试，但我找不到哪里出错了。如果我继续以倾斜的方式插入节点，代码运行良好。例如：如果我最后不插入 1 它会很好，但是一旦它不倾斜就会产生问题。

这是我的代码

splay_tree.h

节点.h

主文件