Week 05 Tutorial Questions

Balanced Trees, Graph Basics

Balancing Trees

  1. Show how the following tree would change if we do a right rotation on the node containing 10 followed by a left rotation on the node containing 6.

  2. Show the result of performing the insert-at-root operation with the value 7 in this binary search tree:

AVL Trees

AVL trees use the following node definition:

struct node {
    int data;
    int height;
    struct node *left;
    struct node *right;
};

You may find these resources on AVL trees useful:

  1. 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. 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. 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.
Graph Representation

  1. Consider the following graph

    The edges are labelled simply for convenience in describing graph properties.

    1. How many edges does it have?
    2. How many cycles are there in the graph?
    3. How many cliques are there in the graph?
    4. What is the degree of each vertex?
    5. How many edges in the longest path from 5 to 8?
      (without traversing any edge more than once)

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

  3. How is the adjacency matrix for a directed graph different to that for an undirected graph?

  4. 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?
A Tutor's Worst Nightmare

  1. The following piece of code has several style issues. Identify and fix them.

    Click here to download the file and a Makefile for compiling it.

    #include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

void freeList(struct Node *head) {
	if (head == NULL) {
	return;
	}
	// Frees the list by iterating through the list, using a temporary element and freeing the elements by using free (hopefully this comment is useful and helps out)
	struct Node *Temp = head;
	while (head != NULL) {
	    Temp = head;
	    head = head->next;
	    free(Temp);
	}
}
void print_list(struct Node *node) {
    while (node->next != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("%d\n", node->data);
    return;
}
struct Node *add(struct Node *a, int data) {
    // malloc the node
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    // set the node's data field
    newNode->data = data;
    // set the node's next field to NULL
    newNode->next = NULL;
	if (a == NULL) {
		a = newNode;
	} else {
        struct Node *lastNode = a;
        while (lastNode->next != NULL) {
            lastNode = lastNode->next;
        }
        lastNode->next = newNode;
	}
	return a;
}
int main() {
	struct Node *head = NULL;
	head = add(head, 1);
	head = add(head, 2);
	head = add(head, 3);
	head = add(head, 4);
	print_list(head);
	freeList(head);
	return 0;
}