Algorithms and Data Structures (INF1, Autumn'05)
Exercise Set 9
Exercise 1:
-
Give appropriate pre- and post- conditions for the operation
retrieve(key:KEY_TYPE):ENTRY_TYPE from the symbol table ADT.
Make sure that the symbol table is not modified.
-
Discuss the operation retrieve in the singly linked list
implementation of the symbol table ADT (showed at the lecture).
-
Improve your implementation such that it uses Move-to-Front
heuristics. Is your implementation still totally correct with regard
to the pre- and post- conditions you suggested above?
Exercise 2 (hand-in):
Consider the following sequence of operations on a symbol
table s using the binary search tree implementation
from the lecture.
s.make
s.insert(s.new_entry(4,"Peter"));
s.insert(s.new_entry(2,"Jan"));
s.insert(s.new_entry(7,"Peter"));
s.insert(s.new_entry(5,"Jiri"));
s.insert(s.new_entry(6,"Anna"));
s.insert(s.new_entry(8,"Peter"));
-
Draw the resulting binary search tree including the
keys and values stored in the nodes.
Exercise 3:
Consider binary search trees as defined at the lecture.
-
Implement a (recursive) algorithm
print(x:ENTRY_TYPE,a:KEY_TYPE,b:KEY_TYPE)
such that if t is a binary search tree and a < b then
print(t.root,a,b) prints the values of all entries
which have the key in the interval [a,b].
(Hint: use inorder traversal).
- Discuss the worst-case time complexity of your algorithm.
Does it depend on the number of printed values?
- Try to improve your algorithm such that you do not
have to visit all the nodes in the tree when printing only a few
values.
Exercise 4:
Draw all binary search trees with exactly three nodes that
store the keys 4, 7 and 8. The values stored in the nodes
are irrelevant.