CODEWITHSUNDEEP
treeprolog
Andrew Cooper
Andrew Cooper

Reputation: 23

Make a prolog BST from a list and return it in the parameter

I need to make a prolog predicate from_list/2 so that if i call from_list([], T) I will get back a tree containg the items in the list(ints) so far I have:

from_list([], empty).
from_list([X], T) :-
    insert(X, empty, T).
from_list([X|Y], T) :-
    from_list(Y, NT),
    insert(X, NT, T).

edit: figured it out, but it is adding them to the tree in reverse order of the list. Any help?

Here is my insert predicate, which seems to work just fine.

insert( X, empty, bt(X, empty, empty) ). 
insert( X, bt(X2, L, R), bt(X2, NL, R) ) :-
    X < X2,
    !,
    insert(X, L, NL). 
insert( X, bt(X2, L, R), bt(X2, L, NR) ):-
    insert(X, R, NR).

And not also a second, much smaller question which doesn't NEED an answer

I know prolog has a very elegant style when used properly...and this code...not so elegant...

is_search(empty).
is_search( bt(_, empty, empty) ).
is_search( bt( X, empty, bt(Y,LEFT,RIGHT) ) ) :-
    X < Y,
    is_search(LEFT),
    is_search(RIGHT).
is_search( bt(X, bt(Y,LEFT,RIGHT), empty) ) :-
    X > Y,
    is_search(LEFT),
    is_search(RIGHT).
is_search( bt( X, bt(Y,L1,R1), bt(Z, L2, R2) ) ) :-
    X > Y,
    X < Z,
    is_search( bt(Y, L1, R1) ),
    is_search( bt(Z, L2, R2) ).

Any tips on how to clean that up a little?

Upvotes: 1

Views: 2282

Answers (2)

mat
mat

Reputation: 40768

Regarding your second question, I would say you should describe the TWO (not five!) cases of a binary tree: Either it is empty, or it is an inner node where all the elements to the left and right are smaller and larger, respectively, and are binary trees themselves:

bt(empty).
bt(bt(Val, Left, Right)) :-
    all_smaller_than(Left, Val),
    all_larger_than(Right, Val),
    bt(Left),
    bt(Right).

I leave all_smaller_than/2 and all_larger_than/2 as an exercise for you. Hint: Again two clauses suffice for each of them. You may find a way to make it faster as well...

Upvotes: 1

solick
solick

Reputation: 2345

Just a hint from my side:

from_list([], empty).
from_list([X], T):- insert(X, empty, T).
from_list([X|Y], T):- from_list(Y, NT), insert(X, NT, T).

This will not work because if you´re looking at line 2 empty is not known.

To have a list in reverse order use

reverse(X,R).

PS: As far as i can see we are talking of SWI-Prolog, right?

Upvotes: 1

Related Questions