Range function for values in a splay tree?

Question

I am a beginner at data structures. I am trying to write some pseudocode for a range function with splay trees: Range(S, A, B), which changes S to the set of all its members for which the key value C satisfies A ≤ C ≤ B. I know a splay trees fall into being types of binary search trees and implement their own splay operation. Basically, I am trying to return a range of values that are between A and B. However, I am having trouble understanding how I should do this, or where I should even begin, and what conditions I should check. I've read the definition of splay trees, and know they are like binary search trees with the move-to-front algorithm.

This is what I have so far:

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

I just feel somewhat lost after this point. I am not sure how to check the values of splay trees. Please let me know if I can provide additional information, or what directions I should go in.

Answer 1

According to 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.

However, since the "splay" operation applies only to random searches, the tree may be considered to be an ordinary "binary search tree".

The algorithm becomes,

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

That is, tree T is traversed, in order; and, for each item C meeting the condition, the item is added to array S. If no item meets the condition, an empty array is returned.

The For each, if not available in the implementation language, may be implemented using the algorithm described as in-order

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

where vist(node) is the place to test whether the item meets the condition.

Answer 2

This is pretty late, but from the term "change" in the question prompt, it seems like it is asking you to modify the S tree so that it has only the elements within range.

So I would do it like this: splay the tree around the lower bound, and drop the left subtree, since everything in the left subtree will be lower value than the lower bound. Then splay the tree around upper bound, then dropping the right subtree, since everything in the right subtree will be higher value than the upper bound.

Here is how I would write it, in pseudocode

//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

Hope this helps! This should run in O(logn) also