Range query over a Binary Search Tree in Prolog

Question

I know how to perform a range query over a BST in procedural way (that is, in C++, Java and so on) but I find it difficult to convert into Prolog language.

The procedural way should be like:

http://www.geeksforgeeks.org/print-bst-keys-in-the-given-range/

any hint how to convert it into Prolog paradigma?

thanks a lot to everybody

mat · Accepted Answer · 2013-12-09 09:17:51Z

2

The declarative description from the site you cite can be directly translated to Prolog:

1) If key is greater than k1, then recursively call in left subtree.

Prolog translation:

bst(tree(Key, Left, Right), K1, K2, Value) :-
        Key > K1,
        bst(Left, K1, K2, Value).

2) If key is in range, then print the key.

We do not use impure predicates like "print", because they are not reversible. Instead, we use Prolog to report bindings on the toplevel for us:

bst(tree(Key, _, _), K1, K2, Key) :- between(K1, K2, Key).

3) If key is smaller than k2, then recursively call in right subtree.

I leave this as an exercise.

The query

?- bst(Tree, K1, K2, Value).

will yield on backtracking bindings for Value that are in the given range.

If you use constraints, you can use this predicate in all directions and also generate trees that contain a value.

answered Dec 9, 2013 at 9:17

mat

40.8k3 gold badges53 silver badges78 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Papatakis Over a year ago

It worked greatly .. but what about If I want to have all whole answer in one step in an output list? This solutions retrieves results one by one.

mat Over a year ago

It is easy to collect all solutions in Prolog: Use an all-solutions predicate like setof/3.

CapelliC · Accepted Answer · 2013-12-09 10:08:48Z

do the very same you do in C++ or Java. There are very high chances you'll got the right result, assuming that (in C++, to say), you wrote the minimal code required. That account usually for a recursive definition: something like

// pseudocode - Elem must implement operator<
struct BST<Elem> {
  bool find(const Elem e) { return find(root, e) }
private:
  bool find(Node n, Elem e) {
    if (!n) return false;
    if (n.payload() == e) return true;
    return n.payload() < e ? find(n.left) : find(n.right);
  }
}

The same search can be written manually unfolding the stack, by means of (duh) stack, then iterating

stack<Node> stack; stack.push(root);
while (!stack.isEmpty()) {
  Node n = stack.pop();
  // check found, return true
  // push left or right...
}

In Prolog the stack is 'embedded' in the language: just state what's the solution 'form': assuming a tree like t(Payload, Left, Right) with a default like t(0,-,-) you can do

% note: untested
bst(t(Payload,_,_), Payload). % found
bst(t(Payload,L,R), Sought) :- Sought @< Payload -> bst(L, Sought) ; bst(R, Sought).

A note on C++: I've uploaded on github (at loqt) an example of a declarative, non intrusive C++ interface on a raw pointer model (Agraph_t* and friends). With that interface, very simple to implement now that we have lambda in C++:

// live code here
void lqXDotScene::dump(QString m) const {
    qDebug() << m;
    cg->depth_first([&](Gp t) { qDebug() << "graph" << gvname(t) << CVP(find_graph(t)); });
    qDebug() << "nodes";
    cg->for_nodes([&](Np n) {
        qDebug() << "node" << gvname(n) << CVP(find_node(n));
        cg->for_edges_out(n, [&](Ep e) {
            qDebug() << "edge" << gvname(e) << CVP(find_edge(e)) << "to" << gvname(e->node) << CVP(find_node(e->node));
        });
    });
}

the line

    cg->depth_first([&](Gp t) { qDebug() << "graph" << gvname(t) << CVP(find_graph(t));

does a full visit. find_graph, find_ etc are member function: lambda it's very powerful.

Collectives™ on Stack Overflow

Range query over a Binary Search Tree in Prolog

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related