Session 7: Trees
Trees
We only consider binary trees here. You can find the definition of a binary tree in Bratko, Section 9.2, p. 204.
-
Write a predicate linearize/2 to collect all the nodes from a given tree in a list.
-
An 'open tree' is a tree in which some subtree is a variable (by the way: in the same way an 'open list' is defined as
a list with a variable as a tail; you will see more about that later). An example of an open tree is given
in Bratko, p.206: t(t(D1,3,D2),5,t(D3,8,D4)). Write a predicate close/1 that given a tree, closes all open
subtrees (i.e. variables) in the tree by instantiating them with nil.
Efficiently searching sorted lists
Searching for an element in a list can be done by using the member/2 predicate. If you know that the given list is sorted, however, searching can be
done more efficiently.
-
Write a predicate occur/2 that succeeds if the first argument
occurs in the sorted list that is provided as second
argument. Try to do this more efficiently than the
member/2 predicate we used before.
-
When we search for an element in a sorted list, we have to compare the
element we are looking for with all the elements that come
before the element we are looking for. We can reduce this number
of comparisons by not looking at each number in the ordered
list, but only looking at the third number in the list: if this
is smaller than the number we are looking for, it must be one of
the two numbers we skipped. Otherwise, skip again 2 numbers and
compare etc. In this way we need on average only 1/3 of the
comparisons of occur/2. Write a predicate occurthree/2 that
performs the search in this way.
Binary dictionaries
We could search very efficiently if we could immediately check the median of our
list (if this is not the element we are looking for, decide in which half of the list we have to search further, take the
median of that half, etc). This is the idea behind binary dictionaries as defined in Bratko (Section 9.2, p.205).
In Bratko you can find definitions of predicates to search, insert and
delete elements in such a binary dictionary.
-
Write a predicate
count/2 that calculates the number of elements in a binary
dictionary (without using findall/3).
-
Write a predicate sorted/1 that succeeds if the argument is a
(correctly sorted) binary dictionary.
Balanced Binary dictionaries
A balanced tree has the following property:
for each each node
in the tree it is the case that the depth of the left subtree differs
at most one from the depth of the right subtree.
Being balanced is an important property for a ordered tree (a binary dictionary):
it ensures access to an element in log(n) time, where n is the number of elements in the tree (see Bratko p.207).
-
Write a predicate balanced/1 that succeeds if the given binary dictionary is balanced.
-
Write a predicate makeOrdered/2 that given a number N, returns as an
output a balanced binary dictionary containing all numbers from 1 to N.
-
Write a predicate list_to_balanced/2 that given a sorted list with numbers, returns as an output a balanced binary
dictionary containing all these numbers.