# Data structures

CPSC 131 Homework 9

Deadline:          Wednesday, April 24 (Mon Wed sections)

Thursday, April 25 (Tue Thu sections)

Turn in your submission as hard copy in class. Do not upload on TITANium.

#1 [6 points]

Given the AVL tree below:

1. (2 points) What is the height of each subtree in the tree? Write the height of each subtree and the balance factor next to each node in a manner similar to that of Zybooks participation activity 8.1.1

1. (2 points) Draw the AVL tree after a new node with key “57” is inserted. Is the new tree the result of a single rotation or a double rotation?

You may refer to the trinode restructuring handout at the end  of this homework assignment  or the AVL Tree slides.

1. (2 points) Draw the AVL tree after a new node with key “12” is inserted into the original tree. Do not consider the effects of prior question b. Is the new tree the result of a single rotation or a double rotation?

You may refer to the trinode restructuring handout at the end  of this homework assignment  or the AVL Tree slides.

#2 [4 points]

Create two AVL trees with 7 keys: A, B, C, D, E, F, and G. (There are 5,040 different key sequences that produce 429 unique trees. Of those trees, 17 are AVL trees.)

1. (2 points)Draw the shortest AVL tree containing these 7 keys.

1. (2 points) Draw one of the tallest possible AVL trees containing these 7 keys.

#3 [4 points]

Add a public member function to the BST class that returns the size of the tree—the number of the nodes in the tree. For simplicity, the class contains only the key and not a value. You may add any helper functions you find necessary. (Hint: think recursion)

template <typename T>

class Node {

T key;

Node<T>*            left;

Node<T>*            parent;

Node<T>*            right;

};

template <typename T>

class BST {

private:

Node<T> root;

public:

BST(): root(nullptr) { }

int getHeight();

// declare any helper functions here

}