Lab 4b
(100 pts)
Due Oct 31, midnight (scary!)
You may work with a partner, or you may work on your own. You know the rules.
This lab requires the NodeT class definitions and the BSTY class definitions from last class. You will be
modifying both to create an AVL Tree.
Note: the lab must compile in order to be graded. In addition, for this lab, the lab must run to the point
of producing output, or it will not be graded. At this point in the semester you should be proficient
enough at programming in c++ so that your code produces output at least close to the desired output for
a grade.
Part 1:
Binary Search Tree code, due Oct 24 (hopefully you’ve already finished this)
Part 2 (60 pts): AVL Tree
Modify the BSTY class so that you’ve included the following methods:
NodeT * BSTY::rotateRight(NodeT *n)
NodeT * BSTY::rotateLeft(NodeT *n)
In addition, modify your adjustHeights method so that it checks balances and, when necessary, rotates
appropriately.
You may wish to write a helper method
int BSTY::findBalance(NodeT *n)
that finds the balance of node n, and returns that balance.
Once you have this code working, download and run my updated TreePuzzle.cpp and hpp files and my
mainAVL.cpp files and run them with (note that I included specifications of when I rotated right and left
and double-rotated, for your information). For this part, you will have to uncomment out PART 2 in the
main() function in mainAVL.cpp. Your output should look like the output in output2.txt. (35 pts for
correct order of letters, 25 pts for correct height at each node)
Part 3 (40 pts): Dictionary look-up
Make sure you’ve downloaded strangeAnimalDict.txt. This is the file that will be read into the AVL Tree.
1. Modify the NodeT to include a string field called def (which will hold the word definitions).
2. In the currently existing NodeT constructor, set the def field to be a blank string (“”);
3. Create a second constructor that takes as input parameters 2 strings. It should set data to be
the first input string, and def to be the second input strings. All the other fields should be set as
they were in the first constructor.
4. Modify the printNode method in the NodeT class to print out the data, then the height, and
then the def
5. In BSTY overload the method insertit so that it takes 2 input parameters (both strings). Within
the second method, change each NodeT constructor call to take 2 input parameters instead of
one (so it will look something like this:
bool BSTY::inserting(string x, string y) {
…
root = new NodeT(x,y);
6. Modify the find method in BSTY so that it keeps track of the number of comparisons needed to
find a node.
7. In TreePuzzle.cpp, uncomment out Part 3. You should get the same output as that in the file
output3.txt.(30 pts – 10 pts for correct in-order traversal, 15 pts for correctly finding all nodes,
10 pts for correct comparison count)
8. In comments at the top of your mainAVL.cpp file, answer the following questions in comments:
How many nodes in the dictionary tree?
What is the maximum number of comparisons needed to find any node in the tree? (Hint: the
tree is NOT complete, although it should be balanced, so the count will be 1 more than the
perfect case). (5 pts)
HINTS FOR THIS LAB:
1. Make sure you leave time for debugging this lab.
2. Remember the parents!!!! Draw out a rotation, including all changes in height and all changes
in pointers, both to children and parents. When you do a rotation, which nodes’ parents
change? Make sure you include all of those changes in your code.
3. Remember to check for NULL pointers
4. When rotating, if you rotate one node down, and another node up, you must modify the height
of the node that rotated to the child position before you modify the height of the new parent
(the node that just rotated).
5. Make sure you check for the condition of a node being the root of the tree (in which case it will
have no parents).
版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。