Difference between revisions of "CISC220 F2021 Lab7"

From class_wiki
Jump to: navigation, search
(Created page with "==Lab #7== ===1. Written problems=== * '''(1 point)''' What are the minimum and maximum number of leaves in a binary heap of height ''h'', where a single-node tree is height...")
 
Line 1: Line 1:
 +
 
==Lab #7==
 
==Lab #7==
  
===1. Written problems===
+
I have provided a partial implementation of AVL trees [xxx here].  The AVLTree class is based on BSTree_Fast, but insert(), contains(), and findMax() have been written.  The executable is called "avl" and it expects the name of an input file on the command line.  Try running it on a few files before you start to program.  It will print out information about the (unbalanced) BST that has been constructed.
 +
 
 +
For this lab your job is to fill in as much of the ''updateBalanceFactors()'' function in avl.hh as you can, following Chapter 6.7.2 of the textbook and your lecture notes, so that the constructed trees are actually balanced..  This function is called automatically at the end of each insert().
 +
 
 +
===1. C++ programming exercises===
  
* '''(1 point)''' What are the minimum and maximum number of leaves in a binary heap of height ''h'', where a single-node tree is height 1? Show your reasoning.
+
* '''(2 points)''' Update the ''balanceFactor'' values as necessary in each AVLNode of the tree.  Note that as the textbook's pseudocode indicates (4th edition only, apparently), this only has to happen along the path from the inserted node to the root. The ''print_level_and_pretty()'' function prints the keys of each level's nodes in [http://en.wikipedia.org/wiki/Tree_traversal#Breadth-first level order], followed in square brackets by their (a) recursively computed balance factor and (b) balanceFactor variable.  (a) is done for you; you are just computing (b) a different wayYou will know you are correct when (a) and (b) are the same.  It also [http://leetcode.com/2010/09/how-to-pretty-print-binary-tree.html pretty prints] a pseudo-graphical representation of the tree (using only the first character of each key string) so that you can get a visual sense of its balance.
* '''(2 points)'''  
+
* '''(1.5 points)''' Take care of the "single rotation" case to rebalance the tree.  This should work for both the +2/+1 case and the -2/-1 case.  Rotation functions have already been written: ''rotate_right(t)'' performs a right rotation at node ''t'', and ''rotate_left(t)'' performs a left rotation at node ''t''.  You just need to do the correct rotation in the correct place.
** (a) Draw the tree after each insertion of the following integer keys into a max heap, both before and after upheaping: 80, 40, 30, 60, 81, 90, 100, 10. 
+
* '''(1.5 points)''' Take care of the "double rotation" case to rebalance the tree.  This should work for both the +2/-1 case and the -2/+1 case.
** (b) Now removeMax() is called on the tree just created.  Show the tree after each step of the process of removeMax(), before and after downheapingClearly label or mark what is going on for both (a) and (b).
 
* '''(2 points)''' Write a C++ function ''int removeMax()'' for a heap that is represented in array form (root at index 1, etc.).  Assume the array is called H and that ''int leftChild(int i)'', ''int rightChild(int i)'', and ''int parent(int i)'' functions are defined which return the array ''index'' of those nodes given the index of node ''i''.
 
  
 
===2. Submission===
 
===2. Submission===
  
* Make a '''PDF file''' <Your Name>_Lab7_README.pdf with your answers to the written exercises
+
* Include a '''PDF file''' <Your Name>_README.pdf which contains the inputs and outputs of your program, etc.  You should (a) list the input files you tested, (b) show the output of calling ''print_level_and_pretty()'' on the final tree WITH AND WITHOUT calling updateBalanceFactors() if the tree height is <= 7, and (c) show the "statistics" (from the driver() function in main.cpp) for all input files regardless of size, again with and without calling updateBalanceFactors().  Test on at least 3inarow.txt, 5words_doi.txt, partial_alphabet.txt, firstline_wap.txt, and the three cleaned files from Lab #5 (DOI, BTS, and GE).
* No need to compress or archive the PDF, since that's all you're turning in.
+
* Create a single tar/zip file out of the top-level and all subdirectories.  This archive file should be named <Your Last Name>_Lab7.tar (or .zip, etc.).  
* Submit it in Canvas by ''midnight at the end of Thursday, October 30''
+
* Submit it in Canvas by ''midnight at the end of Tuesday, October 19''

Revision as of 13:58, 13 October 2021

Lab #7

I have provided a partial implementation of AVL trees [xxx here]. The AVLTree class is based on BSTree_Fast, but insert(), contains(), and findMax() have been written. The executable is called "avl" and it expects the name of an input file on the command line. Try running it on a few files before you start to program. It will print out information about the (unbalanced) BST that has been constructed.

For this lab your job is to fill in as much of the updateBalanceFactors() function in avl.hh as you can, following Chapter 6.7.2 of the textbook and your lecture notes, so that the constructed trees are actually balanced.. This function is called automatically at the end of each insert().

1. C++ programming exercises

  • (2 points) Update the balanceFactor values as necessary in each AVLNode of the tree. Note that as the textbook's pseudocode indicates (4th edition only, apparently), this only has to happen along the path from the inserted node to the root. The print_level_and_pretty() function prints the keys of each level's nodes in level order, followed in square brackets by their (a) recursively computed balance factor and (b) balanceFactor variable. (a) is done for you; you are just computing (b) a different way. You will know you are correct when (a) and (b) are the same. It also pretty prints a pseudo-graphical representation of the tree (using only the first character of each key string) so that you can get a visual sense of its balance.
  • (1.5 points) Take care of the "single rotation" case to rebalance the tree. This should work for both the +2/+1 case and the -2/-1 case. Rotation functions have already been written: rotate_right(t) performs a right rotation at node t, and rotate_left(t) performs a left rotation at node t. You just need to do the correct rotation in the correct place.
  • (1.5 points) Take care of the "double rotation" case to rebalance the tree. This should work for both the +2/-1 case and the -2/+1 case.

2. Submission

  • Include a PDF file <Your Name>_README.pdf which contains the inputs and outputs of your program, etc. You should (a) list the input files you tested, (b) show the output of calling print_level_and_pretty() on the final tree WITH AND WITHOUT calling updateBalanceFactors() if the tree height is <= 7, and (c) show the "statistics" (from the driver() function in main.cpp) for all input files regardless of size, again with and without calling updateBalanceFactors(). Test on at least 3inarow.txt, 5words_doi.txt, partial_alphabet.txt, firstline_wap.txt, and the three cleaned files from Lab #5 (DOI, BTS, and GE).
  • Create a single tar/zip file out of the top-level and all subdirectories. This archive file should be named <Your Last Name>_Lab7.tar (or .zip, etc.).
  • Submit it in Canvas by midnight at the end of Tuesday, October 19