Homework

Implement a(n) (unbalanced) binary search tree nonstd::MultiSet class which behaves similarly to std::multiset (Links to an external site.)Links to an external site.. Note that you will not have to implement iterators, which is why insert is void.

Any members or methods in the private sections can be modified however you like, as long as it's still in the spirit of the assignment. For example, you may use regular pointers instead of std::unique_ptr but don't use an std::multiset as part of your implementation.

Note that in a more realistic implementation, you might not have getters and setters for the MultiSet::Node's left and right children but I have them in this assignment so I can more easily grade your code without needing to care whether you use regular pointers or something else.

multiset.h

#pragma once #include  namespace nonstd { template  class MultiSet { public: class Node { private: T value_; std::unique_ptr left_, right_; Node(const T& value) : value_(value) {} public: Node *left() { // TODO } Node *right() { // TODO } const T& value() const { // } friend class MultiSet; }; private: std::unique_ptr root_; int size_; public: MultiSet() { // TODO } ~MultiSet() { // TODO } void insert(const T& value) { // TODO } int count(const T& value) { // TODO } bool contains(const T& value) { // TODO } int size() { // TODO } Node *root() { // TODO } }; } // namespace nonstd 

all in C++, and only these methods are allowed