How to search for a member in a 2-3 tree

Question

The code below successfully finds a member in a binary tree. Except that now I want to find a member in a 2-3 tree. (Similar to the tree shown in https://www.youtube.com/watch?v=vSbBB4MRzp4.) The last line below is an attempt to do this. But I am unsure what to use for the items marked TBD (and other parts of this line could be wrong). Any help on how to do this? Thanks!

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

In a 2–3-tree, each node can be a:

• 2-node, say t(Left,Key,Right), that has one key and two children, or
• 3-node, say t(Left,Key1,Middle,Key2,Right), that has two keys and three children.

Thus, the 2-3-tree:

can be represented as:

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

To search this tree, you can use the following predicate:

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

Examples:

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