prolog - 二叉搜索树：最小元素

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 版本更优雅，因为您提到的树术语的两种情况自然出现在其中。