C++ Programming
For this assignment, write a class named AVLTree that extends class Tree that you wrote for HW-06. Class AVLTree will implement the algorithms for an AVLTree discussed in Unit XI.
Use the following UML diagram and attribute descriptions.
AVLTree Attributes:
- height – returns the height of a tree. Accepts the root pointer for the tree to find the height of.
- rotateRight – implements the logic for a right rotation. Accepts the pointer for the node to be rotated, by reference.
- rotateLeft – implements the logic for a left rotation. Accepts the pointer for the node to be rotated , by reference.
- rotateRightLeft – implements the logic for a right-left rotation. Accepts the pointer for the node to be rotated , by reference.
- rotateLeftRight – implements the logic for a left-right rotation. Accepts the pointer for the node to be rotated , by reference.
- difference – returns balance factor for a node. Accepts the pointer for the node as it’s argument.
- balance – brings the AVLTree back into balance, if necessary. Accepts the pointer for a node that needs to be adjusted.
Notes:
- The add and remove methods in class AVLTree override the base class versions, calling balance as required.
- Be sure to include preprocessor guards and to #include “Tree.h” in AVLTree.h, otherwise you won’t be able to inherit from it.
- You may use the Tree class I wrote as a solution to HW-06 if you want as the base class for your AVLTree class.
- Accessors should always be marked const.
- Don’t forget to balance the root node, that’s why you are overriding the public add and remove methods.
- By extending class Tree (inheritance), we’re saving ourselves from having to rewrite all that code from scratch, which is a core benefit of object-oriented programming. See Code Re-use (Links to an external site.), and Inheritance (Links to an external site.).
- You’ll need to make one slight modification to Tree.h. Change Node and root to protected.
Submission Instructions:
- Place the code for class AVLTree, and only class AVLTree, in it’s own header file named AVLTree.h.
- Submit both Tree.h and AVLTree.h when you are done.