如何在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树中，每个节点可以是：

• 2-node，say t(Left,Key,Right)，它有一个键和两个子键，or
• 3-node，say t(Left,Key1,Middle,Key2,Right)，它有两个键和三个子键。

因此，2-3树：

​

​

可表示为：

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