Week 05 Tutorial Answers

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

   Answer:

   Tree annotated with heights:

   

   1. After inserting 0, the node containing 3 becomes unbalanced:

      

      After rebalancing:

      

   2. After inserting 2, the node containing 3 becomes unbalanced:

      

      After rebalancing:

      

   3. After inserting 10, the node containing 6 becomes unbalanced:

      

      After rebalancing:

      

   4. After inserting 17, the node containing 6 becomes unbalanced:

      

      After rebalancing:

      

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

   Answer:

   The following diagram shows how the tree grows:

   

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.

   Answer:

   1. One possible solution inserts all array elements into an AVL tree, and then for each element A[i], checks if (v - A[i]) is in the tree. However some extra care is needed to make sure we don't add an element A[i] to itself to get v.

      hasTwoSum(A, v):
      	Input:  array A[0..n - 1] of integers
      	        integer v
      	Output: true if A contains two elements that sum to v, false otherwise
      
      	if v is even and v/2 occurs more than once in A then
      		return true
      	end if
      
      	t = new AVL tree
      	for i = 0 up to n - 1 do
      		if 2 x A[i] =/= v then
      			insert A[i] into t
      		end if
      	end for
      	
      	for i = 0 up to n - 1 do
      		if (v - A[i]) is in t then
      			return true
      		end if
      	end for
      	
      	return false
      

      Here is a cleaner solution:

      hasTwoSum(A, v):
      	Input:  array A[0..n - 1] of integers
      	        integer v
      	Output: true if A contains two elements that sum to v, false otherwise
      
      	t = new AVL tree
      	
      	for i = 0 up to n - 1 do
      		if (v - A[i]) is in t then
      			return true
      		end if
      		insert A[i] into t
      	end for
      	
      	return false
      

   2. First solution: The first if statement runs in \( O(n) \) time, since counting the number of occurrences of a value in an array is \( O(n) \). The first for loop inserts at most \( n \) values into an AVL tree, and since AVL tree insertion is \( O(\log n) \), this loop runs in \( O(n \log n) \) time. The second for loop performs at most \( n \) searches in the AVL tree, and since searching in an AVL tree is \( O(\log n) \), this loop also runs in \( O(n \log n) \) time. Thus the time complexity of the algorithm is \( O(n) + O(n \log n) + O(n \log n) = O(n \log n) \). Notice how this algorithm is more efficient than the algorithm we developed in Week 3.

      Second solution: The for loop performs at most \( n \) searches and \( n \) insertions in the AVL tree, and since searching and inserting in an AVL tree are both \( O(\log n) \), the loop runs in \( O(n \log n) \) time. Thus, the time complexity of the algorithm is \( O(n \log n) \).

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

   Answer:

   The following diagram shows how the tree grows:

   

   Search costs (for tree after insertion of 10):

   • search(1): cmp(4), cmp(2), cmp(1) → cost = 3
   • search(7): cmp(4), cmp(6), cmp(8), cmp(7) → cost = 4
   • search(9): cmp(4), cmp(6), cmp(8), cmp(9) → cost = 4
   • search(13): cmp(4), cmp(6), cmp(8), cmp(9), cmp(10) → cost = 5

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) \))

   Answer:

   

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?

   Answer:

   1. Vertices are people (Facebook users)
   2. Edges are "friend" relationships
   3. No - if you are someone's friend, they are also your friend
   4. The degree of a vertex is the number of friends that the person represented by the vertex has
   5. Breadth-first search - find your immediate friends, then consider their friends, and so on