Faculty of Computer Science and Engineering
Department of Computer Science

1/3
DATA STRUCTURES & ALGORITHMS
Tutorial 4 Questions
AVL Tree and Heap

Part 1. AVL Tree
Required Questions

Question 1.
For each of the following key sequences determining the AVL tree obtained when the keys are inserted
one-by-one in the order given into an initially empty tree:

a) 1, 2, 3, 4, 5, 6, 7.
b) 4, 2, 1, 3, 6, 5, 7.
c) 1, 6, 7, 2, 4, 3, 5.
d) 45, 9, 2, 17, 84, 92, 71, 18, 30, 62, 55, 20, 27 Question 2.
For each of the AVL trees obtained in Question 1 determine the tree obtained when the root is withdrawn.

Question 3.
Write a global function in pseudo code to generate an AVL tree from an input list by insert elements in the
list into an initial empty AVL. Refer to Question 1 for an example.

algorithm generateAVLfromList (val list <List>)
This algorithm generate a AVL from the input list


Operation

Complexity

Init

Init the DS with n real numbers (unordered)

O(nlogn)

Insert(x)

Insert x to the DS

O(logn)

findMin

Return the value of the minimal element

O(logn
)

findMax

Return the value of the maximal element

O(logn
)


Question 7.
Show the heap (tree) you will have after inserting the following values:
a) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
b) 8, 4, 3, 6, 11, 9, 10, 10, 9
c) 3, 1, 4, 1, 5, 9, 2, 6, 5, 4
d) 2, 7, 1, 8, 2, 8, 1, 8, 2
e) 45, 9, 2, 17, 84, 92, 71, 18, 30, 62, 55, 20, 27

Question 8.
Show the heap (tree) you will have after removing (from 1-3 times) the root element of the tree generated
in the all cases of the previous question.
Advanced Questions

Question 9.
The following class definition will be used for the problem that follow:
public class BinaryTree <E extends Comparable<E>> {
private class Node {
E data;
Node left, right;
}
Node root;
}

Faculty of Computer Science and Engineering
Department of Computer Science

3/3
Write a recursive method called isCompleteBinaryTree() that returns true if the binary tree represents a
complete binary tree (one that satisfies the shape property for heaps).