% Taha Sheikh, 991016627 % CSC324 Programming Languages % Assignment 2 % ------------------------------------------------------------------------------------ % Binary Search Tree node(empty). node(K,empty,empty). node(K,S,T) :- node(S), node(T). % ------------------------------------------------------------------------------------ % Question 1: % min(T, Min) : "Min" is the smallest integer element in the BST "T". % The minimum element of a BST is the last node of the root's left % subtree. Track left child until an empty subtree is reached. min(node(K, empty, empty), K). min(node(K, S, T), Min) :- min(S, Min). % ------------------------------------------------------------------------------------ % Question 2: % max(T, Max) : "Max" is the largest integer element in the BST "T". % The maximim element of a BST is the last node of the root's right % subtree. Track the right child until an empty subtree is reached. max(node(K, empty, empty), K). max(node(K, S, T), Max) :- max(T, Max). % ------------------------------------------------------------------------------------ % Question 3: % height(T, H) : "H" is the integer height of the binary search tree "T". height(empty, -1). % height of an empty tree is -1 height(node(K,S,T), H) :- height( S, HL ), height( T, HR ), HL >= HR, H is HL+1. height(node(K,S,T), H) :- height( S, HL ), height( T, HR ), HL < HR, H is HR+1. % ------------------------------------------------------------------------------------ % Question 4: % nodecount(T, NumNodes) : "Nodes" is the integer value representing the total % number of nodes in the binary search tree "T". nodecount(empty, 0). nodecount(node(K, S, T), NumNodes) :- nodecount(S, NL), nodecount(T, NR), NumNodes is NL+NR+1. % ------------------------------------------------------------------------------------ % Question 5: % member(Element, T) : "Element" is tested for membership in the binary search tree "T" member(E,node(E,_,_)). % element is root, left, or right child member(E,node(_,E,_)). member(E,node(_,_,E)). member(E,node(_,S,_)) :- % element is less than root, check member(E,S). % in left subtree member(E,node(_,_,T)) :- % element is greater than root, check member(E,T). % in right subtree % ------------------------------------------------------------------------------------ % Question 6: % insert(E, oldTree, newTree) : "E" is an integer element that is inserted % according to the BST property to produce the result newTree. insert(E, empty, node(E, empty, empty)). % insert into empty tree insert(E, node(K, S, T), node(K, NewS, T)) :- % element is less than root, insert E < K, % in left subtree insert(E, S, NewS). insert(E, node(K, S, T), node(K, S, NewT)) :- % element is greater than root, insert E > K, % in right subtree insert(E, T, NewT). % ------------------------------------------------------------------------------------ % Question 7: % delete(E, oldTree, newTree) : E is an integer element to be deleted from "oldTree" % to produce the result "newTree" merged( empty,T, T ). merged( S,empty, S ). merged( node(SK,SS,ST),T, node(SK,SS,FixedT) ) :- merged( ST,T, FixedT ). delete( E, node(E,S,T), NT ) :- merged( S,T, NT ). delete( E, node(K,S,T), node(K,FixedS,T) ) :- E < K, delete( E, S, FixedS ). delete( E, node(K,S,T), node(K,S,FixedT) ) :- E > K, delete( E, T, FixedT ). % del(E, node(E, empty, T), T) :- % !. % del(E, node(E, S, empty), S) :- % !. % del(E, node(E, S, T), node(Max, newS, T)) :- % delmax(S, NewS, Max). % del(E, node(E, S, T), node(K, newS, T)) :- % E < K, % del(E, S, NewT). % del(Node, bst(Root, LT, RT), bst(Root, LT, NewRT)) :- % Node > Root, % del(Node, RT, NewRT). % % delmax(bst(Max, LT, empty), LT, Max). % delmax(bst(Root, LT, RT), bst(Root, LT, NewRT), Max):- % RT \== nil, % delmax(RT, NewRT, Max). % ------------------------------------------------------------------------------------ % Question 8: % inorder(T, NodeList) : "NodeList" is the inorder traversal of integer % elements in the binary search tree "T" inorder(empty, [ ]). % empty tree, return null inorder(node(K, S, T), NodeList) :- % inorder traversal, left, root, right inorder(S, SNodes), % recursive call on left subtree inorder(T, TNodes), % recursive call on right subtree append(SNodes, [K | TNodes], NodeList). % NodeList inorder traversal % ------------------------------------------------------------------------------------ % Test Cases % Test trees generated to test functionality of written procedures test_tree(1,node(25, node(23,node(20,node(17,empty,node(19,empty,empty)),node(22,empty,empty)),node(24,empty,empty)), node(35,node(32,node(30,empty,empty),node(33,empty,empty)),node(39,node(38,empty,empty),node(47,node(40,empty,empty),empty))))). test_tree(2,node(4,node(3,node(2,empty,empty),empty),node(5,empty,empty))). test_tree(3,node(10,node(9,node(8,node(7,empty,empty),empty),empty),node(11,empty,node(12,empty,node(13,empty,empty))))). % test_tree % test_tree(1,node(25, % node(23,node(20,node(17,empty,node(19,empty,empty)),node(22,empty,empty)),node(24,empty,empty)), % node(35,node(32,node(30,empty,empty),node(33,empty,empty)),node(39,node(38,empty,empty),node(47,node(40,empty,empty),empty)))). % BST for Testing: % node(25, % node(23,node(20,node(17,empty,node(19,empty,empty)),node(22,empty,empty)),node(24,empty,empty)), % node(35,node(32,node(30,empty,empty),node(33,empty,empty)),node(39,node(38,empty,empty),node(47,node(40,empty,empty),empty)))). % member(7,node(3,node(2,empty,empty),node(4,empty,node(5,empty,empty)))). % member(7,node(3,node(2,1,4),node(4,3,node(5,empty,empty)))). % member(9,node(3,node(2,1,4),node(4,3,node(5,empty,empty)))). % member(30, node(25, % node(23,node(20,node(17,empty,node(19,empty,empty)),node(22,empty,empty)),node(24,empty,empty)), % node(35,node(32,node(30,empty,empty),node(33,empty,empty)),node(39,node(38,empty,empty),node(47,node(40,empty,empty),empty))))). % insert(2,node(4,node(3,empty,empty),node(5,empty,empty)),Result).