3
\$\begingroup\$

Here is my Set implementation with binary search tree that compiles. Please let me know what changes are needed to make it better. Thank you.

#include <vector>

using namespace std;

template <class T> class Set;
template <class T> class Node_Iterator;

template<class T>
struct Node_Set
{
    Node_Set(const T& data)
    {
        _value = data;
        _left = NULL;
        _right = NULL;
        _friend = NULL;
    }

    ~Node_Set()
    {
        delete _left;
        delete _right;
    }

    T _value;
    Node_Set *_left;
    Node_Set *_right;
    Node_Set *_friend; // in-order traversal
};

template<class T>
class Set
{
    public : 
    Set()
    {
        _size = 0;
        _root = NULL;
    }

    ~Set()
    {
        clear();
    }

    typedef typename Node_Iterator<T> iterator;

    Set(const Set &s)
    {
        _size = 0;
        _root = NULL;
        for(iterator it = s.begin(); it != s.end(); it++)
        {
            insert(*it);
        }
    }

    Set& operator =(const Set &s)
    {
        if(&s == this) return *this;

        clear();
        for(iterator it = s.begin(); it != s.end(); it++)
        {
            insert(*it);
        }
        return *this;
    }


    void clear()
    {
        if(_root)
        {
            delete _root;
            _root = NULL;
            _size = 0;
        }
    }

    size_t size() const
    {
        return _size;
    }

    bool empty() const
    {
        return _size == 0;
    }

    mutable size_t _size;
    mutable Node_Set<T> *_root;
    mutable Node_Set<T> *startIterator;

    T& insert(const T& t)
    {
        return insert_imp(t, _root, _size);
    }

    bool find(const T& t, T*& result)
    {
        return (find_imp(t, result, _root) != NULL);
    }

    bool remove(const T& t)
    {
        T *result;
        Node_Set<T> **nodeRemove = find_imp(t, result, _root);

        if(nodeRemove == NULL) {
            return false;
        }

        _size--;
        remove_imp(*nodeRemove);
        return true;
    }

    iterator begin() const
    {
        build_iterators(_root);
        return iterator(startIterator);
    }

     iterator end() const { 
         return iterator(0); 
     }

    private : 
    void build_iterators(const Node_Set<T> *root) const
    {
        size_t i;
        std::vector<Node_Set<T>*> iterators;
        build_iterators_imp(iterators, root);

        if(empty()) 
        {
            startIterator = NULL;
            return;
        }

        startIterator = iterators[0];   
        for(i = 0; i < iterators.size() - 1; i++)
        {
            iterators[i]->_friend = iterators[i + 1];
        }
        iterators[i]->_friend = NULL;
    }

    static void build_iterators_imp(std::vector<Node_Set<T>*> &iterators, const Node_Set<T> *root)
    {
        if(root == NULL) {
            return;
        }

       build_iterators_imp(iterators, root->_left);

       iterators.push_back((Node_Set<T>*)root);

       build_iterators_imp(iterators, root->_right);
    }

    static T& insert_imp(const T& t, Node_Set<T> *&root, size_t &_size)
    {
        if(!root)
        {
            _size++;
            root = new Node_Set<T>(t);
            return root->_value;
        }

        if(t == root->_value)
        {
            return root->_value;
        }
        else if(t < root->_value)
        {
            return insert_imp(t, root->_left, _size);
        }
        else
        {
            return insert_imp(t, root->_right, _size);      
        }       
    }

    static Node_Set<T>** find_imp(const T& t, T*& result, Node_Set<T> *&root)
    {
        if(!root)
        {
            result = NULL;
            return NULL;
        }

        if(t == root->_value)
        {
            result = &root->_value; 
            return &root;
        }
        else if(t < root->_value)
        {
            return find_imp(t, result, root->_left);
        }
        else
        {
            return find_imp(t, result, root->_right);       
        }       
    }

    static void travel_rightmost(Node_Set<T> *&_this, Node_Set<T> **&nodeResult)
    {
        if(!_this) return;
        if(_this->_right) {
            nodeResult = &_this;
            return travel_rightmost(_this->_right, nodeResult);
        }
    }

    static void travel_leftmost(Node_Set<T> *&_this, Node_Set<T> **&nodeResult)
    {
        if(!_this) return;      
        if(_this->_left) {
            nodeResult = &_this;
            return travel_leftmost(_this->_left, nodeResult);   
        }
    }

    static void remove_imp(Node_Set<T> *&root)
    {
        if(root == NULL) {
            return;
        }

        if(root->_left == NULL && root->_right == NULL)
        {
            delete root;
            root = NULL;
            return;
        }

        if(root->_left != NULL && root->_right == NULL)
        {
            Node_Set<T> *leftNode = root->_left;
            root->_left = NULL;
            delete root;
            root = leftNode;
            return;
        }

        if(root->_left == NULL && root->_right != NULL)
        {
            Node_Set<T> *rightNode = root->_right;
            root->_right = NULL;
            delete root;
            root = rightNode;
            return;
        }

        if(root->_left != NULL && root->_right != NULL)
        {
            Node_Set<T> **nodeLeftMost = NULL;
            Node_Set<T> **nodeRightMost = NULL;
            Node_Set<T> *leftChild = root->_left;
            Node_Set<T> *rightChild = root->_right;

            travel_leftmost(root->_right, nodeRightMost);

            if(nodeRightMost != NULL && (*nodeRightMost)->_left == NULL && (*nodeRightMost)->_right == NULL)
            {
                root->_value = (*nodeRightMost)->_value;
                delete *nodeRightMost;
                *nodeRightMost = NULL;

                return;
            }

            travel_rightmost(root->_left, nodeLeftMost);

            if(nodeLeftMost != NULL && (*nodeLeftMost)->_left == NULL && (*nodeLeftMost)->_right == NULL)
            {
                root->_value = (*nodeLeftMost)->_value;
                delete *nodeLeftMost;
                *nodeLeftMost = NULL;

                return;
            }
            else if(leftChild->_right == NULL)
            {
                root->_left = NULL;
                root->_right = NULL;
                delete root;
                root = leftChild;
                root->_right = rightChild;
            }
            else if(rightChild->_left == NULL)
            {
                root->_left = NULL;
                root->_right = NULL;
                delete root;
                root = rightChild;
                root->_left = leftChild;
            }
        }
    }   
};

template <class T>
class Node_Iterator 
{
   Node_Set<T> * n;
public:
   Node_Iterator() : n(0) {}
   Node_Iterator(Node_Set<T> * newNode) : n(newNode) { }

   bool operator == (Node_Iterator it) const { return n == it.n; }
   bool operator != (Node_Iterator it) const { return n != it.n; }

   // In-order traversal
   Node_Iterator & operator++(); 
   Node_Iterator operator++(int); 

   T & operator*() { return n->_value; }
   T * operator->() { return &n->_value; }
   Node_Iterator & operator=(Node_Iterator<T> it) { n = it.n; return *this; }

  friend class Set<T>;
};

template <class T>
Node_Iterator<T>& Node_Iterator<T>::operator ++()
{
   n = n->_friend;
   return *this;
}

template <class T>
Node_Iterator<T> Node_Iterator<T>::operator ++(int)
{
   Node_Iterator<T> it(*this); ++(*this);

   return it;
}

And here is the code that is used to test the Set class :

#include <iostream>
#include "set.h"

using namespace std;

int main()
{
    Set<int> set;
    set.insert(4); set.insert(0);
    set.insert(2); set.insert(7);
    set.insert(0); set.insert(2);
    set.insert(6); set.insert(4);
    set.insert(12); set.insert(11);
    set.insert(8); set.insert(1); 
    set.insert(5); set.insert(0);
    set.insert(3); set.insert(2);
    set.insert(7); set.insert(1);
    set.insert(1); set.insert(1);
    set.insert(9); set.insert(7);
    set.insert(11); set.insert(1);

    Set<int> set2 = set;

    for(Set<int>::iterator it = set2.begin(); it != set2.end(); it++)
    {
        cout << *it << ' ';
    }
}
\$\endgroup\$
3
\$\begingroup\$

Here are some things that may help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. It's especially bad to put into a header file as in the current code.

Use your own namespace

Combined with the problem above, your use of the name Set is not good. It is very similar to std::set and is also not very descriptive of the data structure. Since it's a tree, maybe name it Tree?

Don't use leading underscores in names

Anything with a leading underscore is a reserved name in C++ (and in C). See this question for details.

Prefer using to typedef in templates

The current code includes this line

typedef typename Node_Iterator<T> iterator;

However this doesn't compile on my machine (and shouldn't compile on yours) because a typedef can't be a template. Instead, we have using which was introduced for that purpose:

using iterator = Node_Iterator<T>;

Separate interface from implementation

It makes the code somewhat longer for a code review, but it's often very useful to separate the interface from the implementation. In C++, this is usually done by putting the interface into separate .h files and the corresponding implementation into .cpp files, but things are a bit different for header-only templates such as this one. However, I'd still recommend having an interface section and an implementation section to better aid users (or reviewers) of the code see and understand the interface.

Use nullptr rather than NULL

Modern C++ uses nullptr rather than NULL. See this answer for why and how it's useful.

Prefer modern initializers for constructors

The constructor use the more modern initializer style rather than the old style you're currently using. Instead of this:

Set()
{
    _size = 0;
    _root = NULL;
}

You could use this:

Set() :
    _size{0}, _root{nullptr}, startIterator{nullptr}
{}

Don't abuse mutable

The purpose for the mutable keyword is to mark things that can change but are not visible to the outside interface. For examle, it might be reasonble to declare your startIterator as mutable but it certatinly is not reasonable to declare _size and _root mutable!

Don't expose class internals

The insert() member function returns a reference to the data just inserted. This is not a good idea, because it then allows for internal data to be altered outside the class. Consider:

Set<int> set;
int &foo = set.insert(0);
set.insert(1);
set.insert(2);
foo = 99;

Now the tree contains 1, 2 and 99.

Simplify node deletion

The code for remove_imp is much more complex than it needs to be.

static void remove_imp(Node_Set<T> *&root)
{
    if(root == nullptr) {
        return;
    }

    if(root->_left == nullptr) {
        if (root->_right == nullptr) {
            delete root;
            root = nullptr;
        } else {
            Node_Set<T> *rightNode = root->_right;
            root->_right = nullptr;
            delete root;
            root = rightNode;
        }
    } else {
        if (root->_right == nullptr) {
            Node_Set<T> *leftNode = root->_left;
            root->_left = nullptr;
            delete root;
            root = leftNode;
        } else {
            Node_Set<T> **left = &root->_right;
            while ((*left)->_left) {
                left = &(*left)->_left;
            }
            root->_value = (*left)->_value;
            remove_imp(*left);
        }
    }
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy