CODEWITHSUNDEEP
treeprologlogic
theantomc
theantomc

Reputation: 649

Find a element in binary tree in PROLOG

I am trying to implement this with Prolog to find an element in a binary tree.

elem1(tree(Element,void,void),Element).

elem1(tree(_Element,Left,Right),N) :-
  elem1(Left,N), 
  elem1(Right,N).

because I think that elem1 checks if root of my tree is an element that I search and this work with this output.

?- trace,elem1(tree(c,void,void),c).
Call: (9) elem1(tree(c, void, void), c) ? creep
Exit: (9) elem1(tree(c, void, void), c) ? creep
true

But in the recursive way like this: 

  ?- trace,elem1(tree(4,tree(1,void,void),tree(2,void,void)),1).
  Call: (9) elem1(tree(4, tree(1, void, void), tree(2, void, void)), 1) 
  creep
  Call: (10) elem1(tree(1, void, void), 1) ? creep
  Exit: (10) elem1(tree(1, void, void), 1) ? creep
  Call: (10) elem1(tree(2, void, void), 1) ? creep
  Call: (11) elem1(void, 1) ? creep
  Fail: (11) elem1(void, 1) ? creep
  Fail: (10) elem1(tree(2, void, void), 1) ? creep
  Redo: (10) elem1(tree(1, void, void), 1) ? creep
  Call: (11) elem1(void, 1) ? creep
  Fail: (11) elem1(void, 1) ? creep
  Fail: (10) elem1(tree(1, void, void), 1) ? creep
  Fail: (9) elem1(tree(4, tree(1, void, void), tree(2, void, void)), 1) ? 
  creep

  false.

seems that call in right way the (10) and check correctly the predicate, but after try to expand more and give me a failure.

I don't know why this happened, but the base case is working well, so I aspect that when find a element, exit and give me the true, because base predicate is valid.

Upvotes: 2

Views: 1326

Answers (1)

Guy Coder
Guy Coder

Reputation: 24976

Your code slightly modified to show use of AND (,) exagerated.

elem_01(tree(Element,void,void),Element).

elem_01(tree(_Element,Left,Right),N) :-
  (
    elem_01(Left,N)
  ,
    elem_01(Right,N)
  ).

Example:

?- elem_01(tree(4,tree(1,void,void),tree(2,void,void)),1).
false.

which gives incorrect result.

Corrected version which uses OR (;).

elem_02(tree(Element,void,void),Element).

elem_02(tree(_Element,Left,Right),N) :-
  (
    elem_02(Left,N)
  ;
    elem_02(Right,N)
  ).

Example:

?- elem_02(tree(4,tree(1,void,void),tree(2,void,void)),1).
true ;
false.

Correctly finds 1 in binary tree.

?- elem_02(tree(4,tree(1,void,void),tree(2,void,void)),3).
false.

Correctly shows 3 is not in tree.

Corrected version to show use of two clauses instead of OR (;).

elem_03(tree(Element,void,void),Element).

elem_03(tree(_Element,Left,_),N) :-
    elem_02(Left,N).

elem_03(tree(_Element,_,Right),N) :-
    elem_02(Right,N).

Example:

?- elem_03(tree(4,tree(1,void,void),tree(2,void,void)),1).
true ;
false.

Correctly finds 1 in binary tree.

?- elem_03(tree(4,tree(1,void,void),tree(2,void,void)),3).
false.

Correctly shows 3 is not in tree.

In your question you show the tree as

elem1(tree(4,tree(1,void,void),tree(2,void,void)),1).

e.g.

  4
 / \
1   2

and while it is a binary tree, it is not a proper binary tree where the keys on the left are less than the root and the keys on the right are greater than the root.

The reason you want the keys as such is that you can then use comparisons when searching so that you don't have to search the entire tree.

Your code works, but it must search the entire tree if the value is missing. If you have a very large tree and don't have a match then you can find that it is missing much faster if you build the tree correctly and add the comparisons into your code.

This is a proper tree for your example:

elem1(tree(2,tree(1,void,void),tree(4,void,void)),1).

e.g.

  2
 / \
1   4

Upvotes: 2

Related Questions