% TREES in Prolog %1. Experiment with the predicates below (from the lecture notes) %2. Write a predicate that removes a key from a binary search tree. %3. Start working on Assignment 4 % ============== % Trees can be represented as structures like this: % bt(LeftSubTree, Key, RightSubTree) % Leaves can be denoted like this: % bt(key, nil, nil) % nil is just a constant to represent an empty tree % you can use any constants, such as null or empty. % A binary search tree is a binary tree such that the % value of the key at a node is larger than the keys in the left subtree % and smaller than the keys in the right subtree. % To test whether a key is in a binary search tree % we a implement btMember(E,T): btMember(E, bt(E, _L, _R)). btMember(E, bt(E1, L, _R)):- E < E1, btMember(E, L). btMember(E, bt(E1, _L, R)):- E > E1, btMember(E, R). % To do insertion, we implement btInsert(E,T,T1) % where T1 is the new tree after the key E is added to T. btInsert(E, nil, bt(E, nil, nil)). btInsert(E, bt(E, L, R), bt(E, L, R)). btInsert(E, bt(E1, L, R), bt(E1, L1, R)) :- E < E1, btInsert(E, L, L1). btInsert(E, bt(E1, L, R), bt(E1, L, R1)) :- E > E1, btInsert(E, R, R1). test(T4):- btInsert(7, nil, T), btInsert(5, T, T1), btInsert(9, T1, T3), btInsert(3, T3, T4). test1(T5):- btInsert(7, nil, T), btInsert(5, T, T1), btInsert(1, T1, T2), btInsert(6, T2, T3), btInsert(9, T3, T4), btInsert(3, T4, T5). % 7 % / \ % 5 9 % / \ %1 6 % \ % 3 % X+Y % + % / \ % X Y %prefix 7 5 1 3 6 9 + X Y node left right %infix 1 3 5 6 7 9 X + Y left node right %postfix 3 1 6 5 9 7 X Y + left right node %balanced trees of a given height hbal_tree(0,nil) :- !. hbal_tree(1,t(x,nil,nil)) :- !. hbal_tree(D,t(x,L,R)) :- D > 1, D1 is D - 1, D2 is D - 2, distr(D1,D2,DL,DR), hbal_tree(DL,L), hbal_tree(DR,R). distr(D1,_,D1,D1). distr(D1,D2,D1,D2). distr(D1,D2,D2,D1).