如何在2-3棵树中搜索成员

Question

下面的代码成功找到二叉树中的成员。只是现在我想在 2-3 树中找到一个成员。 （类似于 https://www.youtube.com/watch?v= vSbBB4MRzp4。）下面的最后一行是尝试执行此操作。但我不确定标记为 TBD 的项目要使用什么（并且该行的其他部分可能是错误的）。关于如何执行此操作有任何帮助吗？谢谢！

bTree(L,X,R).

member(X, bTree(L,Y,_)) :-       
    X #< Y,
    member(X,L).
member(X, bTree(_,X,_)).
member(X, bTree(_,Y,R)) :-
    X #> Y,                      
    member(X,R).
member(X, bTree(L,Y,R)) :-
    X #> TBD, X #< TBD                     
    member(X,TBD).

Answer 1

在 2–3-tree 中，每个节点可以是：

• 2节点，例如t（左，键，右），有一个钥匙和两个孩子，或
• 3节点，例如t（左，键1，中间，键2，右），有两个键和三个孩子。

因此，2-3-tree：

可以表示为：

mytree(
  t(t(t(nil,1,nil),
    4,
    t(nil,5,nil,7,nil),
    13,
    t(nil,15,nil)),
  16,
  t(t(nil,17,nil,19,nil),
    20,
    t(nil,22,nil),
    24,
    t(nil,29,nil)))
).

搜索此树，您可以使用以下谓词：示例：

:- use_module(library(clpfd)).

% search 2-nodes: t(Left, Key, Right)

has(t(L,X,_), K) :- K #< X, has(L, K).
has(t(_,K,_), K).
has(t(_,X,R), K) :- K #> X, has(R, K).

% search 3-nodes: t(Left, Key1, Middle, Key2, Right)

has(t(L,X,_,_,_), K) :- K #< X, has(L, K).
has(t(_,K,_,_,_), K).
has(t(_,X,M,Y,_), K) :- K #> X, K #< Y, has(M, K).
has(t(_,_,_,K,_), K).
has(t(_,_,_,Y,R), K) :- K #> Y, has(R, K).

示例：

?- mytree(T), has(T, 51).
false.

?- mytree(T), has(T, 16).
T = t(t(t(nil, 1, nil), 4, t(nil, 5, nil, 7, nil), 13, t(nil, 15, nil)), 16, t(t(nil, 17, nil, 19, nil), 20, t(nil, 22, nil), 24, t(nil, 29, nil))) .

?- mytree(T), forall(has(T,X), writeln(X)).
1
4
5
7
13
15
16
17
19
20
22
24
29
T = t(t(t(nil, 1, nil), 4, t(nil, 5, nil, 7, nil), 13, t(nil, 15, nil)), 16, t(t(nil, 17, nil, 19, nil), 20, t(nil, 22, nil), 24, t(nil, 29, nil))).