问题标签 [splay-tree]

我已经实现了几个函数来旋转展开树中的节点，但它通过将相同的节点发送到不同的地方以某种方式破坏了我的树。他们将儿子旋转到父亲节点。爸爸的指针可能是过度的，但我想尝试这种方式。我在函数中使用那些将节点调整为根。

我做了一个伸展树，但我不明白如何从中删除最小元素，有人可以帮忙吗？

在一篇关于多分支树的论文中，它提到多分支树具有 O(loglogn) 竞争性。二叉搜索树具有 O(loglogn) 竞争性究竟意味着什么？为什么多杀树 O(loglogn) 具有竞争力？

所以我试图实现一个函数： func rsum(root, left, right) 这个函数接受一个范围的值，然后在一个展开树中返回该树中所有键的总和。我希望它在 O(log n) 中工作。

我试过这个：

虽然它在 O(log n) 中不起作用，但有更好的方法吗？

我有一个展开树，我已经实现了 range_sum(left,right)，它将树中的所有元素添加到从左到右的范围内，并且它在对数时间内工作，无论如何我可以制作一个函数 range_up(left,right ,delta) 将 delta 添加到从左到右范围内的每个元素并在对数时间内工作？

我正在 Splay Tree 节点上编写一些代码。不需要太技术性，我想实现一棵基础树和一棵支持左右子树反转的派生树。当前摘录如下所示：

这显然是行不通的，因为c[0]是 typenode并且没有 member r。不过，我知道c[0]of nodeonly points tonode和c[0]of reversable_nodeonly points to reversable_node。所以我可以做一些演员表：

但这看起来超级笨拙。有没有更好的方法在派生类中也可以在基类中使用自引用指针？

PS 整个代码如下所示：

所以基本上我们有一个节点是否反转的标志，当我们尝试旋转树时，我们将标志从节点向下推到它的子节点。这可能需要对 Splay Tree 有所了解。

PS2 它应该是一个库，但一些用例会是这样的：