CMPSC 122 section 2 Homework 6 Due: Saturday, May 9 2020 Binary Search Tree & Day-Stout-Warren (DSW) Algorithm lookup, addition and removal of items. The time complexity of searching an item in a BST...

C++


CMPSC 122 section 2 Homework 6 Due: Saturday, May 9 2020 Binary Search Tree & Day-Stout-Warren (DSW) Algorithm lookup, addition and removal of items. The time complexity of searching an item in a BST is ?(ℎ) where ℎ is the height of the tree, Binary search tree (BST) is a data structure that stores items (such as numbers and names) in a specific way in memory. It allows fast and therefore keeping the height value ℎ small is important. The Day-Stout-Warren (DSW) algorithm is an algorithm that decreases the height of a binary search tree to as ?(log?), where ? is the total number of nodes, by restructuring BST using left- and right-right rotations. DSW algorithm is composed of two steps: 1. Converting a BST to a backbone that has a form of linear chain using a series of right rotations, and 2. Converting the backbone to an almost complete binary tree (ACBT) using a series of left rotations. Assignment The goal of this assignment is to implement BST and DSW algorithm. To this end, you should implement the following functions: 1. void BST::Insert(double value); // insert value into BST 2. Node* BST::Search(double query); // return the node whose value is query, or // NULL if such a node is not exists in BST 3. void BST::Inorder(void (*visit)(const Node*)); // inorder traversal 4. void BST::Preorder(void (*visit)(const Node*)); // preorder traversal 5. void BST::Postorder(void (*visit)(const Node*));// postorder traversal 6. void BST::TreeToBackbone(); // DST step 1: converting BST to backbone 7. void BST::BackboneToACBT(); // DST step 2: converting backbone to ACBT The details of prototypes of the BST class and the BST test functions are provided in the following startup files: bst.h bst.cpp bsttest.cpp In this assignment, you can add your own member functions of BST class into bst.h file, and you should implement the above functions and your own functions into bst.cpp. The left- and right-rotation functions are provided in bst.h file that receive the pointer of grand parent’s left (or right) child: void BST∷RotateLeft(Node** grandparent_child) and void BST∷RotateRight(Node** grandparent_child). You can find the main function in bsttest.cpp that runs several test cases. Compile and run the program using the following commands: $ g++ -ansi -pedantic -Wall bst.cpp bsttest.cpp -o bsttest $ ./bsttest The program performs the following tests: Test 1: building a BST; Test 2: searching elements in the BST; Test 3: preorder traversals of the BST; Test 4: postorder traversals of the BST; Test 5: inorder traversals of the BST; Test 6: running DST algorithm. (10 points, 10 test cases) (16 points, 8 test cases) (10 points, 1 test case) (10 points, 1 test case) (10 points, 1 test case) (35 points, 7 test cases) 1 Each test case of test 6 is composed of three steps: building a BST (1 point), converting the BST to a backbone (2 points), and converting the backbone to ACBT (2 points). You will receive 91 points from the 6 tests. You will receive 9 points from dynamic memory allocation and your coding style such as creating and deleting Node objects, indentation, variable names, and comments. What to submit • Electronic submission (Due: 11:59:59 PM, Saturday, May 9 2020) via Canvas drop box • Note: If your program does not compile, you will get automatic zero as stated in the syllabus.