All of the work in this project is my own! I have not left copies of my code in public folders on university computers. I have not given any of this project to others. I will not give any portion of this project to others taking this class. I realize that the penalty for turning in work that is not my own can range from an "F" in the class to dismissal from Trinity University.
Print Name __________________________ Time Required = ______.____ Hrs.
Signature __________________________
Print Name __________________________ Time Required = ______.____ Hrs.
Signature __________________________
__________ {T/F} Although we started this lab as a team, we finished it individually.
AVL Direct Access I Lab
Individual/Team (1-2 Persons) Assignment
Make Any Changes Necessary For Compilation
50 Points
1] Copy folder DA-BinTree2 Create a folder, called DA-AVL-Tree1.
2] Remove Node.cpp and Node.hpp from your project. Remove the two files from your folder.
3] Download the AVLNode.cpp & AVLNode.cpp. Add them to the project.
4] Replace Node with AVLNode throughout the project. Compile --> Your project should work!
5] Change the name of file BinTree.hpp to AVLTree.hpp. Change the name of file BinTree.cpp to AVLTree.cpp.
6] Add AVLTree.hpp and AVLTree.cpp to the project.
7] Replace BinTree with AVLTree throughout the project.
8] Replace BINTREE with AVLTREE throughout the project. Compile --> Your project should work!
9] Remove function Delete and the block of test code for function Delete.cti
10] Compile --> Your project should work!
11] Function main is to call TestDA_AVLTree1, TestDA_AVLTree2, TestDA_AVLTree3, TestDA_AVLTree4, & TestDA_AVLTree5; Add a prototype and function TestDA_AVLTree5 to AVLTree.cpp. You are to write all of your own test code.
void TestDA_AVLTree5(void)
{
puts("\n\n*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("********************** Start TestDA_AVLTree5 *********************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************\n\n");
Student
Students[30];
Part
Parts[80];
Auto
Autos[30];
Students[0].Set("Brown, Chris", 101, MALE);
Students[1].Set("Weston, Clay", 102, MALE);
Students[2].Set("McBryde, Michael", 103, MALE);
Students[3].Set("Elsaifi, Leslie", 104, FEMALE);
Students[4].Set("Kelly, Nick", 105, MALE);
Students[5].Set("Wilson, Jennifer", 106, FEMALE);
Students[6].Set("Silliman, Mark", 107, MALE);
Students[7].Set("Merka, Lauren", 108, FEMALE);
Students[8].Set("Guest, Ben", 109, MALE);
Students[9].Set("Condon, Ryan", 200, MALE);
Students[10].Set("Bertles, Joe, Ryan", 201, MALE);
Students[11].Set("Gonzaba, Jodi", 202, FEMALE);
Students[12].Set("Crowe, Loren", 203, MALE);
Students[13].Set("Marquez, Angel", 204, MALE);
Students[14].Set("Houck, David", 205, MALE);
Students[15].Set("Ross, Garrett, David", 206, MALE);
Students[16].Set("Schwartz, Scott, David", 207, MALE);
Students[17].Set("Caille, Ryan", 208, MALE);
Students[18].Set("Schubet, Kurt", 209, MALE);
Students[19].Set("Canion, Todd", 300, MALE);
Students[20].Set("West, Paul", 301, MALE);
Students[21].Set("Haik, Adrienne", 302, FEMALE);
Students[22].Set("Swanson, Anna", 303, FEMALE);
Students[23].Set("Jones, Travis", 304, MALE);
Students[24].Set("Stansell, Kevin", 305, MALE);
Students[25].Set("Lara, Domingo", 306, MALE);
Students[26].Set("Rodriquez, Anthony", 307, MALE);
Students[27].Set("Mohajan, Rohit", 308, MALE);
Students[28].Set("Middleton, Phillip", 309, MALE);
Students[29].Set("Schwartz, Scott, David", 204, MALE);
Autos[0].Set("Corvette Stingray", 101, CONVERTABLE);
Autos[1].Set("Porche 911", 102, CONVERTABLE);
Autos[2].Set("VW", 103, CONVERTABLE);
Autos[3].Set("Limo", 104, COUP);
Autos[4].Set("Lincoln Continental", 105, CONVERTABLE);
Autos[5].Set("Maxima", 106, COUP);
Autos[6].Set("Mercury Cougar", 107, CONVERTABLE);
Autos[7].Set("Mustang", 108, COUP);
Autos[8].Set("Explorer", 109, CONVERTABLE);
Autos[9].Set("Lincoln Towncar", 200, CONVERTABLE);
Autos[10].Set("Chevrolet Capri", 201, CONVERTABLE);
Autos[11].Set("Jaguar", 202, COUP);
Autos[12].Set("Honda 2000", 203, CONVERTABLE);
Parts[1].Set("Basketball", 111, 3, 10, 25.00);
Parts[2].Set("Football", 105, 3, 15, 25.00);
Parts[3].Set("Tennis Balls", 127, 3, 6, 3.00);
Parts[4].Set("Golf Balls", 104, 3, 10, 12.00);
Parts[5].Set("Soccer Ball", 141, 3, 5, 40.00);
Parts[6].Set("GB Hard Drive", 120, 2, 12, 37.95);
Parts[7].Set("Microwave", 112, 1, 15, 59.80);
Parts[8].Set("Gas Stove", 136, 1, 6, 237.69);
Parts[9].Set("Cup", 156, 3, 23, 8.88);
Parts[10].Set("Baseball", 123, 3, 10, 8.00);
Parts[11].Set("Teather Ball", 155, 3, 4, 14.00);
Parts[12].Set("Golf Tees", 125, 3, 60, 2.00);
Parts[13].Set("Tennis Shoes", 101, 3, 10, 100.00);
Parts[14].Set("Ping Pong Balls", 154, 3, 10, 3.00);
Parts[15].Set("MotherBoard", 113, 2, 11, 55.00);
Parts[16].Set("SDRAM", 135, 2, 30, 40.01);
Parts[17].Set("Iron", 132, 1, 21, 38.77);
Parts[18].Set("Long Socks", 153, 3, 34, 9.99);
Parts[19].Set("CD-ROM", 110, 2, 11, 30.12);
Parts[20].Set("CD-RW", 124, 2, 26, 56.13);
Parts[21].Set("Thin Monitor", 140, 2, 5, 89.00);
Parts[22].Set("Large Monitor", 139, 2, 9, 78.99);
Parts[23].Set("Dish Washer", 117, 1, 10, 120.78);
Parts[24].Set("Tennis Racquet", 118, 3, 4, 80.00);
Parts[25].Set("Golf Club", 152, 3, 14, 49.00);
Parts[26].Set("Gym Bag", 151, 3, 10, 14.00);
Parts[27].Set("Golf Glove", 128, 3, 11, 14.06);
Parts[28].Set("Golf Bag", 150, 3, 5, 99.00);
Parts[29].Set("Squash Racquet", 119, 3, 2, 80.00);
Parts[30].Set("Squash Balls", 149, 3, 3, 8.00);
Parts[31].Set("Archery Set", 148, 3, 1, 25.00);
Parts[32].Set("Compound Bow", 102, 3, 1, 80.00);
Parts[33].Set("Arrows", 147, 3, 100, 6.00);
Parts[34].Set("Quiver", 131, 3, 2, 16.00);
Parts[35].Set("Racquet Balls", 146, 3, 15, 6.00);
Parts[36].Set("Baseball Bats", 106, 3, 4, 48.00);
Parts[37].Set("Golf Driver", 130, 3, 3, 99.00);
Parts[38].Set("Knee Pads", 103, 3, 4, 8.00);
Parts[39].Set("Soccer Cleats", 121, 3, 2, 48.00);
Parts[40].Set("Shin Guards", 137, 3, 5, 48.05);
Parts[41].Set("Printer", 145, 2, 14, 29.98);
Parts[42].Set("Laser Printer", 108, 2, 13, 43.99);
Parts[43].Set("Printer Cables", 144, 2, 12, 9.99);
Parts[44].Set("Tranportable Fan",116, 1, 6, 45.67);
Parts[45].Set("Dirt Devil", 114, 1, 11, 48.80);
Parts[46].Set("B-Ball Shoes", 143, 3, 9, 135.99);
Parts[47].Set("Case", 134, 2, 4, 20.00);
Parts[48].Set("Graphics Card", 142, 2, 7, 58.00);
Parts[49].Set("Sound Card", 107, 2, 4, 34.99);
Parts[50].Set("CD Player", 138, 1, 16, 57.75);
Parts[51].Set("Floppy Drive", 126, 2, 4, 12.00);
Parts[52].Set("Removeable Drive",122, 2, 12, 59.94);
Parts[53].Set("External zip", 129, 2, 8, 67.75);
Parts[54].Set("Floppy's", 115, 2, 99, .50);
Parts[55].Set("Mouse", 109, 2, 35, 7.99);
Parts[56].Set("Keyboard", 133, 2, 44, 12.99);
// -------------------------------------------------------------------------------
if (DA_AVLTREE_DIAGNOSTICS_LEVEL <= 60)
{
puts("\n\n\n\n");
puts ("**************************************************************************************************");
puts ("**************************************************************************************************");
puts ("******************************** AVL Single Rotate Left *******************************");
puts ("******************************** DA_AVLTREE_DIAGNOSTICS_LEVEL = 60 *******************************");
puts ("**************************************************************************************************");
puts ("**************************************************************************************************");
puts("\n");
}
// -------------------------------------------------------------------------------
puts("\n\n*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("********************** End TestDA_AVLTree5 *********************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************");
puts("*******************************************************************\n\n");
}
12] It is essential that all functions work properly before you continue! Compile --> Your project should work!
13] Your program must include the following: (you may use them if you like - I will)
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
// TestAVLIntegrity //
// //
// Purpose : Traverse the tree to make sure that the nodes occur in ascending //
// order and that the balance factors are in the range -1, 0, +1. //
// Explicitly return true if valid; otherwise false. //
// //
// Written By : Dr. Thomas E. Hicks Environment : Windows XP //
// Date : XX/XX/XXXX Compiler : Visual NET //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
template <class HeaderType, class InfoType>
bool DA_AVLTree <HeaderType, InfoType> ::TestAVLIntegrity (long int HeaderNo)
{
HeaderType
Header;
NodePtr
Ptr;
AVLNode<InfoType>
Node;
if (Empty(HeaderNo))
return (true);
ValidAVLTree = true;
ReadRecord(&Header, HeaderNo, hfp);
Ptr = Header.Root;
ReadRecord(&Node, Ptr, nfp);
while(Node.Left != NILL)
{
Ptr = Node.Left;
ReadRecord(&Node, Ptr, nfp);
}
HighValue = Node.Info;
TestAVLIntegrityHelper (Header.Root);
return (ValidAVLTree);
}
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
// TestAVLIntegrityHelper //
// //
// Purpose : Change ValidAVLTree to false if the inorder traversal does not //
// continue to increase. Change the ValidAVLTree to false if the //
// balance factor is outside the range -1, 0, +1. //
// //
// Written By : Dr. Thomas E. Hicks Environment : Windows XP //
// Date : XX/XX/XXXX Compiler : Visual NET //
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
template <class HeaderType, class InfoType>
void DA_AVLTree <HeaderType, InfoType> ::TestAVLIntegrityHelper(NodePtr Ptr)
{
AVLNode <InfoType>
Node;
if (Ptr != NILL)
{
ReadRecord(&Node, Ptr, nfp);
TestAVLIntegrityHelper (Node.Left);
ReadRecord(&Node, Ptr, nfp);
if (Node.Info >= HighValue)
HighValue = Node.Info;
else
{
ValidAVLTree = false;
printf ("\nData Out Of Order = Node # %ld\n", Ptr);
}
if ((Node.BalanceFactor > 1) || (Node.BalanceFactor < -1))
{
ValidAVLTree = false;
printf ("\nInvalid Balance Factor = Node # %ld\n", Ptr);
}
ReadRecord(&Node, Ptr, nfp);
TestAVLIntegrityHelper (Node.Right);
}
}
14] Your class definition must include, but is not limited to, the following: Compile --> Your project should work!
template <class HeaderType, class InfoType>
class DA_AVLTree
{
public:
DA_AVLTree(char HeaderFileName[], char NodeFileName[],
long int NoHeaders, long int NoNodes);
DA_AVLTree(char HeaderFileName[], char NodeFileName[]);
~DA_AVLTree(void);
void CreateHeaderNodes(char HeaderFileName[], long int NoHeaders);
void CreateNodes(char NodeFileName[], long int NoNodes);
NodePtr GetNode(void);
void FreeNode(NodePtr OldNodePtr);
bool Empty (long int HeaderNo);
bool SetRight (long int HeaderNo, InfoType NewInfo, NodePtr MotherPtr);
bool SetLeft (long int HeaderNo, InfoType NewInfo, NodePtr MotherPtr);
bool Inplace (long int HeaderNo, InfoType NewInfo);
bool ValidHeader(long int HeaderNo);
bool ValidNode(long int NodeNo);
void DeleteTree(long int HeaderNo);
void InitializeNoNodes();
void DisplayNoNodes(char Message [] ="");
bool UpdateBalanceFactors(NodePtr HeaderNo, ????);
bool RotateRight(NodePtr HeaderNo, ????);
bool RotateLeft(NodePtr HeaderNo, ????);
bool DoubleRotateRight(NodePtr HeaderNo, ????);
bool DoubleRotateLeft(NodePtr HeaderNo, ????);
void Display (char Message[] = "");
void DisplayNodeFile(char Message[] = "");
void DisplayHeaderFile(char Message[] = "");
void QuickAndDirtyIntegerDisplay(long int HeaderNo, char Message[] = "");
void QuickAndDirtyIntegerDisplayHelper(NodePtr Ptr);
void InorderTraversalDisplay (long int HeaderNo, char Message[] = "");
void InorderHelper(NodePtr Ptr);
void PreorderTraversalDisplay (long int HeaderNo, char Message[] = "");
void PreorderHelper(NodePtr Ptr);
void PostorderTraversalDisplay (long int HeaderNo, char Message[] = "");
void PostorderHelper(NodePtr Ptr);
void NoNodesAtEachLevelTraversalDisplay (long int HeaderNo, char Message[]="");
void NoNodesAtEachLevelHelper(NodePtr Ptr);
void DisplayLoadBalanceStatistics(long int HeaderNo, char Message[]="");
bool TestAVLIntegrity (long int HeaderNo);
void TestAVLIntegrityHelper(NodePtr Ptr);
FILE
* nfp,
* hfp;
NodePtr
Avail;
long int
TempCounter,
LevelNo,
NoNodes[5001],
NoRotateRightRotations,
NoRotateLeftRotations,
NoDoubleRotateRightRotations,
NoDoubleRotateLeftRotations;
AVLNode<InfoType>
Node;
InfoType
HighValue;
bool
ValidAVLTree;
};
15] Although your class must include the methods and declarations above, feel free to add as many other functions and variables as you need. Some of you will choose to add a stack? If you decide to add a FatherPtr to the AVLNode class, modify all displays to show the FatherPtr.
Stack <long int> TreePtrs(500);
16] Implement the RotateRight, RotateLeft, and UpdateBalanceFactors work with your AVL Trees.
////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// // UpdateBalanceFactors // // // // Purpose : ??????????????????????????????????????????????????????????????? // // // // Written By : ???????????????? Environment : Windows XP Home // // Date.......: xx/xx/xxxx Compiler....: Visual Studio Net [C++] // ////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// // RotateRight // // // // Purpose : ??????????????????????????????????????????????????????????????? // // // // Written By : ???????????????? Environment : Windows XP Home // // Date.......: xx/xx/xxxx Compiler....: Visual Studio Net [C++] // ////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////// // RotateLeft // // // // Purpose : ??????????????????????????????????????????????????????????????? // // // // Written By : ???????????????? Environment : Windows XP Home // // Date.......: xx/xx/xxxx Compiler....: Visual Studio Net [C++] // ////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////
17] [6 Points] Create a DA-AVLTree.cpp file with testing for RotateLeft and RotateRight. This testing must include at least one testing example for each of the following datatypes; it is essential that your trees work for more than Integers.
PartTreeHeader & Part
AutoTreeHeader & Auto
StudentTreeHeader & Student
IntegerTreeHeader & Integer
18] When you are convinced that your program is working correctly, place a copy of this folder (1) in your "To Be Graded Folder" On Ananke (2) on you Y drive and (3) on your personal computer.
19] Print DA_AVLTree.hpp & DA_AVLTree.cpp
Turn In The Following [Staple or Bind In This Order!]
A] Copy of Page 1 assignment sheet. Using an ink pen, print your name(s) and sign this lab at the top.
B] Listings DA_AVL_Tree.hpp & DA_AVL_Tree.cpp