====== Search tree ======
{{tag>trees searching}}
===== Description =====
Finding an item in a binary dictionary.

**Source**:  PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.
===== Download =====
Program source code: {{search_tree.pl}}
===== Listing =====
<code prolog>
% Figure 9.7  Finding an item X in a binary dictionary.


% in( X, Tree): X in binary dictionary Tree

in( X, t( _, X, _) ).

in( X, t( Left, Root, Right) )  :-
  gt( Root, X),                    % Root greater than X
  in( X, Left).                    % Search left subtree 

in( X, t( Left, Root, Right) )  :-
  gt( X, Root),                    % X greater than Root
  in( X, Right).                   % Search right subtree

gt(A,B):-A > B.</code>
===== Comments =====