CS 202 Fundamental Structures of Computer Science II

Assignment 3 – Heaps and Balanced Search Trees

Due Date: July 13, 2010 (Tuesday)

Question-1 (10points)

Trace the action of heapSort on the following array.

7 8 3 6 1 9 5 2 4

Question-2 (10 points)

a) Starting with an empty heap, insert the following keys into the heap in the given order:

Keys: 1 8 3 4 5 7 6 9 2

Show the heap after each insertion.

b) Delete the key 9 from this heap. Show the heap after the deletion.

Question-3 (20 points)

Starting with an empty tree, insert the following keys into the table in the given order

Keys: 6 1 7 9 4 3 2 5

and then delete the keys 9 6 (in the given order) from the tree. [On deleting an internal node, use the inorder successor of the node.]

Assume that the table is implemented as

a) An AVL tree

b) A 2-3 tree

and show the underlying tree after each insertion and deletion.

Question-4 (60 points)

Submit a program in C++ language for accepting insertion and deletion requests on an AVL tree of positive integers from standard input and output the edges using its preorder traversal. Initially, the AVL tree is empty. On deleting an internal node, use the inorder predecessor of the node. The print format of an AVL tree should be as follows:

(root, its left subtree, its right subtree) if the tree is not empty

NULL if the tree is empty.

Formats:

Please enter your request (i=insert, d=delete, p=print e=exit) : p

AVL Tree: NULL

Please enter your request (i=insert, d=delete, p=print e=exit) : i 20

Please enter your request (i=insert, d=delete, p=print e=exit) : p

AVL Tree: (20,NULL,NULL)

Please enter your request (i=insert, d=delete, p=print e=exit) : i 10

Please enter your request (i=insert, d=delete, p=print e=exit) : p

AVL Tree: (20,(10,NULL,NULL),NULL)

Please enter your request (i=insert, d=delete, p=print e=exit) : i 5

Please enter your request (i=insert, d=delete, p=print e=exit) : p

AVL Tree: (10,(5,NULL,NULL),(20,NULL,NULL))

Please enter your request (i=insert, d=delete, p=print e=exit) : i 30

Please enter your request (i=insert, d=delete, p=print e=exit) : p

AVL Tree: (10,(5,NULL,NULL),(20,NULL,(30,NULL,NULL)))

Please enter your request (i=insert, d=delete, p=print e=exit) : d 20

Please enter your request (i=insert, d=delete, p=print e=exit) : p

AVL Tree: (10,(5,NULL,NULL),(30,NULL,NULL))

Please enter your request (i=insert, d=delete, p=print e=exit) : e

Bye!

Hand-in:

· You should give the hard copy of your homework that includes the solutions of first three questions during the class hour on the due date. Make sure that your homework must be a printer output with your names, and student ids on them; otherwise it will not be graded.

· You should also send an email message to your TA, Sefa Kılıç (sefak@cs.bilkent.edu.tr), attaching with one zipped file (named as yournameyourlastname.zip ) which contains:

1. A Word file containing the solutions of first three questions of your homework (hw3.doc) and

2. Another file (hw3Q4.cpp) containing source code of your C++ program in Question-4.

· Make sure that the subject field of your email is “CS202 HW3”. You should send this email message before 6:00 pm on the due date. Do not forget to put your name in the header comment in your program.

· You are free to write your programs in any environment (you may use either Linux or Windows). On the other hand, we will test your programs on “dijkstra.ug.bcc.bilkent.edu.tr” and we will expect your programs to compile and run on the “dijkstra” machine. If we could not get your program properly work on the “dijkstra” machine, you would lose a considerable amount of points. Therefore, we recommend you to make sure that your program compiles and properly works on “dijkstra.ug.bcc.bilkent.edu.tr” before submitting your assignment.

· Keep all the files before you receive your grade.

· DO IT YOURSELF. CHEATING WILL BE HEAVILY PUNISHED.