subject

In this assignment you will implement AVL trees. You are responsible for implementing insertion and deletion, so you are also responsible for rotating subtrees to maintain the balance property, find the minimum, and a few additional auxiliary methods. In assignment3.zip, we are providing you with the following code: avl. cpp -> your AVL implementation, mostly dummy text avl. hpp -> header file, you do not have to change it avl. cpp already has a couple methods implemented that you should not change: • a method to print trees, and . a main method that reads test cases (sequences of operations) and executes them A sample README file is also provided. You may find how to compile and test the code. We will test your implementation with test cases that spell out operations (insert a number, delete a number, and print) to be executed on an (initially) empty AVL tree. For example, insert 100 insert 30 insert 20 insert 50 print delete 30 print insert 990 insert 900 print means that you should insert 100, 30, 20, 50 and print the resulting AVL tree. Then you should delete 30 and print the resulting AVL tree. Finally, you need to insert 990 and 900 and print the resulting AVL tree. The expected outcome is the following: 30 11 20 Ir 100 | |1 50 50 11 20 Ir 100 50 11 20 Ir 900 1 100 | Ir 990 where the last tree has root 50 and two children: 20 and 900, and node 900 has two children: 100 and 990. Also, 50 is the left child of 100 in the first tree. A few more notes: • We will publish more complex test cases three days prior to the submission deadline. I recommend you run the examples we saw in class by yourself. • Your insertion and deletion must run in O(log(n)), and you must update the height of nodes after each operation. Opportunity for extra credits (up to 25 points): Write a program that checks whether a binary search tree is an AVL. The input is an arbitrary binary search tree, and the output is binary, so, either true of false. #include #include #include "avl. hpp" using namespace std; #define IS_ROOT O #define IS_LEFT 1 #define IS_RIGHT 2 O ** * * Internal method to insert into a subtree. x is the item to insert. * t is the node that roots the subtree. * Set the new root of the subtree. */ void insert( const int & info, AvlNode * & root ) { std::cout << "As of now, I am implementing a dummy insert" «< endl; std::cout << "Code for inserting " « info «< goes here" << endl; 11 == if (root NULL) root = new AvlNode (info, NULL, NULL); else if (info % 2 == 0){ // for now, even numbers to the left ... [CHANGE THIS] insert( info, root->left ); • } else { // and off numbers to the right [CHANGE THIS] insert( info, root->right ); } Internal method to remove from a subtree. * info is the item to remove. * root is the node that roots the subtree. Set the new root of the subtree. */ Ovoid remove( const int & info, AvlNode * & root ) { std::cout << "Code for deleting " «< info << " goes here" << endl; 1/* * You will probably neesd auxiliary mathods to find the minimum of tree rotate (single and double, in both directions balance am AVL tree * == == /* * Print methods, do not change */ void print (AvlNode *root, int level, int type) { if (root NULL) { return; } if (type IS_ROOT) { std::cout << root -> element << "\n"; } else { for (int i 1; i < level; i++) { std::cout << "|"; } if (type IS_LEFT) { std::cout << "|1_" «< root -> element << "\n"; } else { std::cout << "Ir_" «< root -> element << "\n"; } 40- == if (root -> left != NULL) { print(root -> left, level + 1, IS_LEFT); } if (root -> right != NULL) { print(root -> right, level + 1, IS_RIGHT); } } void print (AvlNode *root) { print(root, 0, IS_ROOT); } * END Print methods, do not change * Main method, do not change == int main(int argc, const char * argv[]) { AvlNode *root = NULL; std::string filename argv[1]; freopen(filename. c_str(), ",", stdin); std::string input; int data; while(std::cin >> input){ if (input "insert"){ std::cin>>data; insert(data, root); } else if(input == "delete"){ std::cin>>data; remove(data, root); } else if(input "print"){ print (root); std::cout << "\n"; } else{ std::cout<<"Data not consistent in file"; break; == Estruct AvlNode { int element; AvINode *left; AvlNode *right; int height; AvlNode (const int & ele, AvlNode *lt, Av Node *rt, int h = 0) { element ele; left lt; right = rt;

ansver
Answers: 3

Other questions on the subject: Computers and Technology

image
Computers and Technology, 22.06.2019 18:30, emojigirl2824
Word vocabulary words: print, proofread, status line, graphics, font effects, left margin, justification, line spacing, copy/paste, data. review words: font point, bold, save, center, error. fill in the correct word for the definition and then transfer the letters to the appropriate spot by number. some numbers will be found multiple times. you will end up with a quotation about…… what else? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 k 16 17 18 19 20 21 22 23 24 25 8 27 28 29 w 31 32 k 34 35 36 w h 39 40 41 42 8 44 45 46 47 48 49 50 51 52 53 54 55 .1. a software function that records keystrokes on a disk or drive so information can be 5 4 52 9 later retrieved. p n 2. to produce a paper copy of information. 10 7 12u n 3. a display that shows the location of the cursor, pages, etc. 45 46 18 27 36 20 42p4. pictures or images, located in clip art or other files. 6 24 44 28 34 49 555. any mis-stroke of a key. 47 41 48 2 10 n6. allows major changes to the font such as shadow, emboss, etc. 21 25 46 35 23 21 29 14 22 17 n7. a feature that centers lines of text horizontally. 49 53 46 9 51 p8. size of the font 31 16 22 b l 9. a feature that prints designated text darker than the rest to add emphasis. 32 3 . p10. to compare copy on a display screen or printout to the original 24 39 25 23 54 9 50 3 and correct errors. j un 11. a feature that allows text to be aligned at the left 11 12 7 21 16 49 40 46 34 2 and right margins. leftn 12. amount of blank space on the left side of the paper. 8 18 41 6 34 linen 13. number of blank lines between lines of text. 17 4 49 13 1914. any information inputted into the computer. 3 4 46 44 p /p15. feature that duplicates text from one location and places it in another.
Answers: 2
image
Computers and Technology, 23.06.2019 18:00, sophx
Apunishment or the threat of punishment used to enforce conformity. select the best answer from the choices provided t f
Answers: 1
image
Computers and Technology, 24.06.2019 14:30, ari313
Two students are discussing the flow of electricity. student a says that voltage is a measure of the amount of electron flow in a circuit. student b says that power is the product of voltage and current. which of the following statements is correct? a. only student a is correct b. only student b is correct c. both of the two students are correct d. neither of the two students is correct
Answers: 1
image
Computers and Technology, 24.06.2019 20:00, broach605
Individuals suffering from technology overload feel distressed when deprived of computers and mobile devices. true/fasle
Answers: 2
You know the right answer?
In this assignment you will implement AVL trees. You are responsible for implementing insertion and...

Questions in other subjects: