Some doubts about the implementation of Prolog 2-3 Vocabulary

Question

I am learning Prolog using SWI Prolog, and I have some doubts about how to work with this implementation of vocabulary 2-3 in Prolog.

I know the theory of vocabulary 2-3 , which are trees whose internal nodes can generate 2 or 3 subtrees with the following properties:

1) All elements are stored in leaves and ordered from smaller to larger

2) All sheets are on the same level.

3) The internal nodes do not contain an inserted element, but contain a label that indicates the minimum elements of the subtrees as follows :

• If the inner node has 2 subtrees, the label in this inner node contains the MINIMUM RIGHT SUBTREE ELEMENT (so if I look for an X element that is smaller than the label, I'm sure it's in the left subtree)
• If the inner node has 3 subtrees, the label in this inner node contains 2 values: M2 and M3, where M1 is the MINIMUM that is present in SUBTREE CENTER and M3 is the MINIMUM that is the right subtree

So, searching if an element exists in this dictionary is pretty simple.

The insert is more complicated, I understand its theory, but I only have some problems with interpreting Prolog.

This is my program (take the book by Ivan Bratko: “Programming for Artificial Intelligence”):

/* 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 > XI 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). 

In this implementation, I have:

• l (X) adds an item to my tree
• n2 (T1, M, T2) represents a tree with two subsets T1 and T2, where M is the minimal element in T2
• n3 (T1, M2, T2, M3, T3) ** represents a tree with three subtrees: T1, T2, T3, where M2 is the minimum element in T2 and M3 is the minimum element in T3

The first doubt is related to the relationship that exists between the add23 prefix and ins , which:

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

As the comments write, I think that the first one is related to the case when a new tree does not grow up (for example, I had a tree containing 2 subtrees and inserting a new element, which I create a new subtree that has its leaves at the same level as everyone else (and so the inner node will now have 2 labels). Is this correct?

So, in logic, I can read this as: if the predicate ins (Tree, X, Tree1) is TRUE, then I add X to Tree, generating a new tree1 that has the same height as the old Tree, but contains an X element (so it must have an internal node having 3 children)

The second case is associated with wicht. I have a tree and I need to insert a new element in the node one that already has three subtrees, so I need to split the old tree into 2 trees, which as root have both a label and one label taken from two shortcuts of the old original node. Therefore, I can insert a new element in the form of a sheet and as the new root of a new tree.

So, in logic, I can read it as:

If the predicate ins (Tree, X, T1, M2, T2) is TRUE, this means that it is a TRUE predicate: add23 (Tree, X, n2 (T1, M2, T2))

This is the case when I split the original Tree tree with 3 subtrees into two different trees: T1 and T2, which with root privileges have a node with one minimal label, take Tree from the old root of the original tree.

So, I'm sure that one of these trees will have two subtrees, and the other will have one subtree, so I can add a new inserted element to this subtree, and also use it as a new root newtree which increases in height by one level.

Is it correct? I'm not sure about that ...

In the book, I found an explanation of three specific cases of the ins predicate, and I have many doubts about how this works:

CASE 1:

 ins(n2(T1, M , T2), X, n2(NT1, M, T2)) :- gt(M, X), ins(T1, X, NT1). 

In this case, tell me that the source tree of the tree is n2 (T1, M, T2) , and I insert X into the Tree, which is a tree that has only 2 subtrees : T1 and T2.

M is the MINIMUM CORRECT SUBTREE

So, if gt (M, X) is TRUE, that means M> X, so that means that X may be LEFT SUBTREE , which became NT1 (why? Maybe it depends on the fact that the old T1 has only one sheet in one of its subtrees?), and so at the end the original tree became n2 (NT1, M, T2)

I think this case is simple

CASE 2:

 ins(n2(T1, M, T2), X, n3(NT1a, Mb, NT1b, M, T2)) :- gt(M, X), ins(T1, X, NT1a, Mb, NT1b). 

In this case, tell me that the source tree of the tree is n2 (T1, M, T2) , and I insert X into the Tree, which is a tree that has only 2 subtrees : T1 and T2.

M is the MINIMUM CORRECT SUBTREE

IF it is TRUE that M> X, and it is TRUE predicate: ins (T1, X, NT1a, Mb, NT1b)

this means that I split T1 into 2 subtrees NT1a and NT1b, adding a third child to the original tree, which became n3 (NT1a, Mb, NT1b, M, T2)

Well, this is pretty clear, but my problem is this: in the full code, what is a predicate that should satisfy? I'm making a mess ...

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

This case is the case when the original Tree has 3 subtrees, and when I need to insert it, I have to split the original tree into two trees (n3 (T1, M2, T2, M3, T3) and n2 (NT1a, Mb, NT1b )), insert the new X element into one of these subtrees and use the minimum elements of the second subtree as the root of the left subtree as the root of the new tree (which is now higher than the level)

I doubt: in the previous case NewTree - n2 (NT1a, Mb, NT1b), M2, n2 (T2, M3, T3)

so that M2 (the minimum element of the right subtree) is the new root because it is TRUE, what is M2> X?

Can you give me some tips to better understand this thing?

Answer 1

Firstly, a few points of style. You do not need to have separate constructors for n2 and n3 , as arches will deal with this for you. Secondly, you should be suspicious of any predicate that has abbreviations, especially the red abbreviations that you use in / 2. As a rule, it is better (and faster) to do an explicit case analysis. Also, if possible, specify what you are comparing in the first argument as indexed by default.

I would rewrite in / 2 as

 in(leaf(Item), Item). in(node(Left, M, Right), Item):- compare(Order, Item, M), in_2(Order, Item, node(Left, M, Right). in(node(Left, M1, Mid, M2, Right), Item):- compare(Order, Item, M1), in_3(Order, Item, node(Left, M1, Mid, M2, Right)). in_2(<, Item, node(Left, _, _)):- in(Left, Item). in_2(=, Item, node(_, _, Right)):- in(Right, Item). in_2(>, Item, node(_, _, Right)):- in(Right, Item). in_3(<, Item, node(Left, _, _, _, _)):- in(Left, Item). in_3(=, Item, node(_, _, Mid, _, _)):- in(Mid, Item). in_3(>, Item, node(Left, M1, Mid, M2, Right)):- compare(Order, Item, M2), in_3a(Order, Item, node(Left, M1, Mid, M2, Right)). in_3a(<, Item, node(_, _, Mid, _, _)):- in(Mid, Item). in_3a(=, Item, node(_, _, _, _, Right)):- in(Right, Item). in_3a(>, Item, node(_, _, _, _, Right)):- in(Right, Item). 

As for the insertion of the tree, this is a little more complicated than I think you understand.

One of the key features of 2-3 trees is that all the leaves are at the same depth. This means that when you insert an element, you need to go through the tree to find where among the leaves you need to insert it, and then propagate the changes, supporting the tree so that it remains balanced. These slides from the lecture on data structures describe the algorithm. Try just translating them into Prolog. The slides clearly state what different cases are. The example code I gave above should help you with the first phase of the insert algorithm (find the correct lower level node to insert a new sheet). Use the same approach when you work with wood.