Week 05 Tutorial Questions

AVL Trees

AVL trees use the following node definition:

typedef struct Node *Link; // Links are pointers to nodes
typedef struct Node *Tree; // a Tree is a pointer to its root node

struct Node { int data; int height; Link left; Link right; };

You may find these resources on AVL trees useful:

• AVL tree visualization
• VisuAlgo's AVL tree visualizer (click on AVL tree)

1. (AVL trees)

   For the following AVL tree, annotate each node with the height of its subtree.

   

   Now starting from the initial tree each time, insert the following integers:

   0  2  10  17

2. (AVL trees)

   Show how an AVL tree would be constructed if the following values were inserted into an initially empty tree in the order given:

   12  10  8  6  4  2

3. (Algorithms and complexity)

   Using an AVL tree, design an algorithm to determine if an array contains two elements that sum to a given value.

   1. Write the algorithm in pseudocode.
   2. Analyse the time complexity of your algorithm.

2-3-4 Trees

2-3-4 trees use the following node definition:

typedef struct Node *Link; // Links are pointers to nodes
typedef struct Node *Tree; // a Tree is a pointer to its root node

struct Node { int order; int data[3]; Link child[4]; };

You may find these resources on 2-3-4 trees useful:

• 2-3-4 tree visualization (select Max. Degree = 4)

  Note: This visualizer uses a different strategy from the lecture slides for promoting a value from a full node. The lecture slides promotes the middle of the three values that were already in the node, whereas the visualizer inserts the new value first, and then promotes the smaller of the two middle values.

1. (2-3-4 trees)

   Show how a 2-3-4 tree would be constructed if the following values were inserted into an initially empty tree in the order given:

   1  2  3  4  5  8  6  7  9  10

   Once you have built the tree, count the number of comparisons needed to search for each of the following values in the tree:

   1  7  9  13

Graph Representation

1. For each of the following graphs:

   

   Show the concrete data structures if the graph was implemented via:

   1. adjacency matrix representation (assume a full \( V \times V \) matrix)
   2. adjacency list representation (if non-directional, include both \( (v, w) \) and \( (w, v) \))

2. Facebook could be considered as a giant "social graph"

   1. What are the vertices?
   2. What are the edges?
   3. Are edges directional?
   4. What does the degree of each vertex represent?
   5. What kind of graph algorithm could suggest potential friends?