Difference between revisions of "CISC220 F2021 Lab7"
From class_wiki
(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...") |
(→2. Submission) |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | |||
==Lab #7== | ==Lab #7== | ||
| − | ===1. | + | I have provided a partial implementation of AVL trees [https://drive.google.com/file/d/1u2XX3kbdYxhPbY-96xirobI640JIk51v/view?usp=sharing 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(). Don't worry about post-delete() situations. | ||
| + | |||
| + | ===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 [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 way. You 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. |
| − | + | * '''(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=== | ===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 | + | * Submit it in Canvas by ''midnight at the end of Friday, October 22'' |
Latest revision as of 15:36, 13 October 2021
Lab #7
I have provided a partial implementation of AVL trees 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(). Don't worry about post-delete() situations.
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 Friday, October 22
