我正在使用 SWI Prolog 学习 Prolog，我对 Prolog 中2-3 字典的实现如何工作有一些疑问。
我知道2-3 字典的理论是树，其内部节点可以生成 2 或 3 个具有以下属性的子树：
1）所有的物品都存放在叶子里，按照从小到大的顺序排列
2）所有叶子都在同一级别
3）内部节点不包含插入的项目，但包含以下列方式指定子树的最小元素的标签：
- 如果内部节点有 2 个子树，则该内部节点中的标签包含其 RIGHT SUBTREE 的 MINIMAL ELEMENT（因此，如果我正在搜索小于标签的项目 X，则我确定它在左子树中）
- 如果内部节点有 3 个子树，则该内部节点中的标签包含 2 个值：M2 和 M3，其中 M1 是存在于中心子树中的最小值，而 M3 是作为右子树的最小值
因此，搜索此类字典中是否存在项目非常简单。
插入更复杂，我已经理解它的理论，但我对 Prolog 的解释有一些问题。
这是我的程序（取自 Ivan Bratko 的书：人工智能编程）：
/* in(Item, Tree) predicate is TRUE if the searched Item is in the specified Tree */
% BASE CASE: Item found in a leaf, so end
in(Item, l(Item)).
/* CASE 1: I am searching Item in an internal node having a single label value
so this internal node have 2 subtrees
*/
in(Item, n2(T1,M,T2)) :- gt(M,Item), % IF M label value lexicographically follows the searched Item value
!,
in(Item,T1) % THEN search Item in the left subtree
; % (; is an OR)
in(Item,T2). % Otherwise search Item in the right subtree
/* CASE 2: I am searching Intem in an internal node having 2 label values so this
internal node have 3 subtrees
*/
in(Item, n3(T1,M2,T2,M3,T3)) :- gt(M2,Item), % IF M2 label value lexicographically follows the searched Item value
!,
in(Item,T1) % THEN search Item in the left subtree
; % (; is an OR)
/* IF M3 label value lexicographically follows the searched Item value
BUT this is NOT TRUE that M2>Item
*/
gt(M3,Item),
!,
in(Item,T2) % THEN search Item in the central subtree
; % (; is an OR)
in(Item,T3). % ELSE (it is TRUE that Item>M3) search in the right subtree
/*
*/
% Insertion in the 2-3 dictionary
/* Add X to Tree giving Tree1
CASE 1: After the insertion of X into Tree, Tree1 does not grow upwards (so it means that an internal nodes
having 2 subtrees child, now have 3 subtrees child, so the original tree has grown in width)
*/
add23(Tree, X, Tree1) :- ins(Tree, X, Tree1).
/* CASE 2: Tree grows upwards: It means that if after the insertion of X the height of the new tree is
increased so the ins/5 predicate determines the two subtrees T1 and T2 which are then combined
into a bigger tree
*/
add23(Tree, X, n2( T1, M2, T2)) :- ins(Tree, X, T1, M2, T2).
del23(Tree, X, Tree1) :- add23(Tree1, X, Tree). % Delete X from Tree giving Tree1
/* BASE CASE: Inserting the X item into a voil (nil) tree means to obtain a tree
consisting of the single new leaf l(X)
*/
ins(nil, X, l(X)).
/* BASE CASES: related to inserting a new item X into a tree composed by
a single leaf
*/
ins(l(A), X, l(A), X, l(X)) :- gt(X, A).
ins(l(A), X, l(X), A, l(A)) :- gt(A, X).
/* Tree = n2(T1, M , T2) so Tree is a tree having 2 subtrees T1 and T2
M: is the MINIMAL ELEMENT OF T2
IF it is TRUE that M>X (the minimal element in T2 is > the new X item)
I have to insert X in the LEFT subtrees (into T1 that becomes NT1 and
now have 2 leaves)
*/
ins(n2(T1, M , T2), X, n2(NT1, M, T2)) :- gt(M, X),
ins(T1, X, NT1).
/* Tree = n2(T1, M , T2) so Tree is a tree having 2 subtrees T1 and T2
M: is the MINIMAL ELEMENT OF T2.
IF it is TRUE that M>X (the minimal element in T2 is > the new X item) and
IF I can insert
*/
ins(n2(T1, M, T2), X, n3(NT1a, Mb, NT1b, M, T2)) :- gt(M, X),
ins(T1, X, NT1a, Mb, NT1b).
ins(n2(T1, M, T2), X, n2(T1, M, NT2)) :- gt(X, M),
ins(T2, X, NT2).
ins( n2( T1, M, T2), X, n3( T1, M, NT2a, Mb, NT2b)) :-
gt( X, M),
ins( T2, X, NT2a, Mb, NT2b).
ins( n3( T1, M2, T2, M3, T3), X, n3( NT1, M2, T2, M3, T3)) :-
gt( M2, X),
ins( T1, X, NT1).
/* Tree = n3(T1, M2, T2, M3, T3) so Tree is a tree having 3 subtree: T1,T2 and T2
and the ROOT of Tree is the node (M2,M3)
M2: MINIMAL ELEMENT of T2 subtree
M3: MINIMAL ELEMENT of T3 subtree
If I had the item X then Tree have to grow in height
IF it is TRUE that M2 > X I could try to insert the X item into T1 subtree
IF it is TRUE that X is added in T1 and T1 is splitted in NT1a and NT1b having root Mb
so the new tree is: n2(NT1a, Mb, NT1b), M2, n2(T2, M3, T3)
*/
ins(n3(T1, M2, T2, M3, T3), X, n2(NT1a, Mb, NT1b), M2, n2(T2, M3, T3)) :-
gt(M2, X),
ins(T1, X, NT1a, Mb, NT1b).
ins(n3(T1, M2, T2, M3, T3), X, n3(T1, M2, NT2, M3, T3)) :-
gt(X, M2), gt(M3, X),
ins(T2, X, NT2).
ins( n3( T1, M2, T2, M3, T3), X, n2( T1, M2, NT2a), Mb, n2( NT2b, M3, T3)) :-
gt( X, M2), gt( M3, X),
ins( T2, X, NT2a, Mb, NT2b).
ins( n3( T1, M2, T2, M3, T3), X, n3( T1, M2, T2, M3, NT3)) :-
gt( X, M3),
ins( T3, X, NT3).
ins( n3( T1, M2, T2, M3, T3), X, n2( T1, M2, T2), M3, n2( NT3a, Mb, NT3b)) :-
gt( X, M3),
ins( T3, X, NT3a, Mb, NT3b).
在这个实现中，我有：
- l(X) rappresent 一个存在于我的树中的项目
- n2(T1,M,T2)表示具有 2 个子树 T1 和 T2 的树，其中 M 是 T2 中的最小元素
- n3(T1,M2,T2,M3,T3)** 表示具有 3 个子树的树：T1,T2,T3 其中 M2 是 T2 中的最小元素，M3 是 T3 中的最小元素
第一个疑问与add23和ins谓词之间存在的关系有关，这些：
/* Add X to Tree giving Tree1
CASE 1: After the insertion of X into Tree, Tree1 does not grow upwoards (so it means that an internal nodes
having 2 subtrees child, now have 3 subtrees child, so the original tree has grown in width)
*/
add23(Tree, X, Tree1) :- ins(Tree, X, Tree1).
/* CASE 2: Tree grows upwards: It meaans that if after the insertion of X the height of the new tree is
increased so the ins/5 predicate determines the two subtrees T1 and T2 wich are then combined
into a bigger tree
*/
add23(Tree, X, n2( T1, M2, T2)) :- ins(Tree, X, T1, M2, T2).
正如评论中所写，我认为第一个与新树不会向上生长的情况有关（例如，我有一棵有 2 个子树的树并插入了一个新项目，我正在创建一个新的子树它的叶子在所有其他叶子的同一级别（因此内部节点现在将有 2 个标签）对吗？
所以在逻辑上我可以把它读成：如果ins(Tree, X, Tree1)谓词是 TRUE 那么我将 X 添加到 Tree 生成新 Tree1 ，它与旧 Tree 具有相同的高度但包含 X 项（所以它必须有一个内部节点有 3 个孩子）
第二种情况与我有一棵树的情况有关，我必须在一个已经有 3 个子树的节点中插入一个新项目，所以我必须将旧树拆分为 2 棵树，作为根，两者都作为标签 a单个标签取自旧原始节点的 2 个标签。所以我可以将新项目作为叶子和新树的新根插入。
所以在逻辑上我可以把它读成：
如果谓词ins(Tree, X, T1, M2, T2)为 TRUE，则意味着谓词为 TRUE：add23(Tree, X, n2( T1, M2, T2))
在这种情况下，我将具有3 个子树的原始树 Tree 拆分为两个不同的树：T1 和 T2，它们作为根有一个节点，该节点具有从原始树的旧根获取的单个最小标签。
所以碰巧我肯定会有这些树中的一棵有两个子树，而另一棵有一个子树，所以我可以将新插入的项目添加到这个子树中，并将它用作增加的新树的新根高一级。
这样对吗？我不确定这...
在这本书中，我找到了对ins谓词的三种具体情况的解释，我对它的工作原理有很多疑问：
情况1：
ins(n2(T1, M , T2), X, n2(NT1, M, T2)) :- gt(M, X),
ins(T1, X, NT1).
这种情况说我原来的树 Tree是：n2(T1, M , T2)并且我将 X 插入到 Tree 中，这是一棵只有2 个子树的树：T1 和 T2。
M是右子树的最小元素
因此，如果gt(M, X)为 TRUE，则意味着 M>X，因此这意味着 X 可能是成为NT1的左子树（为什么？这可能取决于旧的 T1 在它的一个中只有 1 个叶子）子树？），所以最后，原始树变成了n2(NT1, M, T2)
我认为这种情况很简单
案例二：
ins(n2(T1, M, T2), X, n3(NT1a, Mb, NT1b, M, T2)) :- gt(M, X),
ins(T1, X, NT1a, Mb, NT1b).
在这种情况下，我说原始树 Tree是：n2(T1, M , T2)并且我将 X 插入到 Tree 中，这是一棵只有2 个子树的树：T1 和 T2。
M是右子树的最小元素
如果 M>X 为 TRUE，则谓词为 TRUE：ins(T1, X, NT1a, Mb, NT1b)
这意味着我将 T1 拆分为 2 个子树 NT1a 和 NT1b，将第三个子树添加到成为n3(NT1a, Mb, NT1b, M, T2)的原始树中
好的，这很清楚，但我的问题是：在完整的代码中，这个谓词必须满足什么？我在做混乱...
案例 3：
ins(n3(T1, M2, T2, M3, T3), X, n2(NT1a, Mb, NT1b), M2, n2(T2, M3, T3)) :-
gt(M2, X),
ins(T1, X, NT1a, Mb, NT1b).
这种情况是原始树 Tree 有 3 个子树，当我必须插入它时，我必须将原始树分成两棵树（n3（T1，M2，T2，M3，T3）和 n2（NT1a，Mb , NT1b)) ，将新项 X 插入这些子树之一，并使用第二个子树的最小元素作为左子树的根作为新树的根（现在高于一个级别）
我的疑问是：在前一种情况下，NewTree是n2(NT1a, Mb, NT1b), M2, n2(T2, M3, T3)
所以 M2（右子树的最小元素）是新的根，因为 M2>X 是真的？
你能给我一些提示来更好地理解这些东西吗？