Logic Issue with custom binary search tree

Question

I am trying to define a simple binary search tree. It is stored in lists like so: [Key, Left Tree, Right Tree]. I'm having issue with my logic. This is what I have

bstadd(K, [], [K,[],[]]).
bstadd(K, [X|_], [X, [], [K, [], []]]) :- K > X.
bstadd(K, [X, [], [K, [], []]], [X|_]) :- K < X.

This is what I query

1 ?- bstadd(19, [],T1), bstadd(20,T1,T2), bstadd(21,T2,T3).

this is what I get out

T1 = [19, [], []],
T2 = [19, [], [20, [], []]],
T3 = [19, [], [21, [], []]]

and this is what I need

[19, [], [20, [], [21, [], []]]]

Any help would be wonderful. I have been banging my head against the wall for days.

Using lists with fixed num.of.elements it's bad practice. Your tree would be better represented by a recursive t(K,L,R) — CapelliC
– CapelliC, Commented Dec 17, 2013 at 6:32

ssbarbee · Accepted Answer · 2013-12-17 07:18:14Z

2

This is my solution. Let me know what you think and if you find it hard to understand it I'll be glad to help you out.

bstadd(Value, [], [Value,[],[]]).
bstadd(Value,[Key,Left,Right],X) :- Value \= Key , % no duplicates in BST
                                    (
                                      Value < Key -> % if Value < Key
                                        % then add to left side
                                        bstadd(Value,Left,Rez) ,
                                        X = [Key,Rez,Right]
                                      ; %else (Value > Key)
                                        % then add to right side
                                        bstadd(Value,Right,Rez) ,
                                        X = [Key,Left,Rez]
                                    ).

edited Dec 17, 2013 at 7:18

answered Dec 17, 2013 at 4:38

ssbarbee

1,7222 gold badges16 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

CapelliC Over a year ago

I would prefer cleaner code. Inner parenthesis on If->Then;Else are not required. The same for the deep spacing in the body of the recursive clause.

ssbarbee Over a year ago

Personally I find it much easier to read the code like this :) Is it too big a sin to leave the code like this?

Daniel Lyons Over a year ago

It's definitely unidiomatic to have Tree=[Key,Left,Right] on line 1 instead of just using [Key,Left,Right] in the head. And not(X=Y) is better expressed X \= Y. But the spacing is not sinful (though I would use more spaces around the commas).

CapelliC Over a year ago

@ssBarBee: No, but since Prolog syntax it's a bit hostile to newcomers, I think that we should keep as simple as possible

ssbarbee Over a year ago

Thanks for the tips Daniel,Cape. I applied some of them and hopefully it ain't hostile to newcomers anymore:)

|

Collectives™ on Stack Overflow

Logic Issue with custom binary search tree

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related