1
\$\begingroup\$

Im implementing a BST using templates and dynamic memory, here is my attempt:

This is the BSTNode.hh

#ifndef BSTNODE_HH
#define BSTNODE_HH

#include <list>
#include <algorithm>
using namespace std;

template <class K, class V>
class BSTNode
{
public:
    BSTNode(const K &key) {
        this->key = key;
        this->values = {};
    }

    BSTNode(const K &key, const list<V>& values) {
        this->key = key;
        this->values = values;
    }

    BSTNode(const BSTNode<K, V> &orig) 
    {
        this->key = orig.key;
        this->values = orig.values;
        if (orig.left != nullptr)
        {
            this->left = new BSTNode<K, V>(*orig.left);
            //this->left->setValues()
            left->setParent(this); // Goes back to the new child to set the parent as this
        }

        if (orig.right != nullptr)
        {
            this->right = new BSTNode<K, V>(*orig.right);
            right->setParent(this); // Goes back to the new child to set the parent as this
        }
    };

    virtual ~BSTNode() { }

    /* Modificadors */
    // Declareu-hi aquí els modificadors (setters) dels atributs que manquen
    /* Consultors */
    void setParent(BSTNode<K, V> *parent) { this->parent = parent; }
    void setRight(BSTNode<K,V> *right){this->right = right;}
    void setLeft(BSTNode<K,V>*left){this->left= left;}
    void setValues(const list<V>& v) {this->values = v;}
    
    // Declareu-hi aquí els consultors (getters) dels atributs que manquen
    const K &getKey() const { return key; }
    const list<V> &getValues() const { return this->values; }
    BSTNode<K, V>* getLeft() const {return this->left;}
    BSTNode<K, V>* getRight() const {return this->right;}
    BSTNode<K, V>* getParent() const {return this->parent;}

    /* Operacions */
    bool isRoot() const { return this->parent == nullptr; }
    bool hasLeft() const { return left != nullptr; }
    bool hasRight() const { return right != nullptr; }
    bool isExternal() const { return !hasLeft() and !hasRight(); }
    void insertValue(const V &v) { values.push_back(v); }
    int depth() const
    {
        if (this->isRoot())
            return 0;
        else
            return 1 + parent->depth();
    }

    int height() const
    {
        if (isExternal())
            return 1;
        else
            return 1 + max(left->height(), right->height());
    }
    
    bool operator==(const BSTNode<K, V> &node) const
    {
        if (key != node.key)
            return false;
        auto it1 = values.begin();
        auto it2 = node.values.begin();

        for (; it1 != values.end() && it2 != node.values.end(); it1++, it2++)
        {
            if (*it1 != *it2)
                return false;
        }

        return it1 == values.end() && it2 == node.values.end();
    }

private:
    K key;
    list<V> values;
    // Afegiu-hi aquí els atributs que manquen
    BSTNode<K, V> *left{nullptr};
    BSTNode<K, V> *right{nullptr};
    BSTNode<K, V> *parent{nullptr};
};

#endif

BSTArbre.hh

#ifndef BSTARBRE_HH
#define BSTARBRE_HH

#include "BSTNode.hh"
#include <iostream>
#include <exception>
using namespace std;

template <class K, class V>
class BSTArbre
{
public:
    BSTArbre() : root(nullptr), _size(0){};
    BSTArbre(const BSTArbre<K, V> &orig)
    {
        this->_size = orig._size;
        // TODO: revisar que este bien
        this->root = new BSTNode<K, V>(orig.root);
    };

    BSTArbre(const BSTNode<K, V>& r)
    {
        // TODO: revisar que este bien
        this->_size = 0;
        this->root = new BSTNode<K, V>(r);
    };

    virtual ~BSTArbre()
    {
        destroyRec(root);
    };

    void destroyRec(BSTNode<K, V> *n)
    {
        if (n != nullptr)
        {
            destroyRec(n->getLeft());
            destroyRec(n->getRight());
            delete n;
        }
    }

    bool empty() const { return root == nullptr; }
    int size() const { return _size; };
    int height() const
    {
        if (empty())
            return 0;
        return root->height();
    };

    BSTNode<K, V> *insert(const K &k, const V &value) {
        return _insert(this->root, nullptr, k, value, false); 
        // el padre de root es nullptr
    }

    BSTNode<K,V>* _insert(BSTNode<K, V> *r, BSTNode<K, V> *parent,
                    const K &k, const V &value, bool left) {
        if (r == nullptr) {
            r = new BSTNode<K, V>(k);
            r->insertValue(value);
            r->setParent(parent);
            if (!left and parent != nullptr) {
                parent->setRight(r);
            }
            else if (left and parent != nullptr) parent->setLeft(r);
            return r;
        }
        else {
            if (k > r->getKey()) {
                return _insert(r->getRight(), r, k, value, false);
            }
            else return _insert(r->getLeft(), r, k, value, true);
        }
    }

        

    const list<V> &valuesOf(const K &k) const
    {
        BSTNode<K, V> *n = search(k);
        if (n == nullptr)
            throw invalid_argument("Key not found!");
        else
            return n->getValues();
    }

    void printValues(const list<V> &values) const
    {

        for (auto it = values.begin(); it != values.end(); it++)
        {
            cout << *it << " ";
        }
        cout << endl;
    }

    void printPreorder(const BSTNode<K, V> *n = nullptr) const
    {
        if (n != nullptr)
        {
            cout << n->getKey() << endl;
            printValues(n->getValues());
            printPreorder(n->getLeft());
            printPreorder(n->getRight());
        }
    }

    void printInorder(const BSTNode<K, V> *n = nullptr) const
    {
        if (n != nullptr)
        {
            printInorder(n->getLeft());
            cout << n->getKey() << endl;
            printValues(n->getValues());
            printInorder(n->getRight());
        }
    }
    void printPostorder(const BSTNode<K, V> *n = nullptr) const
    {

        if (n != nullptr)
        {
            printPostorder(n->getLeft());
            printPostorder(n->getRight());
            cout << n->getKey() << endl;
            printValues(n->getValues());
        }
    }

    BSTNode<K, V>* getRoot() {
        return this->root;
    }


    const list<BSTNode<K, V> *> &getLeafNodes() const;

    void printSecondLargestKey() const {
        if (empty())
            throw invalid_argument("Empty tree!");
        else
            printSecondLargestKey(root);
    };

    void printSecondLargestKey(BSTNode<K, V>* root) {
        if (root->getRight() == nullptr) {
            cout << root->getKey() << endl;
        }
        else {
            printSecondLargestKey(root->getRight());
        }
    }

    void mirrorTree() {
        if (empty())
            throw invalid_argument("Empty tree!");
        else
            mirrorTree(root);
    };

    void mirrorTree(BSTNode<K, V>* root) {
        if (root->getLeft() != nullptr) {
            mirrorTree(root->getLeft());
        }
        if (root->getRight() != nullptr) {
            mirrorTree(root->getRight());
        }
        BSTNode<K, V>* temp = root->getLeft();
        root->setLeft(root->getRight());
        root->setRight(temp);
    }

protected:
    BSTNode<K, V> *root;
    BSTNode<K, V> *search(const K &k) const
    {
        BSTNode<K, V> *act = root;
        while (act != nullptr)
        {
            if (act->getKey() < k)
            {
                act = act->getLeft();
            }
            else if (act->getKey() > k)
            {
                act = act->getRight();
            }
            else
                return act;
        }
        return nullptr;
    }

private:
    int _size;
    /* Mètodes auxiliars definiu aquí els que necessiteu */
};

#endif
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

Stick with a single language

I see you have some Catalan comments, and instead of BSTTree you write BSTArbre, but all other types, variables and member functions are named in English. I recommend you be consistent and write everything in English then; it's already required for someone to understand most of your code, and this way people who don't read Catalan can read your code without issues.

Don't make the destructors virtual

I see you made the destructors virtual. That is only necessary if you are writing a base class, however it doesn't look like your classes are meant to be inherited from, so remove the virtual keyword. Or in the case of BSTNode, remove the destructor entirely, since it's empty anyway.

You could make BSTNode part of BSTArbre

You can nest classes in C++. This allows you to write:

class BSTArbre {
    public:
    class Node {
        ...
    };
    ...
    BSTArbre(const BSTArbre &orig)
    {
        _size = orig._size;
        root = new Node(orig.root);
    };
    ...
protected:
    Node *root;
    ...
};

Note how you no longer need to append <K, V> to the node type, as the inner class is part of the template as well. Note that you can also write BSTArbre without <K, V> inside the template, you don't have to repeat the template parameters for types that are within the template.

Unnecessary use of this->

It is almost never necessary to use this-> in C++. I would remove it everywhere. The exceptions might be functions like setParent(), but you could avoid it even there by renaming the function parameter in some way.

Prefer '\n' over std::endl

Prefer using '\n' instead of std::endl; the latter is equivalent to the former, but also forces the output to be flushed, which is usually not necessary and might impact performance.

Make helper function private

There are several helper functions, like destroyRec() and _insert() that should only be called by other member functions of BSTArbre. Make them private, so they cannot be accidentily called. Keep the public API tidy. If you don't, you risk other code starting to call the helper functions, and that means it will be much harder to change your class later without breaking users.

Handle corner cases where possible

Why throw an exception when trying to mirror an empty tree? It seems natural that the result of mirroring an empty tree is just another empty tree, so I would return without any error instead.

size() always returns zero

You are never updating _size, so size() will always return zero. Either make sure you properly update _size whenever nodes get added or removed, or remove the member variable _size and let size() calculate it every time it is called.

Consider adding iterators

Your class has functions to print the contents to std::cout in pre/in/post-order. But what if I want to print to a file? What if I want to do something else with the values I've stored in the tree? Instead of adding more and more member functions, it would be much nicer if BSTArbre would just provide the means to iterate over the elements in the desired order, and let the caller decide what to do with it. Imagine being able to write:

for (auto& node: tree.preorder()) {
    std::cout << node->getKey() << '\n';
}

This will require some work; you would have to create a preorder() functions that returns a class that has begin() and end() member functions, those member functions should return iterators that iterate over the tree in the desired order.

I would start with just adding iterators to BSTArbre directly, such that you can write:

for (auto& node: tree) {
    ...
}

And just have that do an in-order iteration over the nodes. Find some tutorial about writing your own iterators.

This might seem a lot of work, but if you do this, then apart from range-for working with your class, many STL algorithms might also be able to work directly with your class.

Only store a single value in a node

Each BSTNode has a single key and a std::list of values. Maybe that's what you needed, but now you've had to add functions to manipulate that list, adding complexity to your classes. Instead, I would just store a single value:

V value;

And if you want to have a binary search tree that stores a list of values, you can simply have the caller make that explicit. For example, like so:

BSTArbre<int, std::list<int>> tree;
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.