PROGRAM 4

PROGRAM 4 // PROGRAM: PROGRAM4.CPP AUTHOR: ANTHONY F. ORTIZ // (NOTE: TURNED IN CLOSED HASH TABLE PROGRAM.) #include #include #include #include // OUTFILE. ofstream OUTFILE; // DELCARATION OF TREE NODE CLASS. template class TREE_NODE { protected: // KEY INFORMATION. ETYPE ELEMENT; // RIGHT AND LEFT POINTERS. TREE_NODE * LEFT; TREE_NODE * RIGHT; // TREE_NODE CONSTRUCTOR. TREE_NODE (ETYPE E = 0, TREE_NODE * L = 0, TREE_NODE * R = 0) : ELEMENT (E), LEFT (L), RIGHT (R) {} // HEIGHT OF A NODE IN A TREE. friend int HEIGHT (TREE_NODE * T); // A CLASS CALLED BINARY_SEARCH_TREE WILL USE THE TREE NODE // CLASS. friend class BINARY_SEARCH_TREE ; }; // DELCARATION OF BINARY SEARCH TREE CLASS. template class BINARY_SEARCH_TREE { // THESE PROCEDURES WILL BE CALLED BY THE PUBLIC ONES OF THE SAME // NAME. protected: // MAKE AN EMPTY TREE. void MAKE_EMPTY (TREE_NODE * & T); // INSERT AN ELEMENT INTO A TREE. void INSERT (const ETYPE & X, TREE_NODE * & T); // REMOVE AN ELEMENT FROM A TREE. void REMOVE (const ETYPE & X, TREE_NODE * & T); // PRINT THE TREE USING A INORDER TRAVERSAL. // THIS WILL PRINT IT IN SORTED ORDER. void PRINT_TREE (TREE_NODE * T) const; // COPY A TREE. TREE_NODE * COPY (const TREE_NODE * T); // FIND AN ELEMENT IN THE TREE. TREE_NODE * FIND (const ETYPE & X, TREE_NODE * T) const; // FIND THE MINIMUM ELEMENT IN THE TREE. TREE_NODE * FIND_MIN (TREE_NODE * T) const; // FIND THE MAXIMUM ELEMENT IN THE TREE. TREE_NODE * FIND_MAX (TREE_NODE * T) const; // ROOT OF THE TREE. TREE_NODE * ROOT; // THE LAST FIND IN A FIND ROUTINE. TREE_NODE * LAST_FIND; // THESE PROCEDURES WILL CALL THE PROTECTED ONES. public: // CONSTRUCTORS. BINARY_SEARCH_TREE () : ROOT (0), LAST_FIND (0) {} // ERROR MESSAGE WHEN PASS BY VALUE. BINARY_SEARCH_TREE (BINARY_SEARCH_TREE & VALUE) {OUTFILE << "TREE PASSED BY VALUE."; operator = (VALUE);} // DESTRUCTOR. virtual ~BINARY_SEARCH_TREE () {MAKE_EMPTY (ROOT); ROOT = LAST_FIND = 0;} // OPERATORS. // COPY A TREE. const BINARY_SEARCH_TREE & operator = (const BINARY_SEARCH_TREE & VALUE); // RETURN A TREE ELEMENT. ETYPE operator () () const {return LAST_FIND != 0 ? LAST_FIND -> ELEMENT : 0;} // MEMBER FUNCTIONS. // CALL MAKE_EMPTY AND ASSIGN 0 TO ROOT AND LAST FIND. void MAKE_EMPTY () {MAKE_EMPTY (ROOT); ROOT = LAST_FIND = 0;} // CALL PRINT_TREE. void PRINT_TREE () const {PRINT_TREE (ROOT);} // ASSIGN LAST_FIND TO THE FUNCTION FIND. virtual int FIND (const ETYPE & X) {return int (LAST_FIND = FIND (X, ROOT));} // ASSIGN LAST_FIND TO THE FUNCTION FIND_MIN. virtual int FIND_MIN () {return int (LAST_FIND = FIND_MIN (ROOT));} // ASSIGN LAST_FIND TO THE FUNCTION FIND_MAX. virtual int FIND_MAX () {return int (LAST_FIND = FIND_MAX (ROOT));} // CALL INSERT. virtual void INSERT (const ETYPE & X) {INSERT (X, ROOT);} // CALL REMOVE. virtual void REMOVE (const ETYPE & X) {REMOVE (X, ROOT);} }; // THIS IS THE IMPLEMENTATION OF A BINARY SEARCH TREE CLASS. // COPY A TREE USING '=' OPERATOR. template const BINARY_SEARCH_TREE & BINARY_SEARCH_TREE :: operator = (const BINARY_SEARCH_TREE & VALUE) { if (this != & VALUE) { MAKE_EMPTY (ROOT); ROOT = COPY (VALUE.ROOT); LAST_FIND = ROOT; } return * this; } // COPY THE TREE. template TREE_NODE * BINARY_SEARCH_TREE :: COPY (const TREE_NODE * T) { if (T != 0) return new TREE_NODE (T -> ELEMENT, COPY (T -> LEFT), COPY (T -> RIGHT)); else return 0; } // MAKE THE TREE EMPTY. template void BINARY_SEARCH_TREE :: MAKE_EMPTY (TREE_NODE * & T) { if (T != 0) { MAKE_EMPTY (T -> LEFT); MAKE_EMPTY (T -> RIGHT); delete T; T = 0; } } // FIND AN ELEMENT IN THE TREE. template TREE_NODE * BINARY_SEARCH_TREE :: FIND (const ETYPE & X, TREE_NODE * T) const { if (T == 0) return 0; else if (X < T -> ELEMENT) return FIND (X, T -> LEFT); else if (X > T -> ELEMENT) return FIND (X, T -> RIGHT); else return T; } // FIND THE MINIMUM ELEMENT IN THE TREE. template TREE_NODE * BINARY_SEARCH_TREE :: FIND_MIN (TREE_NODE * T) const { if (T == 0) return 0; else if (T -> LEFT == 0) return T; else return FIND_MIN (T -> LEFT); } // FIND THE MAXIMUM ELEMENT OF A TREE. template TREE_NODE * BINARY_SEARCH_TREE :: FIND_MAX (TREE_NODE * T) const { if (T == 0) return 0; else if (T -> RIGHT == 0) return T; else return FIND_MAX (T -> RIGHT); } // INSERT AN ELEMENT INTO THE TREE. template void BINARY_SEARCH_TREE :: INSERT (const ETYPE & X, TREE_NODE * & T) { if (T == 0) { T = new TREE_NODE (X); if (T == 0) OUTFILE << "OUT OF SPACE."; } else if (X < T -> ELEMENT) INSERT (X, T -> LEFT); else if (X > T -> ELEMENT) INSERT (X, T -> RIGHT); // ELSE X IS IN THE TREE ALREADY AND DO NOTHING. } // REMOVE AN ELEMENT FROM THE TREE. template void BINARY_SEARCH_TREE :: REMOVE (const ETYPE & X, TREE_NODE * & T) { TREE_NODE * TMP_CELL; if (T == 0) OUTFILE << "ELEMENT NOT FOUND."; else if (X < T -> ELEMENT) // GO LEFT. REMOVE (X, T -> LEFT); else if (X > T -> ELEMENT) // GO RIGHT. REMOVE (X, T -> RIGHT); else // FOUND ELEMENT TO BE REMOVED. if (T -> LEFT != 0 && T -> RIGHT != 0) // TWO CHILDREN. { // REPLACE WITH SMALLEST IN RIGHT SUBTREE. TMP_CELL = FIND_MIN (T -> RIGHT); T -> ELEMENT = TMP_CELL -> ELEMENT; REMOVE (T -> ELEMENT, T -> RIGHT); } else // ONE OR ZERO CHILD. { TMP_CELL = T; if (T -> LEFT == 0) // ONLY A RIGHT CHILD. T = T -> RIGHT; else if (T -> RIGHT == 0) // ONLY A LEFT CHILD. T = T -> LEFT; delete TMP_CELL; } } // PRINT THE TREE USING AN INORDER TRAVERSAL. // THIS WILL PRINT IT IN SORTED ORDER. template void BINARY_SEARCH_TREE :: PRINT_TREE (TREE_NODE * T) const { static int COUNT; if (T != 0) { PRINT_TREE (T -> LEFT); OUTFILE << HEIGHT (T) << " " << T -> ELEMENT << " "; COUNT = COUNT + 1; if (COUNT % 8 == 0) { OUTFILE << "\n"; COUNT = 0; } PRINT_TREE (T -> RIGHT); } } // CALCULATE THE HEIGHT OF A NODE. template int HEIGHT (TREE_NODE * T) { if (T == 0) return -1; else return 1 + MAX (HEIGHT (T -> LEFT), HEIGHT (T -> RIGHT)); } // THIS IS THE DECLARATION FOR A AVL NODE CLASS. template class AVL_NODE : public TREE_NODE { private: // HEIGHT OF THE AVL TREE NODE. int HEIGHT; // CALCULATE THE HEIGHT OF A AVL NODE TREE. friend int NODE_HT (AVL_NODE * P) {return P ? P -> HEIGHT : -1;} friend int NODE_HT (TREE_NODE * P) {return NODE_HT ((AVL_NODE *) (P));} friend void CALCULATE_HEIGHT (AVL_NODE * P) {P -> HEIGHT = 1 + MAX (NODE_HT (P -> LEFT), NODE_HT (P -> RIGHT ));} // SINGLE ROTATE LEFT. friend void S_ROTATE_LEFT (AVL_NODE * & K2); // DOUBLE ROTATE LEFT. friend void D_ROTATE_LEFT (AVL_NODE * & K3); // SINGLE ROTATE RIGHT. friend void S_ROTATE_RIGHT (AVL_NODE * & K1); // DOUBLE ROTATE RIGHT. friend void D_ROTATE_RIGHT (AVL_NODE * & K3); protected: // AVL_TREE WILL USE THIS CLASS. friend class AVL_TREE ; public: // AVL NODE CONSTRUCTOR. AVL_NODE (ETYPE E = 0, AVL_NODE * L = 0, AVL_NODE * R = 0, int H = 0) : TREE_NODE (E, L, R), HEIGHT (H) {} }; // THIS IS THE DECLARATION FOR A AVL SEARCH TREE CLASS. template class AVL_TREE : public BINARY_SEARCH_TREE { // THESE PROCEDURES ARE CALLED BY THE PUBLIC ONES OF THE SAME NAME. protected: // COPY AN AVL TREE. AVL_NODE * COPY (const AVL_NODE * T); // INSERT AN ELEMENT INTO AN AVL TREE. void INSERT (const ETYPE & X, AVL_NODE * & T); // DELETE AN ELEMENT FROM AN AVL TREE. void REMOVE (const ETYPE & X, AVL_NODE * & T); // THESE PROCEDURES WILL CALL THE PROTECTED ONES. public: // CONSTRUCTOR. AVL_TREE () : BINARY_SEARCH_TREE () {} // COPY AVL TREE USING '='. const AVL_TREE & operator = (const AVL_TREE & VALUE); // CALL INSERT. virtual void INSERT (const ETYPE & X) {INSERT (X, (AVL_NODE * &) ROOT);} // CALL REMOVE. virtual void REMOVE (const ETYPE & X) {REMOVE (X, (AVL_NODE * &) ROOT);} }; // THIS IS THE IMPLEMENTATION OF THE AVL SEARCH TREE CLASS. // COPY THE AVL TREE. template AVL_NODE * AVL_TREE :: COPY (const AVL_NODE * T) { if (T != 0) return new AVL_NODE (T -> ELEMENT, COPY ((AVL_NODE * )(T -> LEFT)), COPY ((AVL_NODE *) (T -> RIGHT)), T -> HEIGHT); else return 0; } // INSERT AN ELEMENT INTO THE AVL TREE. CORRECT BALANCE IF NECESSARY. template void AVL_TREE :: INSERT (const ETYPE & X, AVL_NODE * & T) { if (T == 0) // CREATE A ONE NODE TREE. { T = new AVL_NODE (X); if (T == 0) OUTFILE << "OUT OF SPACE."; return; } if (X < T -> ELEMENT) { INSERT (X, (AVL_NODE * &) T -> LEFT); if (NODE_HT (T -> LEFT) - NODE_HT (T -> RIGHT) == 2) if (X < ((AVL_NODE *) T -> LEFT) -> ELEMENT) S_ROTATE_LEFT (T); else D_ROTATE_LEFT (T); else CALCULATE_HEIGHT (T); } else if (X > T -> ELEMENT) { INSERT (X, (AVL_NODE * & ) T -> RIGHT); if (NODE_HT (T -> RIGHT) - NODE_HT (T -> LEFT) == 2) if (X > ((AVL_NODE *) T -> RIGHT) -> ELEMENT) S_ROTATE_RIGHT (T); else D_ROTATE_RIGHT (T); else CALCULATE_HEIGHT (T); } // ELSE X IS IN THE TREE ALREADY, SO WE'LL DO NOTHING. } // REMOVE AN ELEMENT FROM THE AVL TREE. CORRECT BALANCE IF NECESSARY. template void AVL_TREE :: REMOVE (const ETYPE & X, AVL_NODE * & T) { AVL_NODE * TMP_CELL; if (T == 0) OUTFILE << "ELEMENT NOT FOUND."; else if (X < T -> ELEMENT) // GO LEFT. { { REMOVE (X, (AVL_NODE * &)T -> LEFT); } } else if (X > T -> ELEMENT) // GO RIGHT. { { REMOVE (X, (AVL_NODE * &) T -> RIGHT); } } else // FOUND ELEMENT TO BE REMOVED. if (T -> LEFT != 0 && T -> RIGHT != 0) // TWO CHILDREN. { // REPLACE WITH SMALLEST IN RIGHT SUBTREE. TMP_CELL = (AVL_NODE *) FIND_MIN (T -> RIGHT); T -> ELEMENT = TMP_CELL -> ELEMENT; REMOVE (T -> ELEMENT, (AVL_NODE * &) T -> RIGHT); } else // ONE OR ZERO CHILD. { TMP_CELL = T; if (T -> LEFT == 0) // ONLY A RIGHT CHILD. T = (AVL_NODE * &) T -> RIGHT; else if (T -> RIGHT == 0) // ONLY A LEFT CHILD. T = (AVL_NODE * &) T -> LEFT; delete TMP_CELL; } } // THIS FUNCTION CAN BE CALLED ONLY IF K2 HAS A LEFT CHILD. // PERFORM A ROTATE BETWEEN A NODE (K2) AND ITS LEFT CHILD. // UPDATE HEIGHTS. template void S_ROTATE_LEFT (AVL_NODE * & K2) { AVL_NODE * K1 = (AVL_NODE * ) K2 -> LEFT; K2 -> LEFT = K1 -> RIGHT; K1 -> RIGHT = K2; K2 -> HEIGHT = MAX (NODE_HT (K2 -> LEFT), NODE_HT (K2 -> RIGHT)) + 1; K1 -> HEIGHT = MAX (NODE_HT (K1 -> LEFT), K2 -> HEIGHT) + 1; K2 = K1; } // THIS PROCEDURE CAN ONLY BE CALLED IF K3 HAS A LEFT CHILD AND K3'S LEFT // CHILD HAS A RIGHT CHILD. // DO THE LEFT-RIGHT DOUBLE ROTATION. template void D_ROTATE_LEFT (AVL_NODE * & K3) { S_ROTATE_RIGHT ((AVL_NODE * &) K3 -> LEFT); S_ROTATE_LEFT (K3); } // THIS FUNCTION CAN BE CALLED ONLY IF K1 HAS A RIGHT CHILD. // PERFORM A ROTATE BETWEEN A NODE (K1) AND ITS RIGHT CHILD. // UPDATE HEIGHTS. template void S_ROTATE_RIGHT (AVL_NODE * & K1) { AVL_NODE * K2 = (AVL_NODE * ) K1 -> RIGHT; K1 -> RIGHT = K2 -> LEFT; K2 -> LEFT = K1; K1 -> HEIGHT = MAX (NODE_HT (K1 -> RIGHT), NODE_HT (K1 -> LEFT)) + 1; K2 -> HEIGHT = MAX (NODE_HT (K2 -> RIGHT), K1 -> HEIGHT) + 1; K1 = K2; } // THIS PROCEDURE CAN ONLY BE CALLED IF K3 HAS A RIGHT CHILD AND K3'S RIGHT // CHILD HAS A LEFT CHILD. // DO THE RIGHT-LEFT DOUBLE ROTATION. template void D_ROTATE_RIGHT (AVL_NODE * & K3) { S_ROTATE_LEFT ((AVL_NODE * &) K3 -> RIGHT); S_ROTATE_RIGHT (K3); } // RETURN THE MAXIMUM NUMBER OF TWO INTEGERS. USED FOR THE HEIGHT. int MAX (int A, int B) { if (A > B) { return A; } else { return B; } } // THIS PROGRAM WILL INSERT 40 RANDOM INTEGERS FROM 1000 TO 10000 INTO // A AVL TREE AND PRINT THEM IN ASCENDING ORDER. THEN, IT // WILL DELETE 20 ELEMENTS FROM THE TREE, PRINTING THE NEW TREE EVERY // FORTH REMOVAL. int main () { // OPEN OUTFILE. OUTFILE.open ("AVL.OUT", ios :: out); // CLEAR SCREEN. clrscr (); // MAKE EACH EXECUTION DIFFERENT. randomize (); // DECLARE VARIABLE FOR AN AVL TREE OF INTEGERS. // IT WILL HOLD THE 40 RANDOM INTEGERS. AVL_TREE INTEGER_TREE; // HOLDS THE CURRENT RANDOM NUMBER. int RANDOM_NUMBER; // HOLDS THE CURRENT RANDOM NUMBER. NEEDED FOR REMOVAL. int TEMP; // HOLDS THE 40 RANDOM INTEGERS. // THIS WILL BE USED FOR DELETION. int RANDOM_ARRAY [40]; // FLAG = 1, THE INTEGER IS ALREADY IN THE TREE. // FLAG = 0, THE INTEGER IS NOT IN THE TREE. int FLAG; // INSERT 40 RANDOM INTEGERS FROM 1000 TO 10000 INTO THE TREE. for (int I = 0; I <= 39; I++) { // GET RANDOM NUMBER AND MAKE SURE IT IS NOT ALREADY IN // THE TREE. do { FLAG = 0; RANDOM_NUMBER = (rand () % 9000) + 1000; for (int J = 0; J <= I; J++) { if (RANDOM_ARRAY [J] == RANDOM_NUMBER); { FLAG = 1; break; } } } while (FLAG != 1); // INSERT IT INTO THE TREE. INTEGER_TREE.INSERT (RANDOM_NUMBER); // ALSO, INSERT IT INTO AN ARRAY. RANDOM_ARRAY [I] = RANDOM_NUMBER; } // PRINT A HEADING AND THEN THE TREE. OUTFILE << "AFTER 40 INSERTIONS (HEIGHT AND INT):\n"; INTEGER_TREE.PRINT_TREE (); // REMOVE 20 ELEMENTS FROM THE TREE. for (int J = 0; J <= 19; J++) { // LOOP IF THE RANDOM NUMBER IS NOT IN THE ARRAY. // THIS MIGHT HAPPEN IF IT HAS BEEN REMOVED FROM // TREE AND ARRAY. do { // RANDOM NUMBER FROM 0 TO 39. // INDEX OF THE ARRAY. RANDOM_NUMBER = (rand () % 40); } while (RANDOM_ARRAY [RANDOM_NUMBER] == 0); // HOLD THE RANDOM NUMBER. TEMP = RANDOM_ARRAY [RANDOM_NUMBER]; // PUT 0 IN THE ARRAY OF THE APPROPRIATE INDEX. RANDOM_ARRAY [RANDOM_NUMBER] = 0; // PUT THE RANDOM NUMBER IN THE TEMP VARIABLE INTO // THE RANDOM NUMBER VARIABLE. RANDOM_NUMBER = TEMP; // REMOVE THE RANDOM NUMBER. INTEGER_TREE.REMOVE (RANDOM_NUMBER); // WRITE A HEADING AND SHOW THE NEW TREE. if ((J + 1) % 4 == 0) { OUTFILE << "\nAFTER 4 DELETIONS (HEIGHT AND INT):\n"; INTEGER_TREE.PRINT_TREE (); } } // CLOSE OUTFILE. OUTFILE.close (); return 0; } // OUTFILE: AVL.OUT AFTER 40 INSERTIONS (HEIGHT AND INT): 0 1309 1 1316 2 1723 0 2170 1 2479 3 2531 0 2891 1 3092 0 3104 5 3315 1 3570 0 3645 2 3713 0 3790 4 4359 0 4501 2 4984 1 5007 0 5200 3 5257 0 5266 1 5308 0 5344 6 5430 0 5606 1 5975 3 6317 0 6427 2 6523 0 7141 1 7227 4 7759 1 7816 0 8000 3 8224 0 8687 1 9104 0 9337 2 9460 0 9788 AFTER 4 DELETIONS (HEIGHT AND INT): 0 1309 1 1316 2 1723 0 2170 1 2479 3 2531 0 2891 1 3092 0 3104 5 3315 1 3570 0 3645 2 3713 0 3790 4 4359 0 4501 2 4984 1 5007 0 5200 3 5257 1 5308 0 5344 6 5430 0 5606 1 5975 2 6317 1 6523 0 7227 4 7759 1 7816 0 8000 3 8224 0 8687 1 9337 2 9460 0 9788 AFTER 4 DELETIONS (HEIGHT AND INT): 0 1309 1 1316 2 1723 0 2170 1 2479 3 2531 0 2891 1 3092 0 3104 5 3315 1 3570 0 3645 2 3713 4 4359 0 4501 2 4984 1 5007 0 5200 3 5257 1 5308 0 5344 6 5430 0 5606 1 5975 2 6317 0 6523 3 7759 0 7816 2 8224 0 8687 1 9460 0 9788 AFTER 4 DELETIONS (HEIGHT AND INT): 0 1316 2 1723 0 2170 1 2479 3 2531 0 2891 1 3092 5 3315 0 3645 1 3713 4 4359 2 4984 1 5007 0 5200 3 5257 1 5308 0 5344 6 5430 0 5606 1 5975 2 6317 0 6523 3 7759 0 7816 2 8224 0 8687 1 9460 0 9788 AFTER 4 DELETIONS (HEIGHT AND INT): 0 1316 2 1723 0 2170 1 2479 3 2891 0 3092 4 3315 0 3713 3 4359 1 4984 0 5007 2 5257 0 5344 5 5430 0 5606 1 5975 2 6317 0 6523 3 7759 0 7816 2 8224 0 8687 1 9460 0 9788 AFTER 4 DELETIONS (HEIGHT AND INT): 1 1723 0 2479 2 2891 0 3092 3 3315 0 3713 2 4359 0 5007 1 5257 0 5344 4 5430 0 5606 1 5975 2 6317 0 6523 3 7759 0 7816 2 8224 1 9460 0 9788 BACK TO CS3240 PAGE.