Objective you will: 1. Implement a Binary Search Tree (BST) from scratch, including the Big Five (Rule of Five) 2. Implement the TreeSort algorithm using a in-order traversal to store sorted elements in a vector. 3. Compare the performance of TreeSort with C++'s std::sort on large datasets. Part 1: Understanding TreeSort How TreeSort Works TreeSort is a comparison-based sorting algorithm that leverages a Binary Search Tree (BST): 1. Insert all elements into a BST (logically sorting them). 2. Traverse the BST in-order to extract elements in sorted order. 3. Store the sorted elements in a vector. Time Complexity Operation Average Case Worst Case (Unbalanced Tree)Insertion 0(1log n) 0 (n)Traversal (Pre-order) 0(n) 0 (n)Overall Complexity 0(n log n) 0(n^2) (degenerated tree) Note: To improve performance, you could use a Self-Balancing BST (like AVL or Red-Black Tree), but for this assignment, implement a standard unbalanced BST. template <typename T>class BST {private: struct TreeNode { T data; TreeNode* left; TreeNode* right; TreeNode(const T& value) : data(value), left(nullptr), right(nullptr) {} }; TreeNode* root; void insertHelper(TreeNode*& node, const T& value); void preOrderTraversalHelper(TreeNode* node, std::vector<T>& sortedVector); void destroyTree(TreeNode* node); TreeNode* copyTree(TreeNode* other); public: // Constructor BST(); // Destructor ~BST(); // Copy Constructor BST(const BST& other); // Copy Assignment BST& operator=(const BST& other); // Move Constructor BST(BST&& other) noexcept; // Move Assignment BST& operator=(BST&& other) noexcept; // Public methods void insert(const T& value); std::vector<T> inOrderTraversal();}; Implement TreeSort using the BST Steps to Implement TreeSort: Insert all elements from an unsorted vector into the BST. Extract elements using in-order traversal and store them in another vector. Return the sorted vector. TreeSort Function: template <typename T>std::vector<T> treeSort(std::vector<T>& arr) { BST<T> tree; // Insert elements into the BST for (const T& val : arr) { tree.insert(val); } // Return the in-order traversal of the BST return tree.inOrderTraversal(); 3. Compare Performance with std::sort Use the C++ library to compare execution time Generate large random datasets (10,000+ elements) Measure sorting time for both methods using Example Benchmarking Code: int main() { const int SIZE = 10000; std::vector<int> data(SIZE); // Fill with random values for (int& val : data) { val = rand() % 10000; } // Measure TreeSort time auto treeData = data; auto start = std::chrono::high_resolution_clock::now(); std::vector<int> treeSorted = treeSort(treeData); auto end = std::chrono::high_resolution_clock::now(); std::cout << "TreeSort Time: " << std::chrono::duration<double, std::milli>(end - start).count() << " ms\n"; // Measure std::sort time auto stdData = data; start = std::chrono::high_resolution_clock::now(); std::sort(stdData.begin(), stdData.end()); end = std::chrono::high_resolution_clock::now(); std::cout << "std::sort Time: " << std::chrono::duration<double, std::milli>(end - start).count() << " ms\n"; return 0;} Submission Requirements Submit a C++ project (.cpp and .h files) implementing: BST Class (with Big Five) TreeSort Algorithm Performance Comparison Include a README.md with: Explanation of TreeSort and how it was implemented Benchmark results comparing TreeSort vs. std::sort Code should be well-documented and use good object-oriented principles.
Objective you will:
1. Implement a Binary Search Tree (BST) from scratch, including the Big Five (Rule of Five)
2. Implement the TreeSort algorithm using a in-order traversal to store sorted elements in a vector.
3. Compare the performance of TreeSort with C++'s std::sort on large datasets.
Part 1: Understanding TreeSort How TreeSort Works TreeSort is a comparison-based sorting algorithm that leverages a Binary Search Tree (BST):
1. Insert all elements into a BST (logically sorting them).
2. Traverse the BST in-order to extract elements in sorted order.
3. Store the sorted elements in a vector.
Time Complexity
Operation Average Case Worst Case (Unbalanced Tree)
Insertion 0(1log n) 0 (n)
Traversal (Pre-order) 0(n) 0 (n)
Overall Complexity 0(n log n) 0(n^2) (degenerated tree)
Note: To improve performance, you could use a Self-Balancing BST (like AVL or Red-Black Tree), but for this assignment, implement a standard unbalanced BST.
template <typename T>
class BST {
private:
struct TreeNode {
T data;
TreeNode* left;
TreeNode* right;
TreeNode(const T& value) : data(value), left(nullptr), right(nullptr) {}
};
TreeNode* root;
void insertHelper(TreeNode*& node, const T& value);
void preOrderTraversalHelper(TreeNode* node, std::vector<T>& sortedVector);
void destroyTree(TreeNode* node);
TreeNode* copyTree(TreeNode* other);
public:
// Constructor
BST();
// Destructor
~BST();
// Copy Constructor
BST(const BST& other);
// Copy Assignment
BST& operator=(const BST& other);
// Move Constructor
BST(BST&& other) noexcept;
// Move Assignment
BST& operator=(BST&& other) noexcept;
// Public methods
void insert(const T& value);
std::vector<T> inOrderTraversal();
};
Implement TreeSort using the BST Steps to Implement TreeSort:
- Insert all elements from an unsorted vector into the BST.
- Extract elements using in-order traversal and store them in another vector.
- Return the sorted vector.
TreeSort Function:
template <typename T>
std::vector<T> treeSort(std::vector<T>& arr) {
BST<T> tree;
// Insert elements into the BST
for (const T& val : arr) {
tree.insert(val);
}
// Return the in-order traversal of the BST
return tree.inOrderTraversal();
3. Compare Performance with std::sort
Use the C++ library to compare execution time
- Generate large random datasets (10,000+ elements)
- Measure sorting time for both methods using
Example Benchmarking Code:
int main() {
const int SIZE = 10000;
std::vector<int> data(SIZE);
// Fill with random values
for (int& val : data) {
val = rand() % 10000;
}
// Measure TreeSort time
auto treeData = data;
auto start = std::chrono::high_resolution_clock::now();
std::vector<int> treeSorted = treeSort(treeData);
auto end = std::chrono::high_resolution_clock::now();
std::cout << "TreeSort Time: "
<< std::chrono::duration<double, std::milli>(end - start).count()
<< " ms\n";
// Measure std::sort time
auto stdData = data;
start = std::chrono::high_resolution_clock::now();
std::sort(stdData.begin(), stdData.end());
end = std::chrono::high_resolution_clock::now();
std::cout << "std::sort Time: "
<< std::chrono::duration<double, std::milli>(end - start).count()
<< " ms\n";
return 0;
}
Submission Requirements
- Submit a C++ project (.cpp and .h files) implementing:
- BST Class (with Big Five)
- TreeSort Algorithm
- Performance Comparison
- Include a README.md with:
- Explanation of TreeSort and how it was implemented
- Benchmark results comparing TreeSort vs. std::sort
- Code should be well-documented and use good object-oriented principles.
Step by step
Solved in 2 steps
