问题标签 [splay-tree]

当我张开时，我正在研究一种正确的旋转方法。我有用于保存左孩子和左孩子右的值的节点。在我测试左孩子的权利为空但当我编译时我得到一个空指针异常的情况下。即使值为 null 也不应该将新节点分配给 null 而不是抛出空指针异常？

以下是我的作业

在我测试的情况下，树看起来像

x 是 3，所以 leftC 是 2，leftsRight 应该是 null 但它只是抛出空指针。

为什么它抛出空指针而不是仅仅将它分配给空？

我有一个程序，允许用户在二叉搜索树、展开树和红黑树之间进行选择。我为二叉搜索树编写了类，现在我正在研究展开树，但我意识到我与用户交互的方法仅适用于二叉搜索树。我对其进行了设置，以便它将创建用户选择的任何树的实例，但在我的代码中，我只使用用户选择二叉搜索树时将创建的变量。我的问题是如何做到这一点，以便我只创建用户选择的树的一个实例，以及我如何只使用一个变量，以便当我插入项目或在树上工作时，我不必添加更多条件语句不同的树？

这就是我现在所拥有的

正如你所看到的，我只填充了 myTree，如果用户选择了 bst，这将是创建的树。在while循环中我只在myTree上工作。

我怎样才能使它更通用，或者我的另一个想法是接受用户输入，然后创建该树的实例，然后将该实例传递给单独的方法，这样我仍然可以只使用 myTree ，因为它会引用该实例已传递给该方法，但我不确定如何将实例传递给另一个方法。这种方式似乎是最好的，但我不确定

任何帮助表示赞赏

我正在为展开树研究正确的旋转方法。当我尝试运行我的程序时，我不断收到空指针异常，但我不知道为什么。这是我的树

这是我得到空指针的地方，它在 lr 分配上。lr 应该为空，因为 2 没有权限，但节点不应该为空，然后程序应该继续运行吗？或者因为它的 null 我必须先检查 2 是否有权利？

这是问题所在：

令 T 为 n 个节点上的伸展树，令 x 为 T 的一个节点。考虑在 x 处的伸展操作。x下的子树是否必然平衡（即splay树中以x为根的子树的高度在splay操作后变成O(logn)）？

我花了很多时间，但仍然感到沮丧....感谢您的回答。

我已经实现了几种展开树算法。

比较它们的最佳方法是什么？

添加随机节点时比较执行时间是一个好的开始吗？

我还实现了一个二叉搜索树，它跟踪每个节点的访问量。我写了一个optimize()创建最优二叉搜索树的方法。
如果我们不打算修改搜索树，并且我们确切地知道每个项目将被访问的频率，我们可以构建一个最优二叉搜索树，这是一个搜索树，其中查找一个项目的平均成本（预期搜索成本）最小化。
我怎样才能在比较伸展树时涉及到这个？

在展开树的这个实现中，列出的makeEmpty()函数（删除所有元素）的时间复杂度为 O(n)。它的实现如下：

鉴于两者findMax和remove可能具有与树的高度成正比的时间复杂度，为什么在最坏的情况下这需要 O(n) 时间？

谢谢！

我正在尝试实现一个自上而下展开的 Splay 树，就像这里描述的那样（http://www.nocow.cn/index.php/Code:Splay_Tree/C）（第一个）。我已经实现了一个自下而上的展开版本，它还在每个节点处维护子树大小，其中子树是该节点的根节点（即 size = 1 + left->size + right->size）。

与每个展开操作一样，我将一个节点向上移动到根，没有必要在每次旋转时更新所有祖先。但是现在在自上而下的版本中，我不明白如何在每个节点（和其他类型的不变量）处维护这个子树大小的值，而不用每次旋转递归地更新祖先。

简而言之，当我进行自上而下的展开操作时，如何保持每个节点的子树大小？（如果有上面提到的页面上描述的 splay 操作的修改版本会很好）

展开树是一种自调整二叉搜索树。将节点插入展开树涉及将其作为叶子插入二叉搜索树中，然后通过“展开”操作将该节点带到根。

如果可以通过以某种顺序将其元素插入到最初为空的展开树中来生成二叉搜索树，那么我们就说二叉搜索树是“展开构造的”。

并非所有二叉搜索树都是可展开构造的。例如，下面是一个最小的不可展开构造的二叉搜索树：

给定二叉搜索树，确定它是否可展开构造的有效算法是什么？

这个问题的灵感来自关于 AVL 和 splay 树之间一致性的相关问题。

更多细节：我有代码可以从给定的序列生成一个展开树，所以我可以在 O(n!log(n)) 时间左右执行蛮力测试，但我怀疑多项式时间性能可以使用某种形式树结构上的动态规划。据推测，这样的算法将利用这样一个事实，即每个大小为n的展开构造树都可以通过将当前根插入到一些大小为n-1的展开构造树中来产生，然后做一些事情来利用重叠/同构子问题。

我想用这两个附加规则创建一个展开树：

这两个规则是否会改变展开树的访问时间（访问引理）？

如果不是，我该如何证明？

所以我是在插入一棵新树后实现 Splay 功能。但是，当我尝试插入多个整数时，它会显示分段错误（核心转储）然后退出。

谁能检查我的问题在哪里？