prolog - 二叉搜索树 : min element

Question

我试图搜索这个但没有运气；如果问题已得到解答，请告诉我!

假设我有一个二叉树，其键值对的形式如下:

• t/0:空树
• t/4:具有t(Key, Value, Left, Right)
的树节点

现在我想获取第一个(最小)元素。显而易见的(对我来说)实现是:

min0(t(K,V,t,_), K, V) :- !.
min0(t(_,_,L,_), K, V) :- min0(L, K, V).

然而，在 SWI-Prolog 的 library(assoc) 中的实现是按照以下行进行的:

min(t(K,V,L,_), Key, Val) :- min(L, K, V, Key, Val).
min(t,K,V,K,V).
min(t(E,K,V,_), _, _, Key, Val) :- min(L, K, V, Key, Val).

max 和 get 等其他操作在方法上表现出相同的差异。

为什么？我在这里错过了什么？据我所知，我的版本没有创建选择点。但话又说回来，我需要削减基本情况。

Answer 1

您的版本确实在考虑执行子句时创建了一个选择点。 !/0 删除之前创建的选择点。您的版本不允许对第一个参数进行索引，而是依赖于术语中更深层次的统一。您是否已经在大型二叉树上对这两个版本进行了基准测试？除此之外，我觉得SWI版本更优雅，因为你提到的树项的两种情况自然出现在它里面。