Recursive binary search tree

Question

How is my usage of std::unique_ptr() and std::move()? How can I improve this code?

//I don't know what to return when key is not found, so throw std::runtime_error()
//this code does not have handwritten copy/move/destruct because I think unique_ptr already handled the node pointers
template<typename T>
using Ptr = std::unique_ptr<T>;

template<typename K, typename V>
class Bst {

    struct Node {
        K key;
        V val;
        std::size_t n;
        Ptr<Node> left;
        Ptr<Node> right;

        Node(const K& k, const V& v, const std::size_t& s) : key(k), val(v), n(s), left(nullptr), right(nullptr) { }
    };

    Ptr<Node> root;

public:

    Bst() :root{nullptr} { }

    std::size_t size() {
        return size(root);
    }

    std::size_t size(Ptr<Node>& t) {
        return (t == nullptr) ? 0 : t->n;
    }

    void insert(const K& k, const V& v) {
        root = insert(root,k,v);
    }

    Ptr<Node> insert(Ptr<Node>& t, const K& k, const V& v) {
        if (t == nullptr) {
            Ptr<Node> node(new Node(k,v,1));
            return node;
        }
        if (k < t->key) {
            t->left = insert(t->left,k,v);
        } else if (k > t->key) {
            t->right = insert(t->right,k,v);
        } else {
            t->val = v;
        }
        t->n = size(t->left)+size(t->right)+1;
        return std::move(t);
    }

    V& operator[](const K& k) {
        return get(root,k);
    }

    V& get(Ptr<Node>& t, const K& k) {
        if (t == nullptr) {
            t = insert(t,k,{});
            return t->val;
        }
        if (k < t->key) {
            return get(t->left,k);
        } else if (k > t->key) {
            return get(t->right,k);
        } else {
            return t->val;
        }
    }

    K min() {
        check(root);
        return min(root)->key;;
    }

    Ptr<Node>& min(Ptr<Node>& t) {
        if (t->left == nullptr) {
            return t;
        }
        return min(t->left);
    }

    K max() {
        check(root);
        return max(root)->key;
    }

    Ptr<Node>& max(Ptr<Node>& t) {
        if (t->right == nullptr) {
            return t;
        }
        return max(t->right);
    }

    void remove_min() {
        check(root);
        root = remove_min(root);
    }

    Ptr<Node> remove_min(Ptr<Node>& t) {
        if (t->left == nullptr) {
            return std::move(t->right);
        }
        t->left = remove_min(t->left);
        t->n = size(t->left)+size(t->right)+1;
        return std::move(t);
    }

    void remove_max() {
        check(root);
        root = remove_max(root);
    }

    Ptr<Node> remove_max(Ptr<Node>& t) {
        if (t->right == nullptr) {
            return std::move(t->left);
        }
        t->right = remove_max(t->right);
        t->n = size(t->left)+size(t->right)+1;
        return std::move(t);
    }

    void remove(K k) {
        root = remove(root, k);
    }

    Ptr<Node> remove(Ptr<Node>& t, K k) {
        check(t);
        if      (k < t->key){
            t->left = remove(t->left,  k);
        } else if (k > t->key){
            t->right = remove(t->right, k);
        } else {
            if (t->right == nullptr) {
                return std::move(t->left);
            }
            if (t->left == nullptr) {
                return std::move(t->right);
            }
            Ptr<Node> d = std::move(t);
            t = std::move(min(d->right));
            t->right = remove_min(t);
            t->left = std::move(d->left);
        }
        t->n = size(t->left)+size(t->right)+1;
        return std::move(t);
    }

    void traverse() {
        traverse(root);
    }

    void traverse(Ptr<Node>& t) {
        if (t == nullptr) {
            return;
        }
        traverse(t->left);
        std::cout << t->key << " " << t->val << '\n';
        traverse(t->right);
    }

private:

    void check(Ptr<Node>& t) {
        if (t == nullptr) {
            throw std::runtime_error("No node");
        }
    }

};

Answer 1

How is my usage of std::unique_ptr() and std::move()?

It's actually more common to use raw pointers with data structures, but I don't think it would hurt to use smart pointers instead. It would avoid the need for a destructor, though it's not too difficult to define a proper destructor for a tree.

My understanding of std::move() is that it's not particularly useful to return by that, even when it appears to be viable. This would also prevent the compiler from making its own decisions. A C++11 compliant compiler should be able to utilize move semantics as needed, and this is one of the times where it's better to let the compiler take over. Forcing something on it may cause problems, or it may simply try to ignore what you're telling it to do (this is where the code's behavior should be tested).

---

• There's no need for multiple private sections, especially with them in between one large public section. This can just be combined into one of the existing sections.

• This is greatly lacking const-correctness. Member functions that don't modify data members, such as getters, should be const:

  std::size_t size() const {
      return size(root);
  }
  

  Since there are many other applicable functions here, I'll let you find and change the rest of them. The compiler will correct you if you make a mistake with this.

  This also applies to objects of non-primitive types being passed to any type of function. If they're not being modified, they should be passed by const& (if move semantics are not viable).

• It makes more sense for Bst, not Node, to have a size field. One node won't have a particular size; it'll have value(s) and pointer(s). Having it for Bst will allow you to maintain the number of nodes currently in the structure. It'll also allow you to have just one size() member function that returns the value of this field.

• Since you're defining operator[], you should also have an at(), similar to the standard library. This should do the same thing, but also throw an exception if the index is out of bounds.

Answer 2

Please don't introduce global name aliases in a header file like this:

template<typename T>
using Ptr = std::unique_ptr<T>;

You're setting yourself up for name collisions and other nasties. Just use the god... I mean committee given names.

If you really want a shorthand, then use a type-local alias. Like this:

template<typename K, typename V>
class Bst {
private:
    struct Node;
public:
    typedef std::unique_ptr<Node> NodePtr;

It encapsulates the shorthand with the context in which it is used. As an added benefit you can now change the implementation from unique_ptr to shared_ptr if need be, without affecting the rest of the application.

The C++11 keyword auto will save your clients typing Bst::NodePtr. Also NodePtr is shorter to type than Ptr<Node> ;)

I agree with RubberDuck on the naming. Prefer BinarySearchTree as class name. Also I'm leaving the indepth review for some one with more time on their hands.

Answer 3

Y u shrt yr nms?

Bst is a really bad name. It's completely meaningless. Call your class what it is, a BinarySearchTree. You have a similar issue with your names for Key and Value. Code is read much more often than it's written, so it's important to be crystal clear with our naming. Particularly our public API. What would you think/say if you say this in some code you were unfamiliar with?

Bst * p1 = new Bst;

I'll leave an actual review of your implementation to the c++ experts though.