1

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

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

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

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

4

2 回答 2

0

根据维基百科，

展开树是一种自我调整的二叉搜索树，具有最近访问的元素可以快速再次访问的附加属性。它在 O(log n) 摊销时间内执行插入、查找和删除等基本操作。

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

算法变为，

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在实现语言中不可用，则可以使用按顺序描述的算法来实现

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

vist(node)测试物品是否符合条件的地方在哪里。

于 2019-03-16T23:31:23.437 回答
0

这已经很晚了，但是从问题提示中的“更改”一词看来，它似乎是在要求您修改 S 树，使其仅包含范围内的元素。

所以我会这样做：围绕下限展开树，并删除左子树，因为左子树中的所有内容都将低于下限。然后围绕上限展开树，然后丢弃右子树，因为右子树中的所有内容都将高于上限。

这是我用伪代码编写的方法

//assumes S is the root of an actual tree with elements
function Range(node S, int A, int B)
    node temp <- Splay(k1, S) //splay around lower bound
    if (temp.key < k1) //makes sure that there are elements in tree that satisfies this
        temp <- temp.right
        if (temp == null) return //there are no key greater than A, abort!
        temp <- Splay(temp.key, S)

    temp.left <- null //drops left subtree, bc they are all going to be lesser value
    temp <- Splay(k2, temp) //splay around upper bound
    if (temp.key > k2)
        temp <- temp.left
        if (temp == null) return //there are no keys less than B, abort!
        temp <- Splay(temp.key, temp)

    temp.right <- null //drops all right subtree
    S <- temp

希望这可以帮助！这也应该在 O(logn) 中运行

于 2019-11-06T15:57:40.193 回答