Prolog binary tree tree test - parent parent parent node

Question

Prolog binary tree tree test - parent parent parent node

I'm new to Prolog, keep that in mind. I am trying to write a predicate to determine if a given term is a binary search tree. I understood this code:

is_btree(nil).
is_btree(node(N,L,R)) :-
   number(N),
   is_btree(L), 
   is_btree(R), 
   small(N, R),
   big(N, L).

small(N, nil).
small(N, node(M,L,R)) :-
   N < M,
   small(N, L),
   small(N, R).

big(N, nil).
big(N, node(M,L,R)) :-
   N > M,
   big(N, L),
   big(N, R).

This works fine until I draw a graph with a node on the right side that passes the condition “above the parent node”, but it is greater than or equal to the parent node of the parent node. In this case, Prolog reports an error.

Here is an example request that terminates unexpectedly:

?- is_btree(node(9,node( 3,node( 2,nil,nil),
                           node(10,nil,nil)),
                   node(12,node( 8,nil,nil),
                           node(15,nil,nil)))).
false.

A very similar problem occurs when some nodes on the left side above the parent node of the parent node are a situation that is shown in the following figure:

How can I check node values only with the value of their immediate parent node, but not the values of the parents of the parents?

+3

binary-tree prolog binary-search-tree

user3533469 07 . '16 17:55

5

repeat · Answer 1 · 2016-01-09T21:03:15+0000

, .

dcg : in-order tree-traversal

in_order(nil) --> [].
in_order(node(X,L,R)) --> in_order(L), [X], in_order(R).

clpfd list ( - )
```
chain(Zs, #<)
```

is_bintreeFD/1 :

< > : use_module ( (clpfd)). is_bintreeFD (T): - phrase (in_order (T), Zs), chain (Zs, # <).

:

?- is_bintreeFD(node(9,node( 3,node(2,nil,nil),node(10,nil,nil)),
                       node(12,node(8,nil,nil),node(15,nil,nil)))).
false.

?- is_bintreeFD(node(9,node( 3,node( 2,nil,nil),node( 8,nil,nil)),
                       node(12,node(10,nil,nil),node(15,nil,nil)))).
true.

repeat · Answer 2 · 2016-01-14T13:07:04+0000

, @WillNess, "[...] , , [...] chain phrase [...]".

lazy_chain/2 chain/2, prolog-coroutining, :

< > : use_module ( (clpfd)). lazy_chain (Zs, R_2): - (var (R_2) → instantiation_error (R_2) ; clpfd: chain_relation (R_2) → freeze (Zs, lazy_chain_aux (Zs, R_2)) ; → domain_error (chain_relation, R_2) ). lazy_chain_aux ([], _). lazy_chain_aux ([Z0 | Zs], R_2): - (Zs, lazy_chain_aux_ (Zs, R_2, Z0)). lazy_chain_aux _ ([], _, _). lazy_chain_aux _ ([Z1 | Zs], R_2, Z0): - (R_2, Z0, Z1), freeze (Zs, lazy_chain_aux_ (Zs, R_2, Z1)).

lazy_chain/2 is_bintreeL/2 :

< > is_bintreeL (T): - lazy_chain (Zs, # <), phrase (in_order (T), Zs).

... " "?

?- T = node(2, nil, node(1, nil, node(3, nil, node(4, nil, node(5, nil, node(6, nil, node(7, nil, node(8, nil, node(9, nil, node(10, nil, node(11, nil, node(12, nil, node(13, nil, node(14, nil, node(15, nil, node(16, nil, node(17, nil, node(18, nil, node(19, nil, node(20, nil, node(21, nil, node(22, nil, node(23, nil, node(24, nil, node(25, nil, node(26, nil, node(27, nil, node(28, nil, node(29, nil, node(30, nil, node(31, nil, node(32, nil, node(33, nil, node(34, nil, node(35, nil, node(36, nil, node(37, nil, node(38, nil, node(39, nil, node(40, nil, node(41, nil, node(42, nil, node(43, nil, node(44, nil, node(45, nil, node(46, nil, node(47, nil, node(48, nil, node(49, nil, node(50, nil, node(51, nil, node(52, nil, node(53, nil, node(54, nil, node(55, nil, node(56, nil, node(57, nil, node(58, nil, node(59, nil, node(60, nil, node(61, nil, node(62, nil, node(63, nil, node(64, nil, node(65, nil, node(66, nil, node(67, nil, node(68, nil, node(69, nil, node(70, nil, node(71, nil, node(72, nil, node(73, nil, node(74, nil, node(75, nil, node(76, nil, node(77, nil, node(78, nil, node(79, nil, node(80, nil, node(81, nil, node(82, nil, node(83, nil, node(84, nil, node(85, nil, node(86, nil, node(87, nil, node(88, nil, node(89, nil, node(90, nil, node(91, nil, node(92, nil, node(93, nil, node(94, nil, node(95, nil, node(96, nil, node(97, nil, node(98, nil, node(99, nil, node(100, nil, nil)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))),
   time((phrase(in_order(T),Zs),eager_chain(Zs,#<))).
% 210 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 4100201 Lips)
false.

?- T = node(2, nil, node(1, nil, node(3, nil, node(4, nil, node(5, nil, node(6, nil, node(7, nil, node(8, nil, node(9, nil, node(10, nil, node(11, nil, node(12, nil, node(13, nil, node(14, nil, node(15, nil, node(16, nil, node(17, nil, node(18, nil, node(19, nil, node(20, nil, node(21, nil, node(22, nil, node(23, nil, node(24, nil, node(25, nil, node(26, nil, node(27, nil, node(28, nil, node(29, nil, node(30, nil, node(31, nil, node(32, nil, node(33, nil, node(34, nil, node(35, nil, node(36, nil, node(37, nil, node(38, nil, node(39, nil, node(40, nil, node(41, nil, node(42, nil, node(43, nil, node(44, nil, node(45, nil, node(46, nil, node(47, nil, node(48, nil, node(49, nil, node(50, nil, node(51, nil, node(52, nil, node(53, nil, node(54, nil, node(55, nil, node(56, nil, node(57, nil, node(58, nil, node(59, nil, node(60, nil, node(61, nil, node(62, nil, node(63, nil, node(64, nil, node(65, nil, node(66, nil, node(67, nil, node(68, nil, node(69, nil, node(70, nil, node(71, nil, node(72, nil, node(73, nil, node(74, nil, node(75, nil, node(76, nil, node(77, nil, node(78, nil, node(79, nil, node(80, nil, node(81, nil, node(82, nil, node(83, nil, node(84, nil, node(85, nil, node(86, nil, node(87, nil, node(88, nil, node(89, nil, node(90, nil, node(91, nil, node(92, nil, node(93, nil, node(94, nil, node(95, nil, node(96, nil, node(97, nil, node(98, nil, node(99, nil, node(100, nil, nil)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))),
   time((lazy_chain(Zs,#<),phrase(in_order(T),Zs))).
% 52 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 1225664 Lips)
false.

, , :)

, lazy_chain/2 dcg , !

. ...

eager_chain/2:

eager_chain(Zs, R_2) :-
   (  var(R_2)                  -> instantiation_error(R_2)
   ;  clpfd:chain_relation(R_2) -> eager_chain_aux(Zs, R_2)
   ;  otherwise                 -> domain_error(chain_relation, R_2)
   ).

eager_chain_aux([], _).
eager_chain_aux([Z0|Zs], R_2) :-
   eager_chain_aux_(Zs, R_2, Z0).

eager_chain_aux_([], _, _).
eager_chain_aux_([Z1|Zs], R_2, Z0) :-
   call(R_2, Z0, Z1),
   eager_chain_aux_(Zs, R_2, Z1).

repeat · Answer 3 · 2016-01-08T06:57:28+0000

clpfd .

< > : use_module ( (clpfd)). : asserta (clpfd: full_answer),

is_bintree/1 bintree_in/2 :

< > is_bintree (T): - bintree_in (T, _). bintree_in (nil, LB-UB): -% LB-UB (LB, UB) LB # < UB. %, , LB < < UB bintree_in (node (Mid, L, R), LB-UB): - Mid # > LB, Mid # < UB, bintree_in (L, LB-Mid), bintree_in (R, Mid-UB).

^1,2 , OP:

| ?- bintree_in(node(9,node( 3,node(2,nil,nil),node(10,nil,nil)),
                       node(12,node(8,nil,nil),node(15,nil,nil))), _).
no

!

< > |? - bintree_in (node (9, node (3, node (2, nil, nil), node ( 8, nil, nil)), node (12, node ( 10, nil, nil), node (15, nil, nil))), _). _A inf..1, _B 16..?; % ( )

OK! :

| ?- bintree_in(T, 0-0).             % no solution (as expected)
no
| ?- bintree_in(T, 0-1).             % empty tree
T = nil ? ;
no
| ?- bintree_in(T, 0-2).             % singleton tree
T = nil ? ;
T = node(1,nil,nil) ? ;
no

, is_btree/1 "", bintree_in/2 ³ "test", ""!

, ( ) :

| ?- bintree_in(T, 0-3).             % T has less than 3 elements
T = nil ? ;
T = node(_A,nil,nil), _A in 1..2 ? ;
T = node(1,nil,node(2,nil,nil)) ? ;
T = node(2,node(1,nil,nil),nil) ? ;
no

| ?- bintree_in(T, 0-4).             % T has less than 4 elements
T = nil ? ;
T = node(_A,nil,nil), _A in 1..3 ? ;
T = node(_A,nil,node(_B,nil,nil)), _A#=<_B+ -1, _B#>=_A+1, _B in 2..3, _A in 1..2 ? ;
T = node(1,nil,node(2,nil,node(3,nil,nil))) ? ;
T = node(1,nil,node(3,node(2,nil,nil),nil)) ? ;
T = node(_A,node(_B,nil,nil),nil), _A#>=_B+1, _A in 2..3, _B in 1..2 ? ;
T = node(2,node(1,nil,nil),node(3,nil,nil)) ? ; 
T = node(3,node(1,nil,node(2,nil,nil)),nil) ? ;
T = node(3,node(2,node(1,nil,nil),nil),nil) ? ;
no

, bintree_in/2 is_btree/1!

is_btree/1 ; labeling/2 .

< > |? - call_time ((UB 2..12, indomain (UB), bintree_in (T, 0-UB), term_variables (T, Zs), ([], Zs), \ + is_btree (T) ; ), T_ms). T_ms = 6270?;

^{1:
(at at sicstus-prolog swi-prolog.
2:
prolog-toplevel
SICStus Prolog 4.3.2 (64- ).
3:
,
() , .}

repeat · Answer 4 · 2016-01-10T13:25:33+0000

@WillNess " " .

in_order_inf_sup//3 in_order//1 chain/2:

:- use_module(library(clpfd)).

in_order_inf_sup(nil, P, P) --> [].
in_order_inf_sup(node(X,L,R), P0, P) -->
   in_order_inf_sup(L, P0, P1),
   [X],
   { P1 #< X },
   in_order_inf_sup(R, X, P).

( ):

?- phrase(in_order_inf_sup(node(9,node( 3,node(2,nil,nil),node(10,nil,nil)),
                                  node(12,node(8,nil,nil),node(15,nil,nil))),_,_),
          Zs).
false.

?- phrase(in_order_inf_sup(node(9,node( 3,node( 2,nil,nil),node( 8,nil,nil)),
                                  node(12,node(10,nil,nil),node(15,nil,nil))),_,_),
          Zs).
Zs = [2,3,8,9,10,12,15].

Will ness · Answer 5 · 2016-01-08T00:47:31+0000

. BST BST.

- . - is_btree, -, small/big.

Both can be combined into one, but immediately the obvious solution will do exactly what you want, and thus succeed in such invalid BSTs:

is_bst(nil).

is_bst(node(N,L,R)):- 
   (  L = nil 
   ;  L = node(M,LL,LR), M < N, is_bst(L), ....
   ),
   (  R = nil
   ;  ...... 
   ).

To fix this, we must return another result from the tree traversal - this is the rightmost element of the tree - and use it in comparison for verification.

(edit: skipped that the last item also needs to be returned)

Prolog binary tree tree test - parent parent parent node

More articles: