时间戳

首页 > 解决方案 > 展开树中值的范围函数？

algorithm - 展开树中值的范围函数？

问题描述

我是数据结构的初学者。我正在尝试为具有展开树的范围函数编写一些伪代码：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

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

标签： algorithmdata-structuresbinary-search-treepseudocodesplay-tree

解决方案

根据维基百科，

展开树是一种自我调整的二叉搜索树，具有最近访问的元素可以快速再次访问的附加属性。它在 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)测试物品是否符合条件的地方在哪里。

推荐阅读