algorithm - splay 树中值的范围函数？

Question

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

这是我目前所拥有的:

Algorithm Range(Array S, int A, int B): array Set
S = new array(size) //Initialize an empty array of some size
if (A > B) then return NULL

我只是觉得有些失落。我不确定如何检查拉伸(stretch)树的值。请让我知道我是否可以提供更多信息，或者我应该去哪里。

Answer 1

根据 Wikipedia ,

A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time.

然而，由于“splay”操作仅适用于随机搜索，因此树可以被认为是普通的“二叉搜索树”。

算法变成，

Range (BSTree T, int A, int B)
  int Array S

  S ← Empty array
  If A <= B then
    For each C in T
      If A <= C and C <= B then
        Append C to S
  Return S

即依次遍历树T；并且，对于每个满足条件的项 C，将该项添加到数组 S。如果没有项满足条件，则返回一个空数组。

For each，如果在实现语言中不可用，可以使用描述为 in-order 的算法来实现

inorder(node)
  if (node = null)
    return
  inorder(node.left)
  visit(node)
  inorder(node.right)

其中vist(node)是测试item是否满足条件的地方。