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 bemodifying 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 pointof producing output, or it will not be graded. At this point in the semester you should be proficientenough at programming in c++ so that your code produces output at least close to the desired output fora grade.Part 1:Binary Search Tree code, due Oct 24 (hopefully you’ve already finished this)Part 2 (60 pts): AVL TreeModify 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, rotatesappropriately.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 mymainAVL.cpp files and run them with (note that I included specifications of when I rotated right and leftand double-rotated, for your information). For this part, you will have to uncomment out PART 2 in themain() function in mainAVL.cpp. Your output should look like the output in output2.txt. (35 pts forcorrect order of letters, 25 pts for correct height at each node)Part 3 (40 pts): Dictionary look-upMake 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 stri代做Lab 4b作业、代写C/C++编程设计作业、代做C/C++语言作业、代写AVL Tree留学生作业 调试Matlangs. It should set data to bethe first input string, and def to be the second input strings. All the other fields should be set asthey were in the first constructor.4. Modify the printNode method in the NodeT class to print out the data, then the height, andthen the def5. In BSTY overload the method insertit so that it takes 2 input parameters (both strings). Withinthe second method, change each NodeT constructor call to take 2 input parameters instead ofone (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 tofind a node.7. In TreePuzzle.cpp, uncomment out Part 3. You should get the same output as that in the fileoutput3.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: thetree is NOT complete, although it should be balanced, so the count will be 1 more than theperfect 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 changesin pointers, both to children and parents. When you do a rotation, which nodes’ parentschange? Make sure you include all of those changes in your code.3. Remember to check for NULL pointers4. When rotating, if you rotate one node down, and another node up, you must modify the heightof 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 willhave no parents). 转自：http://ass.3daixie.com/2018110427695161.html