% Binary Search Trees in Prolog % Author: Steve Wolfman % Based on ideas by David Poole. % Released into the public domain. % A BST will be one of: % + empty % + node(Key, Value, LeftSubtree, RightSubtree), where % all keys in LeftSubtree are less than Key, and % all keys in RightSubtree are greater than Key. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Sample BSTs %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% example_bst("empty", empty). example_bst("1 -> a", node(1, a, empty, empty)). example_bst("1 -> a, 0 -> b, 2 -> c", node(1, a, node(0, b, empty, empty), node(2, c, empty, empty))). % Same contents as the previous one, but "rotated" % to put 0 at the root: example_bst("0 -> b, 1 -> a, 2 -> c", node(0, b, empty, node(1, a, empty, node(2, c, empty, empty)))). % Again, same contents but "rotated" to put 2 at the root. example_bst("2 -> c, 1 -> a, 0 -> b", node(2, c, node(1, a, node(0, b, empty, empty), empty), empty)). % The example from our lecture: example_bst("lecture", node(8, a, node(3, b, node(1, d, empty, empty), node(6, e, node(4, g, empty, empty), node(7, h, empty, empty))), node(10, c, empty, node(14, f, node(13, i, empty, empty), empty)))). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Look-up Predicate %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % lookup(Tree, Key, Val) is true if Key is present % in Tree with value Val. % % Because we'll use arithmetic comparison on the Key % and the keys within the Tree, those keys all need % to be ground numbers. Wouldn't it be great to use % constraints that allowed more flexibility? lookup(Tree, Key, Val). % TODO!!! % Curious about constraint programming: % Refer to https://www.swi-prolog.org/pldoc/man?section=clp, and try out #<, #>, #= %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Insert Predicate %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % insert(Tree, Key, Val, NewTree) is true if NewTree is % the natural result of adding Key/Val to Tree. That means: % % + if Key is already in Tree, NewTree is the same as Tree % except Key's new value is Val. % + otherwise, NewTree is the same as Tree except that the % empty tree where Key would fit in Tree is replaced by % a node with empty subtrees containing Key and Val. % % Because we'll use arithmetic comparison on the Key % and the keys within the Tree, those keys all need % to be ground numbers. Wouldn't it be great to use % constraints that allowed more flexibility? insert(Tree, Key, Val, NewTree). % TODO!!! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Tests %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% :- begin_tests('lookup'). % Base case: test('fails on an empty tree, regardless of key/val', [fail]) :- lookup(empty, _, _). test('succeeds on a tree with just the key sought', [nondet]) :- example_bst("1 -> a", Tree), lookup(Tree, 1, a). test('fails on a tree with just the key sought, wrong value', [fail]) :- example_bst("1 -> a", Tree), lookup(Tree, 1, b). % Recursive cases: test('fails on a small tree without the key sought', [fail]) :- example_bst("1 -> a", Tree), lookup(Tree, 2, _). test('fails on a small tree without the key sought, v2', [fail]) :- example_bst("1 -> a", Tree), lookup(Tree, 0, _). test('three-node successful cases', [nondet]) :- example_bst("1 -> a, 0 -> b, 2 -> c", Tree), lookup(Tree, 1, V1), assertion(V1 == a), lookup(Tree, 2, V2), assertion(V2 == c), lookup(Tree, 0, V0), assertion(V0 == b). test('complex successful cases', [nondet]) :- example_bst("lecture", Tree), lookup(Tree, 4, V4), assertion(V4 == g), lookup(Tree, 14, V14), assertion(V14 == f). test('complex failed cases', [fail]) :- example_bst("lecture", Tree), % ; is disjunction (or): ( lookup(Tree, 2, _) ; % not there lookup(Tree, 4, f) ; % there but not with that key lookup(Tree, 15, _) ).% not there :- end_tests('lookup'). :- begin_tests('insert'). % Base case #1: test('just inserts the new Key/Val', [nondet]) :- insert(empty, Key, Val, NewTree), assertion(NewTree == node(Key, Val, empty, empty)). % Base case #2: test('replaces the root value with the new value when the root key matches the given one', [nondet]) :- example_bst("1 -> a", Tree), insert(Tree, 1, Val, NewTree), assertion(NewTree == node(1, Val, empty, empty)). test('replaces the root value with the new value when the root key matches the given one, complex example', [nondet]) :- example_bst("lecture", Tree), insert(Tree, 8, Val, NewTree), Tree = node(_, _, LST, RST), % The subtrees, which stay the same. assertion(NewTree == node(8, Val, LST, RST)). % Recursive cases. test('simple insert to the left', [nondet]) :- example_bst("1 -> a", Tree), insert(Tree, 0, Val, NewTree), assertion(NewTree == node(1, a, node(0, Val, empty, empty), empty)). test('simple insert to the right', [nondet]) :- example_bst("1 -> a", Tree), insert(Tree, 2, Val, NewTree), assertion(NewTree == node(1, a, empty, node(2, Val, empty, empty))). test('complex insertion', [nondet]) :- example_bst("lecture", Tree), insert(Tree, 9, Val, NewTree), Tree = node(RK, RV, LST, node(RSK, RSV, _, RST)), assertion(NewTree == node(RK, RV, LST, node(RSK, RSV, node(9, Val, empty, empty), RST))). test('complex replacement', [nondet]) :- example_bst("lecture", Tree), insert(Tree, 6, Val, NewTree), Tree = node(RK, RV, node(LSK, LSV, LLST, node(LRSK, _, LRLST, LRRST)), RST), assertion(NewTree == node(RK, RV, node(LSK, LSV, LLST, node(LRSK, Val, LRLST, LRRST)), RST)). :- end_tests('insert').