Prolog二叉搜索树测试-不需要父节点的父节点比较

Question

我是Prolog的新手，请注意。 我尝试编写一个谓词来确定某个给定术语是否为二叉搜索树。我想出了以下代码：

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).

在测试一个具有右侧节点的图表时，如果该节点满足“高于父节点”的条件，但它高于或等于父节点的父节点，则会导致失败。在这种情况下，Prolog会报告失败。

以下是一个意外失败的示例查询：

?- 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.

当左侧某个节点高于父节点的父节点时，会出现非常相似的问题——如下图所示：

如何仅通过它们直接的父节点的值，而不是父节点的父节点的值，来检查节点的值？

- user3533469

---

但它应该失败。那棵树是一个无效的BST，而你的谓词测试的是有效的 BSTs。 - Will Ness

我们应该使用显式区间算术吗？滥用FD域似乎也是一个选项，但那对我来说太过于hackish。使用2个FD变量（Alpha，Omega）来表示区间似乎更有前途... - repeat

@repeat 我会在我的回答中坚持简单的东西。 :) - Will Ness

@WillNess。现在是凌晨2点，是我开始宣传的最佳时机 :) - repeat

Answer 1

这个回答是对先前的回答的直接跟进，特别是针对@WillNess的评论，建议“[...] 交换两个目标，以便在失败时尽快停止遍历 [...] 将chain放在phrase之前 [...]”。 lazy_chain/2类似于chain/2，但利用prolog-coroutining等待足够实例化：

:- use_module(library(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))
   ;  otherwise                 -> domain_error(chain_relation, R_2)
   ).

lazy_chain_aux([], _).
lazy_chain_aux([Z0|Zs], R_2) :-
   freeze(Zs, lazy_chain_aux_(Zs,R_2,Z0)).

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

这段代码是关于编程的，使用了Prolog语言中的clpfd库。它定义了一个懒惰链（lazy chain）的谓词，其中包含一些条件判断和递归调用。如果传入的参数不符合要求，则会抛出相应的错误。

基于 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
懒惰是胜利者-至少在上述情况下如此：)
但请注意，使用 dcg与lazy_chain/2可能会导致难以发现的错误！
为了获得更强大的解决方案，请参见this alternative answer...



为了完整起见，这是eager_chain/2的源代码:

eager_chain(Zs, R_2) ：
   （var（R_2）-＆gt; instantiation_error（R_2）
   ; clpfd：chain_relation（R_2）-＆gt; eager_chain_aux（Zs，R_2）
   ; 否则 -＆gt; 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 2

这是一个略有不同的解决问题的方法。

1.使用dcg收集元素：按顺序树遍历 in_order(nil) --> []. in_order(node(X,L,R)) --> in_order(L), [X], in_order(R).

2.使用clpfd关联相邻的列表元素（它们都是有限域变量）

chain(Zs, #<)

让我们把它们放在一起，像这样定义is_bintreeFD/1:

:- use_module(library(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

---

很好！是否有可能在失败时尽快停止遍历，将两个目标交换位置？将“chain”放在“phrase”之前？ - Will Ness

Answer 3

在本答案中，我们使用clpfd进行声明性整数算术。

:- use_module(library(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 LB, Mid #< UB, bintree_in(L, LB-Mid), bintree_in(R, Mid-UB).

首先，我们测试OP给出的树：^1,2

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

让我们修复树并再次检查！

| ?- 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 in inf..1, _B in 16..sup ? ;      % （有点笨拙）
不行

好的！接下来是一些特殊情况：

| ?- bintree_in(T, 0-0). % 没有解决方案（如预期） 没有 | ?- bintree_in(T, 0-1). % 空树 T = nil ? ; 没有 | ?- bintree_in(T, 0-2). % 单节点树 T = nil ? ; T = node(1,nil,nil) ? ; 没有

请注意，虽然is_btree/1只能“测试”，但bintree_in/2可以同时“测试”和“生成”！

因此，让我们在一个小的域中生成（所有可能的）特定大小的二叉树： | ?- bintree_in(T, 0-3). % T 元素个数小于3 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) ? ; 无解 | ?- bintree_in(T, 0-4). % T 元素个数小于4 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) ? ; 无解

最后，我们使用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), labeling([], Zs), \+ is_btree(T) ; true ), T_ms). T_ms = 6270 ? ; 否

---

^{脚注1： 此答案中的代码在sicstus-prolog和swi-prolog上运行。
脚注2： 所有prolog-toplevel输出均为SICStus Prolog 4.3.2（64位）的输出。
脚注3： 它不仅可以生成和测试，而且可以（几乎）任意混合，因为它可以处理部分实例化的术语。}

- repeat

---

哇，谢谢提供解决方案，但我真的认为这种类型的树也可以有效... :D 抱歉各位 - user3533469

Answer 4

在对此前一个回答的评论中，@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].

注意：本文档中的代码段是用于Prolog编程语言的，in_order_inf_sup是一个谓词，它接受一个二叉树作为其第一个参数，并将其中序遍历的结果存储在其第二个参数中。上面的查询演示了如何使用该谓词来检查给定的二叉树是否按升序排列。

- repeat

Answer 5

但它应该失败。那棵树是一棵无效的二叉搜索树，而您的谓词测试的是有效的二叉搜索树。

这里有一些需要做的事情。现在，您需要对一棵树执行两个操作 - 首先是在is_btree中，其次是在small/big中。

这两个步骤可以合并为一个，但是一种显而易见的解决方案将会精确地达到您想要的目的，因此会在这种无效的二叉搜索树上成功。

is_bst(nil).

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

为了解决这个问题，我们需要从树遍历中返回一个额外的结果——即树的最右侧元素，并在验证比较中使用它。

（编辑：忘记了还需要返回最左侧的元素）

- Will Ness