Description
Exercise 1 Red-Black Trees
We want to store the keys H, R, S, L, D, N in a data structure sorted in
the alphabetical order.
a. Insert the keys above into a Binary Search Tree (BST) in the given
order (insert H as the first and N as the last element). Draw the
resulting tree.
b. Delete the key R from the BST and draw the resulting tree structure.
c. Insert the keys H, R, S, L, D, N into a Red-Black Tree. Draw the
resulting tree after each insertion (Draw red links as dashed or
double lines (- – – or ===) and black links as solid lines (—).
1
Exercise 2 Undirected Graphs and Search with Adjacency Matrices
Download and extract contents of
ceng218 05 Graph Representation and Traversal.tar.gz
a. Compile and run the executable graph-search by running cmake and
make. Inspect the output and the code to understand the implementation of graph search using adjacency lists in C++.
b. Write a new class GraphAdjMat that has the same API as the existing
class GraphAdjList but that represents the graph internally using an
adjacency matrix instead of an adjacency list.
c. Replace the references to GraphAdjList by GraphAdjMat in the file
src/graph search main.cc. Compile and run the executable graph-search.
Make sure the output is exactly the same as before.
2