Lab 5b

(100 pts)

Due Sunday, April 22

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 Apr 15 (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);

  1. Modify the find method in BSTY so that it keeps track of the number of comparisons needed to find a node.
  2. 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)
  3. 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).