How to remove an element from a multiway tree in Prolog

user_10729772 0
Viewed 482

My friends and I are quite struggling with this task. In any other language this would be easy.

We tried converting the tree into a list, remove an element and then building a tree. The build from list to tree building part we have no clue how to do.

How would I go about it with this tree:

tree(1, [tree(6, [tree(7, [])] ),
         tree(3, []),
         tree(2, [tree(4, []), 
                  tree(5, [])])
        ])

Would be immensely grateful for any nudges or solutions.

prolog tree
2 Answers

Prolog variables are immutable - their value cannot be changed. So, if you want to change a tree say 3-way tree, you have a predicate that state the desired change.

A simple non-recursif case to replace specific nodes with new values:

replace_left_node(tree(_,B,C), NewNode, tree(NewNode, B, C).
replace_right_node(tree(A,B,_), NewNode, tree(A, B, NewNode).
replace_middle_node(tree(A,_,C), NewNode, tree(A, NewNode, C).

For a recursif case, you have to specify the change in greater detail. Say, in a tree with left & right sub trees and node value in the middle argument, replace node values having the value a by the value b, such as:

replace(a, b).           % replace the value a by value b
replace(X, X) :- X \= a. % otherwise use the same value unchanged

The recursive situation is to do the same to the Left and Right sub-trees.

replace_recursively(terminal, terminal) % this is the tree leaf
replace_recursively(tree(L, V, R), tree(L1, V1, R1)) :-
    replace(V, V1),             % handle the node value
    replace_recursively(L, L1), % handle left sub-tree
    replace_recursively(R, R1). % handle right sub-tree

Does this answer your question ? What else do you need ?

user_13104170

OK, with the example you gave in the comment, I understand better. I give you an example for removing the node with given value Elm. This is a double recursion, one for handling the functor tree and another for handling lists.

remove_elem_from_tree(Elm, tree(V, Nodes), tree(V,Nodes1) ):-
    Elm \= V,
    remove_elem_from_list(Elm, Nodes, Nodes1).
    
    remove_elem_from_list(_, [], []).
    remove_elem_from_list(E, [X|Xs], [Y|Ys]) :-
        remove_elem_from_tree(E, X, Y), !, 
        remove_elem_from_list(E, Xs, Ys).
    remove_elem_from_list(E, [_|Xs], Ys) :-
        remove_elem_from_list(E, Xs, Ys).

So example run is: remove the node 4

?- remove_elem_from_tree(4, tree(1, 
        [   tree(6, [tree(7, [])]),
            tree(3, []),
            tree(2, [tree(4, []),tree(5, [])])
        ]
      ), Result).

Result = tree(1,[tree(6,[tree(7,[])]),tree(3,[]),tree(2,[tree(5,[])])])

The node 4 was under node 2 in the given tree. It is removed and node 2 now has the only child node 5.

Does this answer help you and your friends ?

user_13104170
Related